Hamiltonicity in 3-domination-critical graphs with alpha=delta+2
Tian, F; Wei, B; Zhang, L
AbstractLet delta, gamma, and alpha be respectively the minimum degree, the domination number and the independence number of a graph G. The graph G is 3-gamma-critical if gamma=3 and the addition of any edge decreases gamma by 1. It was conjectured that any connected 3-gamma-critical graph with delta greater than or equal to 2 is hamiltonian. In Fararon et al. (J. Graph Theory, 25 (1997) 173-184.) it was proved alpha less than or equal to delta + 2; and moreover, if alpha less than or equal to delta + 1, then G is hamiltonian. Here we show that if alpha=delta + 2 then G is hamiltonian, and thus prove the conjecture. We also give a class of 3-gamma-critical graphs with alpha=delta + 2. (C) 1999 Elsevier Science B.V. All rights reserved.
Keyworddomination-critical graphs Hamiltonicity longest cycle
WOS Research AreaMathematics
WOS SubjectMathematics, Applied
WOS IDWOS:000079426100003
Citation statistics
Document Type期刊论文
Corresponding AuthorTian, F
AffiliationAcad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
Recommended Citation
GB/T 7714
Tian, F,Wei, B,Zhang, L. Hamiltonicity in 3-domination-critical graphs with alpha=delta+2[J]. DISCRETE APPLIED MATHEMATICS,1999,92(1):57-70.
APA Tian, F,Wei, B,&Zhang, L.(1999).Hamiltonicity in 3-domination-critical graphs with alpha=delta+2.DISCRETE APPLIED MATHEMATICS,92(1),57-70.
MLA Tian, F,et al."Hamiltonicity in 3-domination-critical graphs with alpha=delta+2".DISCRETE APPLIED MATHEMATICS 92.1(1999):57-70.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Tian, F]'s Articles
[Wei, B]'s Articles
[Zhang, L]'s Articles
Baidu academic
Similar articles in Baidu academic
[Tian, F]'s Articles
[Wei, B]'s Articles
[Zhang, L]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Tian, F]'s Articles
[Wei, B]'s Articles
[Zhang, L]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.