Closures and heavy pairs for hamiltonicity
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912037175558144 |
|---|---|
| author | Shang, Wangyi Broersma, Hajo Zhang, Shenggui Li, Binlong |
| author_facet | Shang, Wangyi Broersma, Hajo Zhang, Shenggui Li, Binlong |
| contents | We say that a graph $G$ on $n$ vertices is $\{H,F\}$-$o$-heavy if every induced subgraph of $G$ isomorphic to $H$ or $F$ contains two nonadjacent vertices with degree sum at least $n$. Generalizing earlier sufficient forbidden subgraph conditions for hamiltonicity, in 2012, Li, Ryjáček, Wang and Zhang determined all connected graphs $R$ and $S$ of order at least 3 other than $P_3$ such that every 2-connected $\{R,S\}$-$o$-heavy graph is hamiltonian. In particular, they showed that, up to symmetry, $R$ must be a claw and $S\in\{P_4,P_5,C_3,Z_1,Z_2,B,N,W\}$. In 2008, Čada extended Ryjáček's closure concept for claw-free graphs by introducing what we call the $c$-closure for claw-$o$-heavy graphs. We apply it here to characterize the structure of the $c$-closure of 2-connected $\{R,S\}$-$o$-heavy graphs, where $R$ and $S$ are as above. Our main results extend or generalize several earlier results on hamiltonicity involving forbidden or $o$-heavy subgraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_13491 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Closures and heavy pairs for hamiltonicity Shang, Wangyi Broersma, Hajo Zhang, Shenggui Li, Binlong Combinatorics We say that a graph $G$ on $n$ vertices is $\{H,F\}$-$o$-heavy if every induced subgraph of $G$ isomorphic to $H$ or $F$ contains two nonadjacent vertices with degree sum at least $n$. Generalizing earlier sufficient forbidden subgraph conditions for hamiltonicity, in 2012, Li, Ryjáček, Wang and Zhang determined all connected graphs $R$ and $S$ of order at least 3 other than $P_3$ such that every 2-connected $\{R,S\}$-$o$-heavy graph is hamiltonian. In particular, they showed that, up to symmetry, $R$ must be a claw and $S\in\{P_4,P_5,C_3,Z_1,Z_2,B,N,W\}$. In 2008, Čada extended Ryjáček's closure concept for claw-free graphs by introducing what we call the $c$-closure for claw-$o$-heavy graphs. We apply it here to characterize the structure of the $c$-closure of 2-connected $\{R,S\}$-$o$-heavy graphs, where $R$ and $S$ are as above. Our main results extend or generalize several earlier results on hamiltonicity involving forbidden or $o$-heavy subgraphs. |
| title | Closures and heavy pairs for hamiltonicity |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.13491 |