Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2504.01364 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908296142651392 |
|---|---|
| author | Berikkyzy, Zhanar Hogenson, Kirsten Kirsch, Rachel McDonald, Jessica |
| author_facet | Berikkyzy, Zhanar Hogenson, Kirsten Kirsch, Rachel McDonald, Jessica |
| contents | Erdős proved an upper bound on the number of edges in an $n$-vertex non-Hamiltonian graph with given minimum degree and showed sharpness via two members of a particular graph family. Füredi, Kostochka and Luo showed that these two graphs play the same role when ``number of edges'' is replaced by ``number of t-stars,'' and that two members of a more general graph family maximize the number of edges among non-$k$-edge-Hamiltonian graphs. In this paper we generalize their former result from Hamiltonicity to related properties (traceability, Hamiltonian-connectedness, $k$-edge Hamiltonicity, $k$-Hamiltonicity) and their latter result from edges to $t$-stars. We identify a family of extremal graphs for each property that is forbidden. This problem without the minimum degree condition was also open; here we conjecture a complete description of the extremal family for each property, and prove the characterization in some cases. Finally, using a different family of extremal graphs, we find the maximum number of $t$-stars in non-$k$-connected graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_01364 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximizing the number of stars in graphs with forbidden properties Berikkyzy, Zhanar Hogenson, Kirsten Kirsch, Rachel McDonald, Jessica Combinatorics 05C35, 05C45 Erdős proved an upper bound on the number of edges in an $n$-vertex non-Hamiltonian graph with given minimum degree and showed sharpness via two members of a particular graph family. Füredi, Kostochka and Luo showed that these two graphs play the same role when ``number of edges'' is replaced by ``number of t-stars,'' and that two members of a more general graph family maximize the number of edges among non-$k$-edge-Hamiltonian graphs. In this paper we generalize their former result from Hamiltonicity to related properties (traceability, Hamiltonian-connectedness, $k$-edge Hamiltonicity, $k$-Hamiltonicity) and their latter result from edges to $t$-stars. We identify a family of extremal graphs for each property that is forbidden. This problem without the minimum degree condition was also open; here we conjecture a complete description of the extremal family for each property, and prove the characterization in some cases. Finally, using a different family of extremal graphs, we find the maximum number of $t$-stars in non-$k$-connected graphs. |
| title | Maximizing the number of stars in graphs with forbidden properties |
| topic | Combinatorics 05C35, 05C45 |
| url | https://arxiv.org/abs/2504.01364 |