On the Number of Connected Edge Cover Sets of Some Graph Families
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908852124909568 |
|---|---|
| author | Abdian, Ali Zeydi Alikhani, Saeid Zare, Mahsa |
| author_facet | Abdian, Ali Zeydi Alikhani, Saeid Zare, Mahsa |
| contents | Let $G=(V,E)$ be a simple connected graph. A connected edge cover of $G$ is a subset $S\subseteq E$ such that every vertex of $G$ is incident with at least one edge in $S$ and the subgraph induced by $S$ is connected. The connected edge cover polynomial of $G$ is defined as $E_c(G,x)=\sum_{i} e_c(G,i)x^i$, where $e_c(G,i)$ denotes the number of connected edge covers of $G$ with exactly $i$ edges. In this paper, we derive explicit formulas for both the connected edge cover polynomials and the total number of connected edge covers for several important graph families, including wheels, complete graphs $K_n$, complete bipartite graphs $K_{2,n}$, friendship graphs, and lollipop graphs. Each formula is accompanied by a combinatorial proof and verified by computational enumeration for small orders. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21660 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Number of Connected Edge Cover Sets of Some Graph Families Abdian, Ali Zeydi Alikhani, Saeid Zare, Mahsa Combinatorics 05C30 Let $G=(V,E)$ be a simple connected graph. A connected edge cover of $G$ is a subset $S\subseteq E$ such that every vertex of $G$ is incident with at least one edge in $S$ and the subgraph induced by $S$ is connected. The connected edge cover polynomial of $G$ is defined as $E_c(G,x)=\sum_{i} e_c(G,i)x^i$, where $e_c(G,i)$ denotes the number of connected edge covers of $G$ with exactly $i$ edges. In this paper, we derive explicit formulas for both the connected edge cover polynomials and the total number of connected edge covers for several important graph families, including wheels, complete graphs $K_n$, complete bipartite graphs $K_{2,n}$, friendship graphs, and lollipop graphs. Each formula is accompanied by a combinatorial proof and verified by computational enumeration for small orders. |
| title | On the Number of Connected Edge Cover Sets of Some Graph Families |
| topic | Combinatorics 05C30 |
| url | https://arxiv.org/abs/2602.21660 |