On a Problem of Wang Concerning the Hamiltonicity of Bipartite Digraphs
DOI:
https://doi.org/10.51408/1963-0003Keywords:
Digraph, cycle, Hamiltonian cycle, Bipartite balanced digraph, Perfect matchingAbstract
R. Wang (Discrete Mathematics and Theoretical Computer Science, vol. 19(3), 2017) proposed the following problem. Problem. Let D be a strongly connected balanced bipartite directed graph of order 2a ≥8. Suppose that d(x) ≥ 2a - k, d(y) ≥a + k or d(y) ≥2a - k, d(x) ≥a + k for every pair of vertices {x; y}with a common out-neighbour, where 2 • k • a=2. Is D Hamiltonian? In this paper, we prove that if a digraph D satis¯es the conditions of this problem, then (i) D contains a cycle factor, (ii) for every vertex x ∈ V (D) there exists a vertex y ∈ V (D) such that x and y have a common out-neighbour.
References
J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2001
G. Gutin, Criterion for complete bipartite digraphs to be Hamiltonian" , Vestsi Akad, Navuk BSSR Ser. Fiz.-Mat. Navuk vol. 1 , pp. 109-110, 1984.
G. Gutin, ‘’ Cycles and paths in semicomplete multipartite digraphs, theorems and algorithms: a survey" J. Graph Theory vol. 19, no. 4, pp. 481-505, 1995.
R. H Äaggkvist and Y .Manoussakis, Cycles and paths in bipartite tournaments with spanning con¯gurations" . Combinatorica, vol. 9, no. 1 , pp. 33-38, 1989.
Y .Manoussakis and I. Millis, A suffcient condition for maximum cycles in bipartite digraphs" , Discrete Math., vol. 207, pp. 161 -171 , 1999.
Adamus and L. A damus, A degree condition for cycles of maximum length in bipartite digraphs" , Discrete Math., vol. 312, pp. 1117-1122, 2012.
D .Amar and Y Manoussakis, Cycles and paths of many lengths in bipartite digraphs" J. Combin. Theory Ser. B 50, pp. 254-264, 1990.
Adamus, L. A damus and A Yeo, On the Meyniel condition for hamiltonicity in bipartite digraphs", Discrete Math. and Theoretical Computer Science,vol. 16, no. 1 , pp. 293-302, 2014.
Adamus, A degree sum condition for hamiltonicity in balanced bipartite digraphs", Graphs and Combinatorics, vol. 33, no. 1 , pp. 43-51 , 2017.
Wang, Asuffient condition for a balanced bipartite digraph to be Hamiltonian". Discrete Mathematics and Theoretical Computer Science, vol. 19, no. 3, 2017.
Kh. Darbinyan, Suffcient conditions for Hamiltonian cycles in bipartite digraphs", arX iv:1 604.08733v1 [matm.CO] 29, 15 pages, Apr 2016.
Kh. Darbinyan, Suffcient conditions for a balanced bipartite digraph to be even pancyclic", Discrete Applied Mathematics, vol. 238, pp. 70-76, 2018.
M. Meszka, New suffcient conditions for bipancyclicity of balanced bipartite digraphs",Discrete Math., Submitted for publication.
S. Kh. Darbinyan, Atheorem on even pancyclic bipartite digraphs", arX iv:1801 051 77v1 [matm.CO] 16, 12 pages, Jan 2018.
J. Adamus, A Meyniel-type condition for bipancyclicity in balanced bipartite digraphs", arX iv:1708.04674v2 [matm.CO], 7 pages, 22 A ug 2017.
Kh. Darbinyan, On pre-Hamiltonian cycles in balanced bipartite digraphs" , Mathematical problems of Computer Science, vol. 46, pp. 7-1 ,2014.
Kh. Darbinyan and I. A .Karapetyan, A Suffcient condition for pre-Hamiltonian Cycles in Bipartite D igraphs" , CSIT 2017 Revised Selected P apers,IEE conference proceeding,, pp. 101-109, DOI:101 109/CSITTechnol.2017.8312150.
O. Ore, Theory of graphs" , American Mathematical Society, Providence, R.I., American Mathematical Society Colloquium Publications, vol. 38, 1962.
C. Berge, Graphs and hypergraphs, North-Holland, Amsterdam, 1973.
J. A .Bondy, Basic Graph Theory: Paths and Circuits, In Handbook of combinatorics 1-2, Elsevier, Amsterdam, 1995.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
