The Hamiltonian properties in K1,r-free split graphs

Guowei Dai, Zan Bo Zhang, Hajo Broersma, Xiaoyan Zhang*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
171 Downloads (Pure)

Abstract

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.

Original languageEnglish
Article number112826
JournalDiscrete mathematics
Volume345
Issue number6
DOIs
Publication statusPublished - Jun 2022

Keywords

  • Hamiltonian
  • K,3-free
  • K,4-free
  • Pancyclic
  • Split graph
  • 2023 OA procedure

Fingerprint

Dive into the research topics of 'The Hamiltonian properties in K1,r-free split graphs'. Together they form a unique fingerprint.

Cite this