% Template for Indonesian Journal of Combinatorics (IJC)
% This file must be in the same folder as ijc.sty 
\documentclass[12pt]{elsarticle}
%\usepackage[dvipdfmx]{graphics}
\usepackage[left=1in,right=1in, top=1.2in,bottom=1.2in]{geometry}
\usepackage{ijc}
\usepackage{times}
\usepackage{amssymb,amsthm,latexsym,amsmath,epsfig,pgf}

% Set the volume if you know.
\volume{{\bf x} (x)}

% Set the starting page
\firstpage{1}

% Put new theorem or any other settings for your document here
\newtheorem{theorem}{Theorem}[section]
\newtheorem*{theorem A}{Theorem A}
\newtheorem*{theorem B}{N\"olker's Theorem}
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{problem}{Problem}
\newtheorem*{question}{Question}
\newtheorem {conjecture}{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}{Remark}[section]
\theoremstyle{remark}
\newtheorem{remarks}{Remarks}


% Title (or short title) and author name for the header
\runauth{
The degree sequences of with restrictions
Title of the article for header
\hspace{2ex} $\arrowvert$\hspace{2ex}
R. Ichishima {\it et al.}}


\begin{document}

\begin{frontmatter}
% Write your paper title here
  \papertitle{The degree sequences of with restrictions}
    
%% use optional labels to link authors explicitly to addresses. The label may be more than one, use comma to separate

%\author[label1,label]{First Author${}^1$}

\author[label1]{Rikio Ichishima}
\author[label2]{Francesc A. Muntaner-Batle}
\author[label3]{Miquel Rius-Font}
\author[label4]{\\Yukio Takahashi}

\address[label1]{
Department of Sport and Physical Education, Faculty of Physical
Education, Kokushikan University, 7-3-1 Nagayama, Tama-shi, Tokyo 206-8515,
Japan
}
\address[label2]{
Graph Theory and Applications Research Group, School of Electrical
Engineering and Computer Science, Faculty of Engineering and Built
Environment, The University of Newcastle, NSW 2308 Australia  }
\address[label3]{}

\address[label4]{
Department of Science and Engineering, Faculty of Electronics and
Informations, Kokushikan University, 4-28-1 Setagaya, Setagaya-ku, Tokyo
154-8515, Japan  

\vspace*{2.5ex} 
        {\normalfont ichishim@kokushikan.ac.jp, famb1es@yahoo.es, Mriusfont@gmail.com, takayu@kokushikan.ac.jp}
}

\begin{abstract}
Two finite sequences $s_{1}$ and $s_{2}$ of nonnegative integers are called
bigraphical if there exists a bipartite graph $G$ with partite sets $V_{1}$
and $V_{2}$ such that $s_{1}$ and $s_{2}$ are the degrees in $G$ of the
vertices in $V_{1}$ and $V_{2}$, respectively. In this paper, we introduce
the concept of $1$-graphical sequences and present a necessary and
sufficient condition for a sequence to be $1$-graphical in terms of
bigraphical sequences.  

\let\thefootnote\relax\footnotetext{Received: xx xxxxx 20xx,\quad
  Accepted: xx xxxxx 20xx.\\[3ex]
  }
  
\end{abstract}

\begin{keyword}
  % Separate keyword by \sep
degree \sep degree sequence \sep graphical sequence \sep bigraphical sequence \sep $1$-graphical sequence  

% Write the classification number
Mathematics Subject Classification : 05C07

\end{keyword}

\end{frontmatter}

%% Main text
\section{Introduction}

We generally follow the notation and terminology pertaining to graphs of 
\cite{CL}.

If $F$ is a nonempty subset of the edge set $E\left( G\right) $ of a graph $%
G $, then the subgraph $\left\langle F\right\rangle $ \emph{induced by} $F$
is the graph whose vertex set consists of those vertices of $G$ incident
with at least one edge of $F$ and whose edge set is $F$.

The \emph{degree of }a\emph{\ vertex} $v$ in a graph $G$ is the number of
edges of $G$ incident with $v$, which is denoted by $\deg v$. A vertex is
called \emph{even} or \emph{odd} according to whether its degree is even or
odd.

A sequence $d_{1},d_{2},\ldots ,d_{n}$ of nonnegative integers is called a 
\emph{degree sequence} of a graph $G$ if the vertices of $G$ can be labeled $%
v_{1},v_{2},\ldots ,v_{n}$ so that $\deg v_{i}=d_{i}$ for all $i$. We adopt
the convention that the vertices have been labeled so that $d_{1}\geq
d_{2}\geq \cdots \geq d_{n}$. We call a sequence of nonnegative integers 
\emph{graphical} if it is the degree sequence of some graph. A necessary and
sufficient condition for a sequence to be graphical was found by Havel \cite%
{Havel} and later rediscovered by Hakimi \cite{Hakimi}.

\begin{theorem}
\label{Havel-Hakimi}A sequence $s:d_{1},d_{2},\ldots ,d_{n}$ of nonnegative
integers with $d_{1}\geq d_{2}\geq \cdots \geq d_{n},n\geq 2,d_{1}\geq 1$ is
graphical if and only if the sequence $s^{\prime }:d_{2}-1,d_{3}-1,\ldots
,d_{d_{1}+1}-1$, $d_{d_{1}+2},\ldots ,d_{n}$ is graphical.
\end{theorem}

According to the definition of a simple graph, two distinct vertices are
joined by at most one edge. If we allow more than one edge (but a finite
number) to join pairs of vertices, the resulting structure is called a \emph{%
multigraph}. If two or more edges join the same two vertices in a
multigraph, then these edges are referred to as \emph{multiple edges}.
Hakimi \cite{Hakimi} extended the preceding result to multigraphs.

\begin{theorem}
\label{Hakimi}Let $d_{1},d_{2},\ldots ,d_{n}$ be nonnegative integers with $%
d_{1}\geq d_{2}\geq \cdots \geq d_{n}$ and $n\geq 2$. Then there exists a
multigraph with degree sequence $s:d_{1},d_{2},\ldots ,d_{n}$ if and only if 
$\sum_{i=1}^{n}d_{i}$ is even and $d_{1}\leq d_{2}+d_{3}+\cdots +d_{n}$.
\end{theorem}

Two finite sequences $s_{1}$ and $s_{2}$ of nonnegative integers are called 
\emph{bigraphical} if there exists a bipartite graph $G$ with partite sets $%
V_{1}$ and $V_{2}$ such that $s_{1}$ and $s_{2}$ are the degrees in $G$ of
the vertices in $V_{1}$ and $V_{2}$, respectively. The following result is
an analog of Theorem \ref{Havel-Hakimi} for graphs (see [1, p. 16]).

\begin{theorem}
\label{Gate-Ryser}The sequences $s_{1}:a_{1},a_{2},\ldots ,a_{r}$ and $%
s_{2}:b_{1},b_{2},\ldots ,b_{t}$ of nonnegative integers with $r\geq
2,a_{1}\geq a_{2}\geq \cdots \geq a_{r},$ $b_{1}\geq b_{2}\geq \cdots \geq
b_{t}$, $0<a_{1}\leq t,0<b_{1}\leq r$ are bigraphical if and only if $%
s_{1}^{\prime }:a_{2},a_{3},\ldots ,a_{r}$ and $s_{2}^{\prime
}:b_{1}-1,b_{2}-1,\ldots ,b_{a_{1}}-1$, $b_{a_{1}+1}-1,\ldots ,b_{t}$ are
bigraphical.
\end{theorem}

The \emph{outdegree} $\mathrm{od}$ $v$ of a vertex $v$ of a digraph $D$ is
the number of vertices of $D$ that are adjacent from $v$, while the \emph{%
indegree} $\mathrm{id}$ $v$ of $v$ is the number of vertices of $D$ adjacent
to $v$. The \emph{degree} $\deg v$ of a vertex $v$ of $D$ is defined by 
\begin{equation*}
\deg v=\mathrm{od}\text{ }v+\mathrm{id}\text{ }v\text{.}
\end{equation*}

A \emph{loop} is an edge that joins a vertex to itself and contributed to
the degree of a vertex twice. A graph $G$ is called a $1$\emph{-graph} if it
has at most one loop attached at each vertex and at most two multiple edges
joining each pair of vertices. A sequence $s$ is called $1$\emph{-graphical}
if there exists a $1$-graph that realizes $s$.

For the sake of notational convenience, we will denote the interval of
integers $x$ such that $a\leq x\leq b$ by simply writing $\left[ a,b\right] $%
.

In this paper, we present a necessary and sufficient condition for a
sequence to be $1$-graphical in terms of bigraphical sequences. To this end,
we use the following theorem, due to Veblen \cite{Veblen}, which
characterizes eulerian graphs in terms of their cycle structures.

\begin{theorem}
\label{Veblen}A nontrivial connected graph $G$ is eulerian if and only if $%
E\left( G\right) $ can be partitioned into subsets $E_{i}$, $i\in \left[ 1,k%
\right] $, where each subgraph $\left\langle E_{i}\right\rangle $ is a cycle.
\end{theorem}

To conclude this introduction, it is worth to mention that L\'{o}pez and
Muntaner-Batle \cite{LM} completely characterized the degree sequences of
graphs with at most one loop attached at each vertex and no multiple edges.
Hence, the work conducted in this paper would be a natural continuation of
their work.

\section{Characterization of 1-graphical sequences}

We are now ready to state and prove the following theorem.

\begin{theorem}
A sequence $s:d_{1},d_{2},\ldots ,d_{n}$ of nonnegative integers with $%
d_{1}\geq d_{2}\geq \cdots \geq d_{n}$ and $n\geq 2$ is $1$-graphical if and
only if there exist \textit{bigraphical }sequences $s_{1}:a_{1},a_{2},\ldots
,a_{n}$ and $s_{2}:b_{1},b_{2},\ldots ,b_{n}$ such that $a_{i}=b_{i}=d_{i}/2$
for even $d_{i}$\textit{\ and }\textbf{\ }$a_{i}+b_{i}=d_{i}$ for odd\textit{%
\ }$d_{i}$, where $i\in \left[ 1,n\right] $.
\end{theorem}

\begin{proof}
By assumption, there exists a $1$-graph that realizes $s$. Assume that the
vertices of $G$ are labeled $v_{1},v_{2},\ldots ,v_{n}$ so that $\deg
v_{i}=d_{i}$ for all $i$, and construct a new graph $H$ with vertex set 
\begin{equation*}
V\left( H\right) =V\left( G\right) \cup \left\{ u\right\} 
\end{equation*}%
and edge set 
\begin{equation*}
E\left( H\right) =E\left( G\right) \cup \left\{ uv_{i}\left\vert d_{i}\text{
is odd}\right. \right\} \text{.}
\end{equation*}%
Since in any graph, there is an even number of odd vertices, it follows that
all vertices in $H$ are even vertices. Therefore, since every component of $H
$ is eulerian, it follows from Theorem \ref{Veblen} that $E\left( H\right) $
can be partitioned into subsets $E_{i}$, $i\in \left[ 1,k\right] $, where
each subgraph $\left\langle E_{i}\right\rangle $ is a cycle. If we orient
each cycle in $\left\langle E_{i}\right\rangle $ cyclically, then we obtain
a digraph $D$ with the property that $\mathrm{od}$ $v=\mathrm{id}$ $v$ for
every $v\in V\left( D\right) $. Now, let $D^{\prime }$ be the digraph
obtained by deleting the vertex $u$ from $D$. Certainly, $d_{i}=\mathrm{od}$ 
$v+\mathrm{id}$ $v$ for each $v\in V\left( D^{\prime }\right) $.
Furthermore, the vertices of $D^{\prime }$ have the properties that $\mathrm{%
od}$ $v=\mathrm{id}$ $v=d_{i}/2$ for even $d_{i}$ and $\left\vert \mathrm{od}%
\text{ }v-\mathrm{id}\text{ }v\right\vert =1$ for odd $d_{i}$, where $i\in %
\left[ 1,n\right] $. Let $A\left( D^{\prime }\right) =\left[ \alpha _{ij}%
\right] $ be the adjacency matrix of $D^{\prime }$, and construct the
bipartite digraph $D^{\ast }$ with partite sets 
\begin{equation*}
X=\left\{ x_{i}\left\vert 1\leq i\leq n\right. \right\} \text{ and }%
Y=\left\{ y_{i}\left\vert 1\leq i\leq n\right. \right\} \text{,}
\end{equation*}%
and with the arcs in such a way that $\left( x_{i},y_{j}\right) \in E\left(
D^{\ast }\right) $ if and only if $\alpha _{ij}=1$. It remains to observe
that the sequences of outdegrees and of indegrees satisfy the required
properties.

Let $G$ be the bipartite graph with partite sets 
\begin{equation*}
X=\left\{ x_{i}\left\vert i\in \left[ 1,n\right] \right. \right\} \text{ and 
}Y=\left\{ y_{i}\left\vert i\in \left[ 1,n\right] \right. \right\} 
\end{equation*}%
such that $s_{1}$ and $s_{2}$ are the degrees in $G$ of the vertices in $X$
and $Y$, respectively. Further, consider the digraph $D$ obtained from $G$,
and let $\left[ \beta _{ij}\right] $ be the $n\times n$ matrix with $\beta
_{ij}=1$ if and only if $\left( x_{i},y_{j}\right) $ is an arc of $D$ and $%
\beta _{ij}=0$ otherwise. Let $D^{\prime }$ be the digraph with the vertex
set $V\left( D^{\prime }\right) =\left\{ w_{i}\left\vert 1\leq i\leq
n\right. \right\} $ and adjacency matrix $\left[ \beta _{ij}\right] $ so
that $\mathrm{od}$ $w_{i}+\mathrm{id}$ $w_{i}=a_{i}+b_{i}=d_{i}$. Then the
graph obtained by replacing each arc $\left( u,v\right) $ of $D^{\prime }$
by the edge of $uv$ is a $1$-graph that realizes a sequence $s$.
\end{proof}

This result has the following consequences.

\begin{corollary}
Let $s:d_{1},d_{2},\ldots ,d_{n}$ be a sequence of nonnegative even integers
with $d_{1}\geq d_{2}\geq \cdots \geq d_{n}$ and $n\geq 2$. Then $s$ is $1$%
-graphical if and only if the sequences 
\begin{equation*}
s_{1}=s_{2}:\frac{d_{1}}{2},\frac{d_{2}}{2},\ldots ,\frac{d_{n}}{2}
\end{equation*}%
are bigraphical.
\end{corollary}

\begin{corollary}
Let $s:d_{1},d_{2},\ldots ,d_{n}$ be a sequence of nonnegative integers with 
$d_{1}\geq d_{2}\geq \cdots \geq d_{n}$, $n\geq 2$ and the properties that $%
d_{i}=d_{i+1}$ for $k\leq i\leq k+l-1$, $d_{i}$ is even for all $i\in \left[
1,k-1\right] \cup \left[ k+l+1,n\right] $ and $d_{i}$ is odd for all $i\in %
\left[ 1,k+l\right] $. Then $s$ is $1$-graphical if and only if the
sequences 
\begin{eqnarray*}
s_{1} &=&s_{2}:\frac{d_{1}}{2},\frac{d_{2}}{2},\ldots ,\frac{d_{k-1}}{2}%
,\left\lceil \frac{d_{k}}{2}\right\rceil ,\left\lceil \frac{d_{k+1}}{2}%
\right\rceil ,\ldots ,\left\lceil \frac{d_{k+\left( l-1\right) /2}}{2}%
\right\rceil , \\
&&\left\lfloor \frac{d_{k+\left( l+1\right) /2}}{2}\right\rfloor ,\ldots
,\left\lfloor \frac{d_{k+l}}{2}\right\rfloor ,\ldots ,\frac{d_{k+l+1}}{2},%
\frac{d_{k+l+2}}{2},\ldots ,\frac{d_{n}}{2}
\end{eqnarray*}%
are bigraphical.
\end{corollary}

\begin{corollary}
Let $s:d_{1},d_{2},\ldots ,d_{n}$ be a sequence of nonnegative integers with 
$d_{1}\geq d_{2}\geq \cdots \geq d_{n}$, $n\geq 2$ and the properties that
there exist some integers $k$ and $l$, $1\leq k<l\leq n$, so that $d_{k}$
and $d_{l}$ are odd, and $d_{i}$ is even for all $i\in \left[ 1,n\right]
\backslash \left\{ k,l\right\} $. Then $s$ is $1$-graphical if and only if
the sequences 
\begin{equation*}
s_{1}:\frac{d_{1}}{2},\frac{d_{2}}{2},\ldots ,\frac{d_{k-1}}{2},\left\lceil 
\frac{d_{k}}{2}\right\rceil ,\frac{d_{k+1}}{2},\ldots ,\frac{d_{l-1}}{2}%
,\left\lfloor \frac{d_{l}}{2}\right\rfloor ,\frac{d_{l+1}}{2},\ldots ,\frac{%
d_{n}}{2}
\end{equation*}%
and 
\begin{equation*}
s_{2}:\frac{d_{1}}{2},\frac{d_{2}}{2},\ldots ,\frac{d_{k-1}}{2},\left\lfloor 
\frac{d_{k}}{2}\right\rfloor ,\frac{d_{k+1}}{2},\ldots ,\frac{d_{l-1}}{2}%
,\left\lceil \frac{d_{l}}{2}\right\rceil ,\frac{d_{l+1}}{2},\ldots ,\frac{%
d_{n}}{2}
\end{equation*}%
are bigraphical.
\end{corollary}

\section{Conclusions}

The bipartite realization problem formulates as follows: Given two finite
sequences $s_{1}$ and $s_{2}$ of nonnegative integers, is there a labeled
bipartite graph such that the pair of $s_{1}$ and $s_{2}$ is the degree
sequence of some bipartite graph? This classical decision problem belongs to
the complexity class of \textrm{P}. This can be proven by two known
approaches established in 1957 by Gale \cite{Gale} and also by Ryser \cite%
{Ryser}. In this paper, we have extended Theorem \ref{Hakimi} by presenting
necessary and sufficient conditions for a sequence of nonnegative integers
to be $1$-graphical in terms of bigraphical sequences. These together with
the bipartite realization problem imply that the decision problem associated
with determining whether a given sequence of nonnegative integers is $1$%
-graphical remains to be the complexity class of \textrm{P}.


\section*{Acknowledgement}
The second and third authors would like to acknowledge Dr. Keith Edwards for
the discussions maintained with us during the elaboration of this work.

\section*{References} 
\begin{thebibliography}{99}
\bibitem{CL} G. Chartrand and L. Lesniak, \textit{Graphs \& Digraphs} 3th
ed. CRC Press (1996).

\bibitem{Gale} D. Gale, A theorem on flows in networks, \textit{Pacific J.
Math}., \textbf{7} (2) (1957) 1073--1082.

\bibitem{Hakimi} S. Hakimi, On the realizability of a set of integers as
degrees of the vertices of a graph, \textit{J. SIAM Appl. Math}., \textbf{10}
(1962) 496--506.

\bibitem{Havel} V. Havel, A remark on the existence of finite graphs
(Czech), \textit{\v{C}asopis P\u{e}st. Math}.,\textbf{\ 80} (1955) 477--480.

\bibitem{LM} S. C. L\'{o}pez and F. A Muntaner-Batle, Mirror bipartite
graphs, preprint, 2013. Available at
https://ui.adsabs.harvard.edu/abs/2013arXiv1305.5145L/abstract.

\bibitem{Ryser} H. J. Ryser, Combinatorial properties of matrices of zeros
and ones, \textit{Can. J. Math}., \textbf{9} (1957) 371--377.

\bibitem{Veblen} O. Veblen, An application of modular equations in analysis
situs, \textit{Math. Ann}., \textbf{14} (1912--1913) 86--94.  

\end{thebibliography}

\end{document}

%%
%% End of file `ijctemplate.tex'.