Article in volume
Authors:
Xiaojing Yang
School of Mathematics and Statistics
Beijing Key Laboratory on MCAACI
Beijing Institute of Technology
Beijing 100081, P.R. of China
email: yangxiaojing89@163.com
Liming Xiong
School of Mathematics and Statistics
Beijing Key Laboratory on MCAACI
Beijing Institute of Technology
Beijing 100081, P.R. of China
email: lmxiong@bit.edu.cn
Title:
Hamiltonian extendable graphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 843-859
Received: 2019-02-14 , Revised: 2020-02-11 , Accepted: 2020-02-11 , Available online: 2020-03-02 , https://doi.org/10.7151/dmgt.2308
Abstract:
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
References:
- 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 - Q. Bian, R.J. Gould, P. Horn, S. Janiszewski, S.L. Fleur and P. Wrayno, $3$-connected $\{K_{1,3}, P_9\}$-free graphs are Hamiltonian-connected, Graphs Combin. 30 (2014) 1099–1122.
https://doi.org/10.1007/s00373-013-1344-6 - J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, Now York, 2008).
- 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 - 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 - 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 - 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 - M.-C. Costa, D. de Werra and C. Picouleau, Extenseurs Hamiltoniens minimaux.
https://uma.ensta-paris.fr/uma2/publis/show.html?id=1868 - 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 - 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 - J.W. Moon, On a problem of Ore, Math. Gaz. 49 (1965) 40–41.
https://doi.org/10.2307/3614234 - O. Ore, Hamiltonian-connected graphs, J. Math. Pures Appl. 42 (1963) 21–27.
- 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 - 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 - 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
Close