# Forbidden triples implying Hamiltonicity: for all graphs

Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson

Discussiones Mathematicae Graph Theory (2004)

- Volume: 24, Issue: 1, page 47-54
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topRalph J. Faudree, Ronald J. Gould, and Michael S. Jacobson. "Forbidden triples implying Hamiltonicity: for all graphs." Discussiones Mathematicae Graph Theory 24.1 (2004): 47-54. <http://eudml.org/doc/270547>.

@article{RalphJ2004,

abstract = {In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i = K_\{1,3\}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_\{1,s\}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_\{1,3\}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁, G₂, G₃ such that all G₁G₂G₃-free graphs are hamiltonian.},

author = {Ralph J. Faudree, Ronald J. Gould, Michael S. Jacobson},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hamiltonian; induced subgraph; forbidden subgraphs; Hamiltonian graph},

language = {eng},

number = {1},

pages = {47-54},

title = {Forbidden triples implying Hamiltonicity: for all graphs},

url = {http://eudml.org/doc/270547},

volume = {24},

year = {2004},

}

TY - JOUR

AU - Ralph J. Faudree

AU - Ronald J. Gould

AU - Michael S. Jacobson

TI - Forbidden triples implying Hamiltonicity: for all graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2004

VL - 24

IS - 1

SP - 47

EP - 54

AB - In [2], Brousek characterizes all triples of graphs, G₁, G₂, G₃, with $G_i = K_{1,3}$ for some i = 1, 2, or 3, such that all G₁G₂G₃-free graphs contain a hamiltonian cycle. In [6], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁, G₂, G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁, G₂, G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In this paper, a characterization will be given of all triples G₁, G₂, G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are hamiltonian. This result, together with the triples given by Brousek, completely characterize the forbidden triples G₁, G₂, G₃ such that all G₁G₂G₃-free graphs are hamiltonian.

LA - eng

KW - hamiltonian; induced subgraph; forbidden subgraphs; Hamiltonian graph

UR - http://eudml.org/doc/270547

ER -

## References

top- [1] P. Bedrossian, Forbidden Subgraph and Minimum Degree Conditions for Hamiltonicity (Ph.D. Thesis, Memphis State University, 1991).
- [2] J. Brousek, Forbidden Triples and Hamiltonicity, Discrete Math. 251 (2002) 71-76, doi: 10.1016/S0012-365X(01)00326-0. Zbl1002.05044
- [3] G. Chartrand and L. Lesniak, Graphs & Digraphs (3rd Edition, Chapman & Hall, 1996).
- [4] R.J. Faudree and R.J. Gould, Characterizing Forbidden Pairs for Hamiltonian Properties, Discrete Math. 173 (1997) 45-60, doi: 10.1016/S0012-365X(96)00147-1. Zbl0879.05050
- [5] R.J. Faudree, R.J. Gould and M.S. Jacobson, Potential Forbidden Triples Implying Hamiltonicity: For Sufficiently Large Graphs, preprint. Zbl1143.05051
- [6] R.J. Faudree, R.J. Gould, M.S. Jacobson and L. Lesniak, Characterizing Forbidden Clawless Triples for Hamiltonian Graphs, Discrete Math. 249 (2002) 71-81, doi: 10.1016/S0012-365X(01)00235-7. Zbl0990.05091

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.