The $1$-nearly edge independence number of a graph
| Autor: | Shozi, Zekhaya B. |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Let $G = (V(G), E(G))$ be a graph. The maximum cardinality of a set $M_k \subseteq E(G)$ such that $M_k$ contains exactly $k$-pairs of adjacent edges of $G$ is called the $k$-nearly edge independence number of $G$, and is denoted by $\alpha'_k(G)$. In this paper we study $\alpha_1'(G)$. In particular, we prove a tight lower (resp. upper) bound on $\alpha_1(G)$ if $G$ is a graph with given number of vertices. Furthermore, we present a characterisation of the general (resp. connected) graphs with given number of vertices and smallest $1$-nearly edge independence number. Lastly, we pose an open problem for further exploration of this study. Comment: 9 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|