arXiv Open Access 2016

Sufficient conditions for Hamiltonian cycles in bipartite digraphs

Samvel Kh. Darbinyan
Lihat Sumber

Abstrak

We prove two sharp sufficient conditions for hamiltonian cycles in balanced bipartite directed graph. Let $D$ be a strongly connected balanced bipartite directed graph of order $2a$. Let $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. (i) {\it If $a\geq 4$ and $max \{d(x), d(y)\}\geq 2a-1$ for every dominating pair of vertices $\{x,y\}$, then either $D$ is hamiltonian or $D$ is isomorphic to one exceptional digraph of order eight.} (ii) {\it If $a\geq 5$ and $d(x)+d(y)\geq 4a-3$ for every dominating pair of vertices $\{x,y\}$, then $D$ is hamiltonian.} The first result improves a theorem of R. Wang (arXiv:1506.07949 [math.CO]), the second result, in particular, establishes a conjecture due to Bang-Jensen, Gutin and Li (J. Graph Theory , 22(2), 1996) for strongly connected balanced bipartite digraphs of order at least ten.

Topik & Kata Kunci

Penulis (1)

S

Samvel Kh. Darbinyan

Format Sitasi

Darbinyan, S.K. (2016). Sufficient conditions for Hamiltonian cycles in bipartite digraphs. https://arxiv.org/abs/1604.08733

Akses Cepat

Lihat di Sumber
Informasi Jurnal
Tahun Terbit
2016
Bahasa
en
Sumber Database
arXiv
Akses
Open Access ✓