Přejít k obsahu


Forbidden triples for hamiltonicity

Citace: [] BROUSEK, J. Forbidden triples for hamiltonicity . Discrete Mathematics, 2002, roč. 251, s. 71-76. ISSN: 0012-365X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Forbidden triples for hamiltonicity
Rok vydání: 2002
Autoři: Jan Brousek
Abstrakt CZ: V tomto článku jsou charakterizovány trojice zakázaných souvislých grafů $C,X,Y$ takové, že každý 2-souvislý graf bez $CXY$ je hamiltonovský. Tento výsledek společně s výsledky autorů Faudree, Gould, Jacobson a Lesniak plně characterizuje trojice zakázaných podgrafů, které jsou postačující podmínkou pro hamiltonicitu 2-souvislých grafů.
Abstrakt EN: In this paper we characterize all triples of connected graphs $C,X,Y$ (where $C$ is a claw) and such that every 2-connected $CXY$-free graph $G$ is hamiltonian. This result together with a previous result by Faudree, Gould, Jacobson and Lesniak give a full characterization of triples of forbidden subgraphs implying hamiltonicity of 2-connected graphs.
Klíčová slova

Zpět

Patička