Geodesic
Hamiltonicities of Double Domination Critical and Stable Claw-Free Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 673-687.

Voir la notice de l'article provenant de la source Library of Science

A graph G with the double domination number γ_× 2 (G) = k is said to be k-γ_× 2-critical if γ_× 2 (G + uv) lt; k for any uv ∉E(G). On the other hand, a graph G with γ_× 2 (G) = k is said to be k-γ_× 2 ^+-stable if γ_× 2 (G + uv) = k for any uv ∉E(G) and is said to be k-γ_× 2^--stable if γ_× 2 (G − uv) = k for any uv ∈ E(G). The problem of interest is to determine whether or not 2-connected k-γ_× 2-critical graphs are Hamiltonian. In this paper, for k ≥ 4, we provide a 2-connected k-γ_× 2-critical graph which is non-Hamiltonian. We prove that all 2-connected k-γ_× 2-critical claw-free graphs are Hamiltonian when 2 ≤ k ≤ 5. We show that the condition claw-free when k = 4 is best possible. We further show that every 3-connected k-γ_× 2-critical claw-free graph is Hamiltonian when 2 ≤ k ≤ 7. We also investigate Hamiltonian properties of k-γ_× 2 ^+-stable graphs and k-γ_× 2 ^--stable graphs.
Keywords: double domination, critical, stable, Hamiltonian 
@article{DMGT_2019_39_3_a5,
     author = {Kaemawichanurat, Pawaton},
     title = {Hamiltonicities of {Double} {Domination} {Critical} and {Stable} {Claw-Free} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {673--687},
     publisher = {mathdoc},
     volume = {39},
     number = {3},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a5/}
}
TY  - JOUR
AU  - Kaemawichanurat, Pawaton
TI  - Hamiltonicities of Double Domination Critical and Stable Claw-Free Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 673
EP  - 687
VL  - 39
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a5/
LA  - en
ID  - DMGT_2019_39_3_a5
ER  - 
%0 Journal Article
%A Kaemawichanurat, Pawaton
%T Hamiltonicities of Double Domination Critical and Stable Claw-Free Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 673-687
%V 39
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a5/
%G en
%F DMGT_2019_39_3_a5
Kaemawichanurat, Pawaton. Hamiltonicities of Double Domination Critical and Stable Claw-Free Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 3, pp. 673-687. http://geodesic.mathdoc.fr/item/DMGT_2019_39_3_a5/

[1] S. Ao, G. MacGillivray and J. Simmons, Hamiltonian properties of independent domination critical graphs, J. Combin. Math. Combin. Comput. 85 (2013) 107–128.

[2] J. Brousek, Z. Ryjáček and O. Favaron, Forbidden subgraphs, Hamiltonicity and closure in claw-free graphs, Discrete Math. 196 (1999) 29–50. doi:10.1016/S0012-365X(98)00334-3

[3] V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 306 (2006) 910–917 (reprinted from Discrete Math. 5 (1973) 215–228). doi:10.1016/j.disc.2006.03.011

[4] M. Chellali and T.W. Haynes, Double domination stable graphs upon edge removal, Australas. J. Combin. 47 (2010) 157–164.

[5] O. Favaron, F. Tian and L. Zhang, Independence and Hamiltonicity in 3 -dominaion critical graphs, J. Graph Theory 25 (1997) 173–184. doi:10.1002/(SICI)1097-0118(199707)25:3h173::AID-JGT1i3.0.CO;2-I

[6] E. Flandrin, F. Tian, B. Wei and L. Zhang, Some properties of 3 -domination critical graphs, Discrete Math. 205 (1999) 65–76. doi:10.1016/S0012-365X(99)00038-2

[7] Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B 70 (1997) 217–224. doi:10.1006/jctb.1996.1732

[8] P. Kaemawichanurat and L. Caccetta, Hamiltonicity of domination critical claw-free graphs, J. Combin. Math. Combin. Comput. 103 (2017) 39–62.

[9] P. Kaemawichanurat, L. Caccetta and W. Ananchuen, Hamiltonicities of connected domination critical graphs, Ars Combin. 136 (2018) 137–151.

[10] J. Simmons, Closure Operations and Hamitonian Properties of Independent and Total Domination Critical Graphs, Ph.D. Thesis (University of Victoria, 2005).

[11] D.P. Sumner and P. Blitch, Domination critical graphs, J. Combin. Theory Ser. B 34 (1983) 65–76. doi:10.1016/0095-8956(83)90007-2

[12] D.W. Thacker, Double Domination Edge Critical Graph, Master Thesis (East Tennessee State University, 2006).

[13] F. Tian, B. Wei and L. Zhang, Hamiltonicity in 3 -domination critical graphs with α = δ + 2, Discrete Appl. Math. 92 (1999) 57–70. doi:10.1016/S0166-218X(98)00149-8

[14] H.C. Wang and L.Y. Kang, Matching properties in double domination edge critical graphs, Discrete Math. Algorithms Appl. 2 (2010) 151–160. doi:10.1142/S1793830910000541

[15] H.C. Wang and E.F. Shan, Some matching properties in 4-γ×2-critical graphs, Comput. Math. Appl. 59 (2010) 694–699. doi:10.1016/j.camwa.2009.10.024

[16] H.C. Wang, E.F. Shan and Y.C. Zhao, 3 -factor criticality in double domination edge critical graphs, Graphs Combin. 32 (2016) 1599–1610. doi:10.1007/s00373-015-1670-y

[17] E. Wojcicka, Hamiltonian properties of domination critical graphs, J. Graph Theory 14 (1990) 205–215. doi:10.1002/jgt.3190140209

[18] W. Xiong, H.J. Lai, X. Ma, K. Wang and M. Zhang, Hamilton cycles in 3 -connected claw-free and net-free graphs, Discrete Math. 313 (2013) 784–795. doi:10.1016/j.disc.2012.12.016

[19] Y. Yuansheng, Z. Chengye, L. Xiaohui, J. Yongsong and H. Xin, Some 3 -connected 4 -edge critical non-Hamiltonian graphs, J. Graph Theory 50 (2005) 316–320. doi:10.1002/jgt.20114