The $1$-nearly edge independence number of a graph
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917720121933824 |
|---|---|
| author | Shozi, Zekhaya B. |
| author_facet | Shozi, Zekhaya B. |
| contents | 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 $α'_k(G)$. In this paper we study $α_1'(G)$. In particular, we prove a tight lower (resp. upper) bound on $α_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08870 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The $1$-nearly edge independence number of a graph Shozi, Zekhaya B. Combinatorics 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 $α'_k(G)$. In this paper we study $α_1'(G)$. In particular, we prove a tight lower (resp. upper) bound on $α_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. |
| title | The $1$-nearly edge independence number of a graph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.08870 |