Geodesic
A sufficient condition for a balanced bipartite digraph to be hamiltonian
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3.

Voir la notice de l'article provenant de la source Episciences

We describe a new type of sufficient condition for a balanced bipartite digraph to be hamiltonian. Let $D$ be a balanced bipartite digraph and $x,y$ be distinct vertices in $D$. $\{x, y\}$ dominates a vertex $z$ if $x\rightarrow z$ and $y\rightarrow z$; in this case, we call the pair $\{x, y\}$ dominating. In this paper, we prove that a strong balanced bipartite digraph $D$ on $2a$ vertices contains a hamiltonian cycle if, for every dominating pair of vertices $\{x, y\}$, either $d(x)\ge 2a-1$ and $d(y)\ge a+1$ or $d(x)\ge a+1$ and $d(y)\ge 2a-1$. The lower bound in the result is sharp. 
@article{DMTCS_2017_19_3_a10,
     author = {Wang, Ruixia},
     title = {A sufficient condition for a balanced bipartite digraph to be hamiltonian},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-3-11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-11/}
}
TY  - JOUR
AU  - Wang, Ruixia
TI  - A sufficient condition for a balanced bipartite digraph to be hamiltonian
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-11/
DO  - 10.23638/DMTCS-19-3-11
LA  - en
ID  - DMTCS_2017_19_3_a10
ER  - 
%0 Journal Article
%A Wang, Ruixia
%T A sufficient condition for a balanced bipartite digraph to be hamiltonian
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-11/
%R 10.23638/DMTCS-19-3-11
%G en
%F DMTCS_2017_19_3_a10
Wang, Ruixia. A sufficient condition for a balanced bipartite digraph to be hamiltonian. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3. doi : 10.23638/DMTCS-19-3-11. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-11/

Cité par Sources :