Geodesic
A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity
Shuya Chiba1 ; Michitaka Furuya2 ; Kenta Ozeki3 ; Masao Tsugaki2 ; Tomoki Yamashita4
1Kumamoto University
2Tokyo University of Science
3National Institute of Informatics
4Kindai University
The electronic journal of combinatorics, Tome 26 (2019) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

In [Graphs Combin. 24 (2008) 469–483], the third author and the fifth author conjectured that if $G$ is a $k$-connected graph such that $\sigma_{k+1}(G) \ge |V(G)|+\kappa(G)+(k-2)(\alpha(G)-1)$, then $G$ contains a Hamilton cycle, where $\sigma_{k+1}(G)$, $\kappa(G)$ and $\alpha(G)$ are the minimum degree sum of $k+1$ independent vertices, the connectivity and the independence number of $G$, respectively. In this paper, we settle this conjecture. The degree sum condition is best possible.
DOI : 10.37236/5480
Classification : 05C38, 05C45, 05C07, 05C40
Mots-clés : Hamilton cycle, degree sum condition

Shuya Chiba  1   ; Michitaka Furuya  2   ; Kenta Ozeki  3   ; Masao Tsugaki  2   ; Tomoki Yamashita  4

1 Kumamoto University
2 Tokyo University of Science
3 National Institute of Informatics
4 Kindai University 
@article{10_37236_5480,
     author = {Shuya Chiba and Michitaka Furuya and Kenta Ozeki and Masao Tsugaki and Tomoki Yamashita},
     title = {A degree sum condition on the order, the connectivity and the independence number for {Hamiltonicity}},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {4},
     doi = {10.37236/5480},
     zbl = {1431.05089},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5480/}
}
TY  - JOUR
AU  - Shuya Chiba
AU  - Michitaka Furuya
AU  - Kenta Ozeki
AU  - Masao Tsugaki
AU  - Tomoki Yamashita
TI  - A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5480/
DO  - 10.37236/5480
ID  - 10_37236_5480
ER  - 
%0 Journal Article
%A Shuya Chiba
%A Michitaka Furuya
%A Kenta Ozeki
%A Masao Tsugaki
%A Tomoki Yamashita
%T A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5480/
%R 10.37236/5480
%F 10_37236_5480
Shuya Chiba; Michitaka Furuya; Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita. A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity. The electronic journal of combinatorics, Tome 26 (2019) no. 4. doi: 10.37236/5480

Cité par Sources :