Vertex-bipancyclicity in a bipartite graph collection

被引:1
作者
Hu, Jie [1 ]
Li, Luyi [1 ]
Li, Xueliang [1 ]
Xu, Ningyan [1 ]
机构
[1] Nankai Univ, Ctr Combinator & LPMC, Tianjin 300071, Peoples R China
基金
中国国家自然科学基金; 中国博士后科学基金;
关键词
Bipartite graph collection; Transversal; Vertex-bipancyclicity; Hamiltonian connectivity; Minimum degree; CYCLES;
D O I
10.1016/j.disc.2024.113980
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G={G(1), . . . ,G(2n)} be a bipartite graph collection on the common vertex bipartition (X,Y) with |X|=|Y|=n. We say that G is bipancyclic if there exists a partial G-transversal isomorphic to an l-cycle for each even integer l is an element of [4,2], while G is vertex-bipancyclic if any vertex is an element of X boolean OR Y is contained in a partial G-transversal isomorphic to an l-cycle for each even integer l is an element of [4,2]. Bradshaw in [Transversals and bipancyclicity in bipartite graph families, Electron. J. Comb., 2021] showed that for each i is an element of [2], if d(Gi)(x) > n/2 for each x is an element of X and d(Gi)(y) >= n/2 for each y is an element of Y, then G is bipancyclic, which generalizes a classical result of Schmeichel and Mitchem in [Bipartite graphs with cycles of all even lengths, J. Graph Theory, 1982] on the bipancyclicity of bipartite graphs to the setting of graph transversals. Motivated by their work, we study vertex-bipancyclicity in bipartite graph collections and prove that if delta(G(i)) >= +12 for any i is an element of [2n], then G is vertex-bipancyclic unless n=3 and G consists of 6 identical copies of a 6-cycle. Moreover, we also show the Hamiltonian connectivity of G. (c) 2024 Elsevier B.V. All rights reserved.
引用
收藏
页数:10
相关论文
共 21 条
[1]  
Aharoni R., 2020, Adv. Comb., V2
[2]   A Rainbow r-Partite Version of the Erdos-Ko-Rado Theorem [J].
Aharoni, Ron ;
Howard, David .
COMBINATORICS PROBABILITY & COMPUTING, 2017, 26 (03) :321-337
[3]  
Aharoni R, 2009, ELECTRON J COMB, V16
[4]  
[Anonymous], 1963, J MATH PURE APPL
[5]  
Bondy J.A., 1971, J COMBINATORIAL THEO, V11, P80
[6]  
Bondy J A., 1971, Proceedings of the Second Louisiana Conference on Combinatorics, Graph Theory and Computing, P167
[7]   From One to Many Rainbow Hamiltonian Cycles [J].
Bradshaw, Peter ;
Halasz, Kevin ;
Stacho, Ladislav .
GRAPHS AND COMBINATORICS, 2022, 38 (06)
[8]  
Bradshaw P, 2021, Arxiv, DOI arXiv:2102.12012
[10]   Rainbow spanning structures in graph and hypergraph systems [J].
Cheng, Yangyang ;
Han, Jie ;
Wang, Bin ;
Wang, Guanghui .
FORUM OF MATHEMATICS SIGMA, 2023, 11