Uniquely $C_{4}^{+}$-saturated graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916541379903488 |
|---|---|
| author | Li, Yuying Xu, Kexiang Gerbner, Dániel Liu, Wenzhong |
| author_facet | Li, Yuying Xu, Kexiang Gerbner, Dániel Liu, Wenzhong |
| contents | A graph $G$ is uniquely $H$-saturated if it contains no copy of a graph $H$ as a subgraph, but adding any new edge into $G$ creates exactly one copy of $H$. Let $C_{4}^{+}$ be the diamond graph consisting of a $4$-cycle $C_{4}$ with one chord and $C_{3}^{*}$ be the graph consisting of a triangle with a pendant edge. In this paper we prove that a nontrivial uniquely $C_{4}^{+}$-saturated graph $G$ has girth $3$ or $4$. Further, $G$ has girth $4$ if and only if it is a strongly regular graph with special parameters. For $n>18k^{2}-24k+10$ with $k\geq2$, there are no uniquely $C_{4}^{+}$-saturated graphs on $n$ vertices with $k$ triangles. In particular, $C_{3}^{*}$ is the only nontrivial uniquely $C_{4}^{+}$-saturated graph with one triangle, and there are no uniquely $C_{4}^{+}$-saturated graphs with two, three or four triangles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_17962 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Uniquely $C_{4}^{+}$-saturated graphs Li, Yuying Xu, Kexiang Gerbner, Dániel Liu, Wenzhong Combinatorics 05C35, 05C07 A graph $G$ is uniquely $H$-saturated if it contains no copy of a graph $H$ as a subgraph, but adding any new edge into $G$ creates exactly one copy of $H$. Let $C_{4}^{+}$ be the diamond graph consisting of a $4$-cycle $C_{4}$ with one chord and $C_{3}^{*}$ be the graph consisting of a triangle with a pendant edge. In this paper we prove that a nontrivial uniquely $C_{4}^{+}$-saturated graph $G$ has girth $3$ or $4$. Further, $G$ has girth $4$ if and only if it is a strongly regular graph with special parameters. For $n>18k^{2}-24k+10$ with $k\geq2$, there are no uniquely $C_{4}^{+}$-saturated graphs on $n$ vertices with $k$ triangles. In particular, $C_{3}^{*}$ is the only nontrivial uniquely $C_{4}^{+}$-saturated graph with one triangle, and there are no uniquely $C_{4}^{+}$-saturated graphs with two, three or four triangles. |
| title | Uniquely $C_{4}^{+}$-saturated graphs |
| topic | Combinatorics 05C35, 05C07 |
| url | https://arxiv.org/abs/2412.17962 |