Contractible Non-Edges in 3-Connected Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909608601190400 |
|---|---|
| author | Kou, Shuai Qin, Chengfu Yang, Weihua Zhang, Mingzu |
| author_facet | Kou, Shuai Qin, Chengfu Yang, Weihua Zhang, Mingzu |
| contents | We call a pair of non-adjacent vertices in G a non-edge. Contraction of a non-edge {u, v} in G is the replacement of u and v with a single vertex z and then making all the vertices that are adjacent to u or v adjacent to z. A non-edge {u, v} is said to be contractible in a k-connected graph G, if the resulting graph after its contraction remains k-connected. Tsz Lung Chan characterized all 3-connected graphs (finite or infinite) that does not contain any contractible non-edges in 2019, and posed the problem of characterizing all 3-connected graphs that contain exactly one contractible non-edge. In this paper, we solve this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08185 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Contractible Non-Edges in 3-Connected Graphs Kou, Shuai Qin, Chengfu Yang, Weihua Zhang, Mingzu Combinatorics We call a pair of non-adjacent vertices in G a non-edge. Contraction of a non-edge {u, v} in G is the replacement of u and v with a single vertex z and then making all the vertices that are adjacent to u or v adjacent to z. A non-edge {u, v} is said to be contractible in a k-connected graph G, if the resulting graph after its contraction remains k-connected. Tsz Lung Chan characterized all 3-connected graphs (finite or infinite) that does not contain any contractible non-edges in 2019, and posed the problem of characterizing all 3-connected graphs that contain exactly one contractible non-edge. In this paper, we solve this problem. |
| title | Contractible Non-Edges in 3-Connected Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.08185 |