TY - JOUR

T1 - The Hamiltonian properties in K1,r-free split graphs

AU - Dai, Guowei

AU - Zhang, Zan Bo

AU - Broersma, Hajo

AU - Zhang, Xiaoyan

N1 - Funding Information:
We are very grateful to the reviewers for their invaluable suggestions and comments, which greatly help to improve the manuscript. The research was partially supported by National Natural Science Foundation of China under Grant Nos. 11871280 , 11971349 and U1811461 , the Natural Science Foundation of Guangdong Province Grant No. 2020B1515310009 and the Qinglan Project of Jiangsu Province .
Publisher Copyright:
© 2022 Elsevier B.V.

PY - 2022/6

Y1 - 2022/6

N2 - For a connected graph F of order at least three, we say that a graph G is F-free if G does not contain an induced subgraph isomorphic to F. We call a connected graph G a split graph if the vertex set of G can be partitioned into a clique and an independent set. Motivated by a hamiltonicity result due to Renjith and Sadagopan (arXiv:1610.00855v3), involving K1,3-free split graphs, we study the hamiltonian properties of K1,r-free split graphs. In our first main result, we show that a K1,3-free split graph G is pancyclic if and only if G is 2-connected, which improves a result of Renjith and Sadagopan. Also, we prove that a K1,4-free split graph G is hamiltonian if G is 3-connected. Further, we give a conjecture as following: Let G be a K1,r+1-free split graph with at least three vertices. If G is r-connected, then G is hamiltonian.

AB - For a connected graph F of order at least three, we say that a graph G is F-free if G does not contain an induced subgraph isomorphic to F. We call a connected graph G a split graph if the vertex set of G can be partitioned into a clique and an independent set. Motivated by a hamiltonicity result due to Renjith and Sadagopan (arXiv:1610.00855v3), involving K1,3-free split graphs, we study the hamiltonian properties of K1,r-free split graphs. In our first main result, we show that a K1,3-free split graph G is pancyclic if and only if G is 2-connected, which improves a result of Renjith and Sadagopan. Also, we prove that a K1,4-free split graph G is hamiltonian if G is 3-connected. Further, we give a conjecture as following: Let G be a K1,r+1-free split graph with at least three vertices. If G is r-connected, then G is hamiltonian.

KW - Hamiltonian

KW - K,3-free

KW - K,4-free

KW - Pancyclic

KW - Split graph

KW - 2023 OA procedure

UR - http://www.scopus.com/inward/record.url?scp=85124954079&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2022.112826

DO - 10.1016/j.disc.2022.112826

M3 - Article

AN - SCOPUS:85124954079

SN - 0012-365X

VL - 345

JO - Discrete mathematics

JF - Discrete mathematics

IS - 6

M1 - 112826

ER -