### Abstract

Original language | Undefined |
---|---|

Pages (from-to) | 2800-2818 |

Number of pages | 19 |

Journal | Discrete mathematics |

Volume | 312 |

Issue number | 18 |

DOIs | |

Publication status | Published - Sep 2012 |

### Keywords

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

### Cite this

*Discrete mathematics*,

*312*(18), 2800-2818. https://doi.org/10.1016/j.disc.2012.05.018

}

*Discrete mathematics*, vol. 312, no. 18, pp. 2800-2818. https://doi.org/10.1016/j.disc.2012.05.018

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

Research output: Contribution to journal › Article › Academic › peer-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 -