Forbidden subgraphs that imply Hamiltonian-connectedness

Haitze J. Broersma, R.J. Faudree, A. Huck, H. Trommel, H.J. Veldman

Research output: Book/ReportReportOther research output

51 Downloads (Pure)

Abstract

It is proven that if $G$ is a $3$-connected claw-free graph which is also $Z_3$-free (where $Z_3$ is a triangle with a path of length $3$ attached), $P_6$-free (where $P_6$ is a path with $6$ vertices) or $H_1$-free (where $H_1$ consists of two disjoint triangles connected by an edge), then $G$ is Hamiltonian-connected. Also, examples will be described that determine a finite family of graphs $\cal{L}$ such that if a 3-connected graph being claw-free and $L$-free implies $G$ is Hamiltonian-connected, then $L\in\cal{L}$.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 1999

Publication series

NameMemorandum / Faculty of Mathematical Sciences
PublisherDepartment of Applied Mathematics, University of Twente
No.1481
ISSN (Print)0169-2690

Keywords

  • MSC-05C45
  • MSC-05C35
  • EWI-3301
  • IR-65670
  • MSC-05C38

Cite this

Broersma, H. J., Faudree, R. J., Huck, A., Trommel, H., & Veldman, H. J. (1999). Forbidden subgraphs that imply Hamiltonian-connectedness. (Memorandum / Faculty of Mathematical Sciences; No. 1481). Enschede: University of Twente, Department of Applied Mathematics.
Broersma, Haitze J. ; Faudree, R.J. ; Huck, A. ; Trommel, H. ; Veldman, H.J. / Forbidden subgraphs that imply Hamiltonian-connectedness. Enschede : University of Twente, Department of Applied Mathematics, 1999. (Memorandum / Faculty of Mathematical Sciences; 1481).
@book{1a4506f74af742d98afb9b40a0431a12,
title = "Forbidden subgraphs that imply Hamiltonian-connectedness",
abstract = "It is proven that if $G$ is a $3$-connected claw-free graph which is also $Z_3$-free (where $Z_3$ is a triangle with a path of length $3$ attached), $P_6$-free (where $P_6$ is a path with $6$ vertices) or $H_1$-free (where $H_1$ consists of two disjoint triangles connected by an edge), then $G$ is Hamiltonian-connected. Also, examples will be described that determine a finite family of graphs $\cal{L}$ such that if a 3-connected graph being claw-free and $L$-free implies $G$ is Hamiltonian-connected, then $L\in\cal{L}$.",
keywords = "MSC-05C45, MSC-05C35, EWI-3301, IR-65670, MSC-05C38",
author = "Broersma, {Haitze J.} and R.J. Faudree and A. Huck and H. Trommel and H.J. Veldman",
note = "Imported from MEMORANDA",
year = "1999",
language = "Undefined",
series = "Memorandum / Faculty of Mathematical Sciences",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1481",

}

Broersma, HJ, Faudree, RJ, Huck, A, Trommel, H & Veldman, HJ 1999, Forbidden subgraphs that imply Hamiltonian-connectedness. Memorandum / Faculty of Mathematical Sciences, no. 1481, University of Twente, Department of Applied Mathematics, Enschede.

Forbidden subgraphs that imply Hamiltonian-connectedness. / Broersma, Haitze J.; Faudree, R.J.; Huck, A.; Trommel, H.; Veldman, H.J.

Enschede : University of Twente, Department of Applied Mathematics, 1999. (Memorandum / Faculty of Mathematical Sciences; No. 1481).

Research output: Book/ReportReportOther research output

TY - BOOK

T1 - Forbidden subgraphs that imply Hamiltonian-connectedness

AU - Broersma, Haitze J.

AU - Faudree, R.J.

AU - Huck, A.

AU - Trommel, H.

AU - Veldman, H.J.

N1 - Imported from MEMORANDA

PY - 1999

Y1 - 1999

N2 - It is proven that if $G$ is a $3$-connected claw-free graph which is also $Z_3$-free (where $Z_3$ is a triangle with a path of length $3$ attached), $P_6$-free (where $P_6$ is a path with $6$ vertices) or $H_1$-free (where $H_1$ consists of two disjoint triangles connected by an edge), then $G$ is Hamiltonian-connected. Also, examples will be described that determine a finite family of graphs $\cal{L}$ such that if a 3-connected graph being claw-free and $L$-free implies $G$ is Hamiltonian-connected, then $L\in\cal{L}$.

AB - It is proven that if $G$ is a $3$-connected claw-free graph which is also $Z_3$-free (where $Z_3$ is a triangle with a path of length $3$ attached), $P_6$-free (where $P_6$ is a path with $6$ vertices) or $H_1$-free (where $H_1$ consists of two disjoint triangles connected by an edge), then $G$ is Hamiltonian-connected. Also, examples will be described that determine a finite family of graphs $\cal{L}$ such that if a 3-connected graph being claw-free and $L$-free implies $G$ is Hamiltonian-connected, then $L\in\cal{L}$.

KW - MSC-05C45

KW - MSC-05C35

KW - EWI-3301

KW - IR-65670

KW - MSC-05C38

M3 - Report

T3 - Memorandum / Faculty of Mathematical Sciences

BT - Forbidden subgraphs that imply Hamiltonian-connectedness

PB - University of Twente, Department of Applied Mathematics

CY - Enschede

ER -

Broersma HJ, Faudree RJ, Huck A, Trommel H, Veldman HJ. Forbidden subgraphs that imply Hamiltonian-connectedness. Enschede: University of Twente, Department of Applied Mathematics, 1999. (Memorandum / Faculty of Mathematical Sciences; 1481).