Contents

On Quadrilaterals in a Bipartite Graph

Qingsong Zou1, Guojun Li2, Shuo Li3
1Department of Mathematics, Xidian University, Xi’an, 710071, P.R.China
2School of Mathematics, Shandong University, Jinan, 250100, P.R.China
3 Department of Mathematics, Changji University, Changji, 831100, P.R.China

Abstract

Let \( G = (V_1, V_2; E) \) be a bipartite graph with \( |V_1| = |V_2| = 2k \), where \( k \) is a positive integer. It is proved that if \( d(x) + d(y) \geq 3k \) for every pair of nonadjacent vertices \( x \in V_1 \), \( y \in V_2 \), then \( G \) contains \( k \) independent quadrilaterals.

Keywords: bipartite graph; quadrilaterals; cycle MSC(2000): 05C38, 05C70