Vertex-disjoint multiquadrilaterals in multigraphs

Abstract

A cycle of length 4 is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most 2. A quadrilateral with four multiedges is called heavy-quadrilateral. It is proved that if the minimum degree of M is at least 6k-2, then M contains k vertex-disjoint quadrilaterals, such that k-1 of them are heavy-quadrilaterals and the remaining one is a quadrilateral with three multiedges, with only three exceptions.

Keywords

Multiquadrilateral / standard multigraph / minimum degree

References

[1] Bang-JensenJ.GutinG.Z., Digraphs: Theory, Algorithms and Applications, London: Springer-Verlag, 2008

[2] Czygrinow A., Kierstead, H.A. , Molla, T. . On directed versions of the Corrádi-Hajnal corollary. European J. Combin. 2014; 42: 1–14

[3] ErdösP., Some recent combinatorial problems, Technical Report, Bielefeld: University of Bielefeld, 1990.

[4] Gao Y.S., Zou, Q.S. , Ma, L.Y. . Vertex-disjoint quadrilaterals in multigraphs. Graphs Combin. 2017; 33(4): 901–912

[5] Randerath B., Schiermeyer, I. , Wang, H. . On quadriaterals in a graph. Discrete Math. 1999; 203(1/2/3): 229–237

[6] Wang H. . Proof of the Erdös-Faudree conjecture on quadrilaterals. Graphs Combin. 2010; 26(6): 833–877

[7] Zhang D.H. , Wang, H. . Disjoint directed quadrilaterals in a directed graph. J. Graph Theory 2005; 50(2): 91–104

RIGHTS & PERMISSIONS

Higher Education Press 2025