Article in press
Authors:
Title:
A Chvátal-Erdős type theorem for path-connectivity
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-04-14 , Revised: 2023-03-03 , Accepted: 2023-03-03 , Available online: 2023-04-11 , https://doi.org/10.7151/dmgt.2493
Abstract:
For a graph $G$, let $\kappa(G)$ and $\alpha(G)$ be the connectivity and
independence number of $G$, respectively. A well-known theorem of Chvátal and
Erdős says that if $G$ is a graph of order $n$ with $\kappa(G)>\alpha(G)$,
then $G$ is Hamilton-connected. In this paper, we prove the following
Chvátal-Erdős type theorem: if $G$ is a $k$-connected graph, $k\geq 2$,
of order $n$ with independence number $\alpha$, then each pair of distinct
vertices of $G$ is joined by a Hamiltonian path or a path of length at least
$(k-1)\max\left\{\frac{n+\alpha-k}{\alpha}, \left\lfloor\frac{n+2\alpha-2k+1}
{\alpha}\right\rfloor\right\}$. Examples show that this result is best possible.
We also strength it in terms of subgraphs.
Keywords:
connectivity, independence number, Hamilton-connected, Chvátal-Erdős theorem
References:
- G.T. Chen, Z.Q. Hu and Y.P. Wu, Circumferences of k-connected graphs involving independence numbers, J. Graph Theory 68 (2011) 55–76.
https://doi.org/10.1002/jgt.20540 - 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 - J.L. Fouquet and J.L. Jolivet, Graphes hypohamiltoniens orientés, in: Problèmes combinatoires et thèorie des graphes, Proc. Coll. Orsay, 1976, (CNRS Publ., Paris 1978) 149–151.
- I. Fournier, Longest cycles in $2$-connected graphs of independence number $\alpha$, Ann. Discrete Math. 27 (1985) 201–204.
https://doi.org/10.1016/S0304-0208(08)73010-X - I. Fournier, Thesis (Ph.D. Thesis, University Paris-XI, Orsay, 1982).
- Z.Q. Hu and F.F. Song, Long cycles passing through \(\left\lfloor\frac{4k+1}3\right\rfloor\) vertices in k-connected graphs, J. Graph Theory 87 (2018) 374–393.
https://doi.org/10.1002/jgt.22164 - Z.Q. Hu, F. Tian and B. Wei, Long cycles through a linear forest, J. Combin. Theory Ser. B 82 (2001) 67–80.
https://doi.org/10.1006/jctb.2000.2022 - M. Kouider, Cycles in graphs with prescribed stability number and connectivity, J. Combin. Theory Ser. B 60 (1994) 315–318.
https://doi.org/10.1006/jctb.1994.1023 - Y. Manoussakis, Longest cycles in $3$-connected graphs with given independence number, Graphs Combin. 25 (2009) 377–384.
https://doi.org/10.1007/s00373-009-0846-8 - K. Menger, Zur allgemeinen Kurventheorie, Fund. Math. 10 (1927) 95–115.
https://doi.org/10.4064/fm-10-1-96-115 - S. O, D.B. West and H.H. Wu, Longest cycles in k-connected graphs with given independence number, J. Combin. Theory Ser. B 101 (2011) 480–485.
https://doi.org/10.1016/j.jctb.2011.02.005 - D.B. West, Introduction to Graph Theory (Prentice Hall Inc., Upper Saddle River, NJ, 1996).
- Y.P. Wu, On the Length of Longest Cycles and Codiameter of $k$-Connected Graphs (Ph.D Thesis, 2011).
Close