Geodesic
Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
Songling Shan1
1Illinois State University
The electronic journal of combinatorics, Tome 28 (2021) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $t>0$ be a real number and $G$ be a graph. We say $G$ is $t$-tough if for every cutset $S$ of $G$, the ratio of $|S|$ to the number of components of $G-S$ is at least $t$. Determining toughness is an NP-hard problem for arbitrary graphs. The Toughness Conjecture of Chv\'atal, stating that there exists a constant $t_0$ such that every $t_0$-tough graph with at least three vertices is hamiltonian, is still open in general. A graph is called $(P_2\cup P_3)$-free if it does not contain any induced subgraph isomorphic to $P_2\cup P_3$, the union of two vertex-disjoint paths of order 2 and 3, respectively. In this paper, we show that every 15-tough $(P_2\cup P_3)$-free graph with at least three vertices is hamiltonian.
DOI : 10.37236/8657
Classification : 05C45, 05C38
Mots-clés : toughness conjecture of Chvátal, \((P_2\cup P_3)\)-free graph

Songling Shan  1

1 Illinois State University 
@article{10_37236_8657,
     author = {Songling Shan},
     title = {Hamiltonian cycles in tough {\((P_2\cup} {P_3)\)-free} graphs},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {1},
     doi = {10.37236/8657},
     zbl = {1458.05134},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8657/}
}
TY  - JOUR
AU  - Songling Shan
TI  - Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8657/
DO  - 10.37236/8657
ID  - 10_37236_8657
ER  - 
%0 Journal Article
%A Songling Shan
%T Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8657/
%R 10.37236/8657
%F 10_37236_8657
Songling Shan. Hamiltonian cycles in tough \((P_2\cup P_3)\)-free graphs. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/8657

Cité par Sources :