Geodesic
Hamiltonian Extendable Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 843-859.

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

A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the degree sequence for Hamiltonian extendable graphs with minimum number of edges. Besides, we completely characterize the pairs of forbidden subgraphs for 2-connected graphs to be Hamiltonian extendable.
Keywords: Hamiltonian extendable, forbidden subgraph 
@article{DMGT_2022_42_3_a10,
     author = {Yang, Xiaojing and Xiong, Liming},
     title = {Hamiltonian {Extendable} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {843--859},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a10/}
}
TY  - JOUR
AU  - Yang, Xiaojing
AU  - Xiong, Liming
TI  - Hamiltonian Extendable Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 843
EP  - 859
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a10/
LA  - en
ID  - DMGT_2022_42_3_a10
ER  - 
%0 Journal Article
%A Yang, Xiaojing
%A Xiong, Liming
%T Hamiltonian Extendable Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 843-859
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a10/
%G en
%F DMGT_2022_42_3_a10
Yang, Xiaojing; Xiong, Liming. Hamiltonian Extendable Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 843-859. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a10/

[1] B. Alspach and J. Liu, On the Hamilton connectivity of generalized Petersen graphs, Discrete Math. 309 (2009) 5461–5473. https://doi.org/10.1016/j.disc.2008.12.016

[2] Q. Bian, R.J. Gould, P. Horn, S. Janiszewski, S.L. Fleur and P. Wrayno, 3 -connected {K1,3, P9} -free graphs are Hamiltonian-connected, Graphs Combin. 30 (2014) 1099–1122. https://doi.org/10.1007/s00373-013-1344-6

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, Now York, 2008).

[4] H.J. Broersma, R.J. Faudree, A. Huck, H. Trommel and H.J. Veldman, Forbidden subgraphs that imply Hamiltonian-connectedness, J. Graph Theory 40 (2002) 104–119. https://doi.org/10.1002/jgt.10034

[5] V. Chvátal and P. Erdős, A note on Hamiltonian circuits, Discrete Math. 2 (1972) 111–113. https://doi.org/10.1016/0012-365X(72)90079-9

[6] M.-C. Costa, D. de Werra and C. Picouleau, Minimal graphs for matching extensions, Discrete Appl. Math. 234 (2018) 47–55. https://doi.org/10.1016/j.dam.2015.11.007

[7] M.-C. Costa, D. de Werra and C. Picouleau, Minimal graphs for 2 -factor extension, Discrete Appl. Math. 282 (2020) 65–79. https://doi.org/10.1016/j.dam.2019.11.022

[8] M.-C. Costa, D. de Werra and C. Picouleau, Extenseurs Hamiltoniens minimaux . https://uma.ensta-paris.fr/uma2/publis/show.html?id=1868

[9] R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for Hamiltonian properties, Discrete Math. 173 (1997) 45–60. https://doi.org/10.1016/S0012-365X(96)00147-1

[10] G. Liu and Q. Yu, Generalization of matching extensions in graphs, Discrete Math. 231 (2001) 311–320. https://doi.org/10.1016/S0012-365X(00)00328-9

[11] J.W. Moon, On a problem of Ore, Math. Gaz. 49 (1965) 40–41. https://doi.org/10.2307/3614234

[12] O. Ore, Hamiltonian-connected graphs, J. Math. Pures Appl. 42 (1963) 21–27.

[13] M.D. Plummer, Extending matchings in graphs: A survey, Discrete Math. 127 (1994) 277–292. https://doi.org/10.1016/0012-365X(92)00485-A

[14] R.B. Richter, Hamilton paths in generalized Petersen graphs, Discrete Math. 313 (2013) 1338–1341. https://doi.org/10.1016/j.disc.2013.02.021

[15] F.B. Shepherd, Hamiltonicity in claw-free graphs, J. Combin. Theory Ser. B 53 (1991) 173–194. https://doi.org/10.1016/0095-8956(91)90074-T