On Quadrilaterals and 4-path in Claw-free Graphs

Qingsong Zou1, Lili Wang2, Guojun Li3
1“Department of Mathematics, Xidian University, Xi’an, 710071, P.R.China
2School of Economics and Management, Chang’an University, Xi’an, 710064, P.R.China
3School of Mathematics, Shandong University, Jinan, 250100, P.R.China

Abstract

Let \( G \) be a claw-free graph of order \( 4k \), where \( k \) is a positive integer. In this paper, it is proved that if the degree sum \( d(u) + d(v) \) is at least \( 4k – 2 \) for every pair of nonadjacent vertices \( u, v \in V(G) \), then \( G \) has a spanning subgraph consisting of \( k – 1 \) quadrilaterals and a 4-path such that all of them are vertex-disjoint, unless \( G \) is isomorphic to \( K_{4k_1 + 2} \cup K_{4k_2 + 2} \), or \( K_{4k_1 + 1} \cup K_{4k_2 + 3} \), where \( k_1 \geq 0, k_2 \geq 0, k_1 + k_2 = k – 1 \). We further showed that the requirement about claw-free is indispensable and the degree condition is sharp.

Keywords: claw-free, vertex-disjoint, quadrilaterals, 4-path MSC(2010): 05C38, 05C70