×

Transversals and bipancyclicity in bipartite graph families. (English) Zbl 1478.05087

Summary: A bipartite graph is called bipancyclic if it contains cycles of every even length from four up to the number of vertices in the graph. A theorem of E. Schmeichel and J. Mitchem [J. Graph Theory 6, 429–439 (1982; Zbl 0502.05036)] states that for \(n \geqslant 4\), every balanced bipartite graph on \(2n\) vertices in which each vertex in one color class has degree greater than \(\frac{n}{2}\) and each vertex in the other color class has degree at least \(\frac{n}{2}\) is bipancyclic. We prove a generalization of this theorem in the setting of graph transversals. Namely, we show that given a family \(\mathcal{G}\) of \(2n\) bipartite graphs on a common set \(X\) of \(2n\) vertices with a common balanced bipartition, if each graph of \(\mathcal G\) has minimum degree greater than \(\frac{n}{2}\) in one color class and minimum degree at least \(\frac{n}{2}\) in the other color class, then there exists a cycle on \(X\) of each even length \(4 \leqslant \ell \leqslant 2n\) that uses at most one edge from each graph of \(\mathcal G\). We also show that given a family \(\mathcal G\) of \(n\) bipartite graphs on a common set \(X\) of \(2n\) vertices meeting the same degree conditions, there exists a perfect matching on \(X\) that uses exactly one edge from each graph of \(\mathcal G\).

MSC:

05C45 Eulerian and Hamiltonian graphs
05C38 Paths and cycles
05C75 Structural characterization of families of graphs
05C12 Distance in graphs
05C07 Vertex degrees

Citations:

Zbl 0502.05036
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] R. Aharoni, M. DeVos, S. Gonz´alez Hermosillo de la Maza, A. Montejano, and R. ˇS´amal. A rainbow version of Mantel’s theorem.Adv. Comb., pages Paper No. 2, 12, 2020. · Zbl 1450.05021
[2] R. Aharoni, A. Georgakopoulos, and P. Spr¨ussel. Perfect matchings inr-partite r-graphs.European J. Combin., 30(1):39-42, 2009. · Zbl 1204.05072
[3] R. Aharoni, C. S. J. A. Nash-Williams, and S. Shelah. A general criterion for the existence of transversals.Proc. London Math. Soc. (3), 47(1):43-68, 1983. · Zbl 0522.05002
[4] J. A. Bondy. Pancyclic graphs. I.J. Combinatorial Theory Ser. B, 11:80-84, 1971. · Zbl 0183.52301
[5] Y. Cheng, G. Wang, and Y. Zhao. Rainbow pancyclicity in graph systems.Electron. J. Combin., 28(3):#P3.24, 2021. · Zbl 1470.05088
[6] V. Chv´atal. On Hamilton’s ideals.J. Combinatorial Theory Ser. B, 12:163-168, 1972. · Zbl 0213.50803
[7] G. A. Dirac. Some theorems on abstract graphs.Proc. London Math. Soc. (3), 2:69-81, 1952. · Zbl 0047.17001
[8] P. Erd˝os, A. Hajnal, and E. C. Milner. On sets of almost disjoint subsets of a set. Acta Math. Acad. Sci. Hungar., 19:209-218, 1968. · Zbl 0174.01804
[9] G. Fan. New sufficient conditions for cycles in graphs.J. Combin. Theory Ser. B, 37(3):221-227, 1984. · Zbl 0551.05048
[10] G. R. T. Hendry. An Ore-type sufficient condition for a bipancyclic ordering.Discrete Math., 102(1):47-49, 1992. · Zbl 0766.05042
[11] F. Joos and J. Kim. On a rainbow version of Dirac’s theorem.Bull. Lond. Math. Soc., 52(3):498-504, 2020. · Zbl 1444.05078
[12] J. Moon and L. Moser. On Hamiltonian bipartite graphs.Israel J. Math., 1:163-165, 1963. · Zbl 0119.38806
[13] O. Ore. Note on Hamilton circuits.Amer. Math. Monthly, 67:55, 1960. · Zbl 0089.39505
[14] L. P´osa. A theorem concerning Hamilton lines.Magyar Tud. Akad. Mat. Kutat´o Int. K¨ozl., 7:225-226, 1962. · Zbl 0114.40003
[15] E. Schmeichel and J. Mitchem. Bipartite graphs with cycles of all even lengths.J. Graph Theory, 6(4):429-439, 1982. · Zbl 0502.05036
[16] I. M. Wanless. Transversals in Latin squares: a survey. InSurveys in combinatorics 2011, volume 392 ofLondon Math. Soc. Lecture Note Ser., pages 403-437. Cambridge Univ. Press, Cambridge, 2011 · Zbl 1226.05067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.