On the independence number in subcubic graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911147081334784 |
|---|---|
| author | Harant, Jochen Schiermeyer, Ingo |
| author_facet | Harant, Jochen Schiermeyer, Ingo |
| contents | For a connected subcubic graph $G\neq K_1$ let $V_i(G) = \{v \in V(G) ~|~ d_G(v)=i\}$ for $1 \leq i \leq 3.$ Given $c_1, c_2, c_ 3 \in \mathbb{R}^+$ and $ d \in \mathbb{R}$,
we show several results of type $α(G) \geq c_1|V_1(G)| + c_2|V_2(G)| + c_3|V_3(G)| - d.$ We also derive classes of graphs $G$ showing sharpness of these lower bounds on the independence number $α(G)$ of $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08367 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the independence number in subcubic graphs Harant, Jochen Schiermeyer, Ingo Combinatorics 05C35, 05C69 For a connected subcubic graph $G\neq K_1$ let $V_i(G) = \{v \in V(G) ~|~ d_G(v)=i\}$ for $1 \leq i \leq 3.$ Given $c_1, c_2, c_ 3 \in \mathbb{R}^+$ and $ d \in \mathbb{R}$, we show several results of type $α(G) \geq c_1|V_1(G)| + c_2|V_2(G)| + c_3|V_3(G)| - d.$ We also derive classes of graphs $G$ showing sharpness of these lower bounds on the independence number $α(G)$ of $G$. |
| title | On the independence number in subcubic graphs |
| topic | Combinatorics 05C35, 05C69 |
| url | https://arxiv.org/abs/2509.08367 |