Pairs of forbidden induced subgraphs for homogeneously traceable graphs

Binlong Li, Binlong Li, Haitze J. Broersma, Shenggui Zhang

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
110 Downloads (Pure)

Abstract

A graph G is called homogeneously traceable if for every vertex v of G, G contains a Hamilton path starting from v. For a graph H, we say that G is H-free if G contains no induced subgraph isomorphic to H. For a family H of graphs, G is called H-free if G is H-free for every H∈H. Determining families of graphs H such that every H-free graph G has some graph property has been a popular research topic for several decades, especially for Hamiltonian properties, and more recently for properties related to the existence of graph factors. In this paper we give a complete characterization of all pairs of connected graphs R,S such that every 2-connected {R,S}-free graph is homogeneously traceable.
Original languageEnglish
Pages (from-to)2800-2818
Number of pages19
JournalDiscrete mathematics
Volume312
Issue number18
DOIs
Publication statusPublished - Sept 2012

Keywords

  • MSC-05C
  • Induced subgraph
  • Forbidden subgraph
  • Homogeneously traceable graph
  • Hamiltonian graph

Fingerprint

Dive into the research topics of 'Pairs of forbidden induced subgraphs for homogeneously traceable graphs'. Together they form a unique fingerprint.

Cite this