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)
28 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 languageUndefined
Pages (from-to)2800-2818
Number of pages19
JournalDiscrete mathematics
Volume312
Issue number18
DOIs
Publication statusPublished - Sep 2012

Keywords

  • EWI-22737
  • MSC-05C
  • Induced subgraph
  • Forbidden subgraph
  • Homogeneously traceable graph
  • METIS-296433
  • IR-83467
  • Hamiltonian graph

Cite this

Li, Binlong ; Li, Binlong ; Broersma, Haitze J. ; Zhang, Shenggui. / Pairs of forbidden induced subgraphs for homogeneously traceable graphs. In: Discrete mathematics. 2012 ; Vol. 312, No. 18. pp. 2800-2818.
@article{e54278ae9de54eef95ffd8e6f4b33b59,
title = "Pairs of forbidden induced subgraphs for homogeneously traceable graphs",
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.",
keywords = "EWI-22737, MSC-05C, Induced subgraph, Forbidden subgraph, Homogeneously traceable graph, METIS-296433, IR-83467, Hamiltonian graph",
author = "Binlong Li and Binlong Li and Broersma, {Haitze J.} and Shenggui Zhang",
note = "eemcs-eprint-22737",
year = "2012",
month = "9",
doi = "10.1016/j.disc.2012.05.018",
language = "Undefined",
volume = "312",
pages = "2800--2818",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "18",

}

Pairs of forbidden induced subgraphs for homogeneously traceable graphs. / Li, Binlong; Li, Binlong; Broersma, Haitze J.; Zhang, Shenggui.

In: Discrete mathematics, Vol. 312, No. 18, 09.2012, p. 2800-2818.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Pairs of forbidden induced subgraphs for homogeneously traceable graphs

AU - Li, Binlong

AU - Li, Binlong

AU - Broersma, Haitze J.

AU - Zhang, Shenggui

N1 - eemcs-eprint-22737

PY - 2012/9

Y1 - 2012/9

N2 - 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.

AB - 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.

KW - EWI-22737

KW - MSC-05C

KW - Induced subgraph

KW - Forbidden subgraph

KW - Homogeneously traceable graph

KW - METIS-296433

KW - IR-83467

KW - Hamiltonian graph

U2 - 10.1016/j.disc.2012.05.018

DO - 10.1016/j.disc.2012.05.018

M3 - Article

VL - 312

SP - 2800

EP - 2818

JO - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 18

ER -