Subgraphs, Closures and Hamiltonicity

Haitze J. Broersma; I. Schiermeyer

doi:10.1016/0166-218X(94)90092-2

Subgraphs, Closures and Hamiltonicity

Haitze J. Broersma
, I. Schiermeyer

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

718 Downloads (Pure)

Abstract

Closure theorems in hamiltonian graph theory are of the following type: Let G be a 2- connected graph and let u, v be two distinct nonadjacent vertices of G. If condition c(u,v) holds, then G is hamiltonian if and only if G + uv is hamiltonian. We discuss several results of this type in which u and v are vertices of a subgraph H of G on four vertices and c(u, v) is a condition on the neighborhoods of the vertices of H (in G). We also discuss corresponding sufficient conditions for hamiltonicity of G.

Original language	English
Pages (from-to)	39-46
Number of pages	8
Journal	Discrete applied mathematics
Volume	51
Issue number	1-2
DOIs	https://doi.org/10.1016/0166-218X(94)90092-2
Publication status	Published - 1994
Event	2nd Twente Workshop on Graphs and Combinatorial Optimization 1991 - University of Twente, Enschede, Netherlands Duration: 22 May 1991 → 24 May 1991

Access to Document

10.1016/0166-218X(94)90092-2Licence: Other

Broersma94subgraphsFinal published version, 500 KBLicence: Other

Cite this

@article{680e8a7a7ee04c20a00fe3038bc540be,

title = "Subgraphs, Closures and Hamiltonicity",

abstract = "Closure theorems in hamiltonian graph theory are of the following type: Let G be a 2- connected graph and let u, v be two distinct nonadjacent vertices of G. If condition c(u,v) holds, then G is hamiltonian if and only if G + uv is hamiltonian. We discuss several results of this type in which u and v are vertices of a subgraph H of G on four vertices and c(u, v) is a condition on the neighborhoods of the vertices of H (in G). We also discuss corresponding sufficient conditions for hamiltonicity of G.",

author = "Broersma, \{Haitze J.\} and I. Schiermeyer",

year = "1994",

doi = "10.1016/0166-218X(94)90092-2",

language = "English",

volume = "51",

pages = "39--46",

journal = "Discrete applied mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1-2",

note = "2nd Twente Workshop on Graphs and Combinatorial Optimization 1991 ; Conference date: 22-05-1991 Through 24-05-1991",

}

TY - JOUR

T1 - Subgraphs, Closures and Hamiltonicity

AU - Broersma, Haitze J.

AU - Schiermeyer, I.

PY - 1994

Y1 - 1994

N2 - Closure theorems in hamiltonian graph theory are of the following type: Let G be a 2- connected graph and let u, v be two distinct nonadjacent vertices of G. If condition c(u,v) holds, then G is hamiltonian if and only if G + uv is hamiltonian. We discuss several results of this type in which u and v are vertices of a subgraph H of G on four vertices and c(u, v) is a condition on the neighborhoods of the vertices of H (in G). We also discuss corresponding sufficient conditions for hamiltonicity of G.

AB - Closure theorems in hamiltonian graph theory are of the following type: Let G be a 2- connected graph and let u, v be two distinct nonadjacent vertices of G. If condition c(u,v) holds, then G is hamiltonian if and only if G + uv is hamiltonian. We discuss several results of this type in which u and v are vertices of a subgraph H of G on four vertices and c(u, v) is a condition on the neighborhoods of the vertices of H (in G). We also discuss corresponding sufficient conditions for hamiltonicity of G.

U2 - 10.1016/0166-218X(94)90092-2

DO - 10.1016/0166-218X(94)90092-2

M3 - Article

SN - 0166-218X

VL - 51

SP - 39

EP - 46

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 1-2

T2 - 2nd Twente Workshop on Graphs and Combinatorial Optimization 1991

Y2 - 22 May 1991 through 24 May 1991

ER -

Subgraphs, Closures and Hamiltonicity

Abstract

Access to Document

Fingerprint

Cite this