More powerful closure operations on graphs

Yong-jin Zhu; Feng Tian; Xiao-tie Deng

doi:10.1016/0012-365X(91)90049-8

More powerful closure operations on graphs

Yong-jin Zhu
, Feng Tian
, Xiao-tie Deng

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

3 Citations (Scopus)

Abstract

Bondy and Chvátal have observed the following result: G=(V,E) is a simple graph of order n. If uv∉E and d(u)+d(v)≥n, then G is Hamiltonian iff G+uv is Hamiltonian. Thus, we can obtain a graph C_n(G), named the n-closure of G, from G by successively joining pairs of non-adjacent vertices whose degree sum is at least n. Therefore, G is Hamiltonian if C_n(G) is Hamiltonian. Moreover, Bondy and Chvátal [2] generalized this idea to several properties on G. In the paper, we present some more powerful closure operations that extend the idea of Bondy and Chvátal. © 1991.

Original language	English
Pages (from-to)	197-214
Journal	Discrete Mathematics
Volume	87
Issue number	2
DOIs	https://doi.org/10.1016/0012-365X(91)90049-8
Publication status	Published - 31 Jan 1991
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

project was supported by the National Natural Science Foundation of China.

Access Output

10.1016/0012-365X(91)90049-8

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{06609c83c3ab41a1974c191bb7c0889b,

title = "More powerful closure operations on graphs",

abstract = "Bondy and Chv{\'a}tal have observed the following result: G=(V,E) is a simple graph of order n. If uv∉E and d(u)+d(v)≥n, then G is Hamiltonian iff G+uv is Hamiltonian. Thus, we can obtain a graph Cn(G), named the n-closure of G, from G by successively joining pairs of non-adjacent vertices whose degree sum is at least n. Therefore, G is Hamiltonian if Cn(G) is Hamiltonian. Moreover, Bondy and Chv{\'a}tal [2] generalized this idea to several properties on G. In the paper, we present some more powerful closure operations that extend the idea of Bondy and Chv{\'a}tal. {\textcopyright} 1991.",

author = "Yong-jin Zhu and Feng Tian and Xiao-tie Deng",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1991",

month = jan,

day = "31",

doi = "10.1016/0012-365X(91)90049-8",

language = "English",

volume = "87",

pages = "197--214",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - More powerful closure operations on graphs

AU - Zhu, Yong-jin

AU - Tian, Feng

AU - Deng, Xiao-tie

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1991/1/31

Y1 - 1991/1/31

N2 - Bondy and Chvátal have observed the following result: G=(V,E) is a simple graph of order n. If uv∉E and d(u)+d(v)≥n, then G is Hamiltonian iff G+uv is Hamiltonian. Thus, we can obtain a graph Cn(G), named the n-closure of G, from G by successively joining pairs of non-adjacent vertices whose degree sum is at least n. Therefore, G is Hamiltonian if Cn(G) is Hamiltonian. Moreover, Bondy and Chvátal [2] generalized this idea to several properties on G. In the paper, we present some more powerful closure operations that extend the idea of Bondy and Chvátal. © 1991.

AB - Bondy and Chvátal have observed the following result: G=(V,E) is a simple graph of order n. If uv∉E and d(u)+d(v)≥n, then G is Hamiltonian iff G+uv is Hamiltonian. Thus, we can obtain a graph Cn(G), named the n-closure of G, from G by successively joining pairs of non-adjacent vertices whose degree sum is at least n. Therefore, G is Hamiltonian if Cn(G) is Hamiltonian. Moreover, Bondy and Chvátal [2] generalized this idea to several properties on G. In the paper, we present some more powerful closure operations that extend the idea of Bondy and Chvátal. © 1991.

UR - http://www.scopus.com/inward/record.url?scp=19544386497&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-19544386497&origin=recordpage

U2 - 10.1016/0012-365X(91)90049-8

DO - 10.1016/0012-365X(91)90049-8

M3 - RGC 21 - Publication in refereed journal

SN - 0012-365X

VL - 87

SP - 197

EP - 214

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 2

ER -

More powerful closure operations on graphs

Abstract

Bibliographical note

Funding

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this