New Invariants for Partitioning a Graph into 2-connected Subgraphs
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_ | 1866910365741219840 |
|---|---|
| author | Furuya, Michitaka Kashima, Masaki Ota, Katsuhiro |
| author_facet | Furuya, Michitaka Kashima, Masaki Ota, Katsuhiro |
| contents | A vertex partition in which every part induces a 2-connected subgraph is called a 2-proper partition. This concept was introduced by Ferrara et al. in 2013, and Borozan et al. gave the best possible minimum degree condition for the existence of a 2-proper partition in 2016. Later, in 2022, Chen et al. extended the result by showing a minimum degree sum condition for the existence of 2-proper partition. In this paper, we introduce two new invariants of graph, denoted by $σ^*(G)$ and $α^*(G)$. These two invariants are defined from degree sum on all independent sets with some property. We prove that if a graph $G$ satisfies $σ^*(G)\geq |V(G)|$, then with some exceptions, $G$ has a 2-proper partition with at most $α^*(G)$ parts. This result is best possible, and implies both of the results by Borozan et al. and by Chen et al.. Moreover, as a corollary of our result, we give a minimum degree product condition for the existence of a 2-proper partition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_08465 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | New Invariants for Partitioning a Graph into 2-connected Subgraphs Furuya, Michitaka Kashima, Masaki Ota, Katsuhiro Combinatorics 05C07 A vertex partition in which every part induces a 2-connected subgraph is called a 2-proper partition. This concept was introduced by Ferrara et al. in 2013, and Borozan et al. gave the best possible minimum degree condition for the existence of a 2-proper partition in 2016. Later, in 2022, Chen et al. extended the result by showing a minimum degree sum condition for the existence of 2-proper partition. In this paper, we introduce two new invariants of graph, denoted by $σ^*(G)$ and $α^*(G)$. These two invariants are defined from degree sum on all independent sets with some property. We prove that if a graph $G$ satisfies $σ^*(G)\geq |V(G)|$, then with some exceptions, $G$ has a 2-proper partition with at most $α^*(G)$ parts. This result is best possible, and implies both of the results by Borozan et al. and by Chen et al.. Moreover, as a corollary of our result, we give a minimum degree product condition for the existence of a 2-proper partition. |
| title | New Invariants for Partitioning a Graph into 2-connected Subgraphs |
| topic | Combinatorics 05C07 |
| url | https://arxiv.org/abs/2403.08465 |