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 -