Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.09020 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916361059434496 |
|---|---|
| author | Balbuena, Camino Dankelmann, Peter |
| author_facet | Balbuena, Camino Dankelmann, Peter |
| contents | Let $G$ be a connected graph. The edge-connectivity of $G$, denoted by $λ(G)$, is the minimum number of edges whose removal renders $G$ disconnected. Let $δ(G)$ be the minimum degree of $G$. It is well-known that $λ(G) \leq δ(G)$, and graphs for which equality holds are said to be maximally edge-connected. The square $G^2$ of $G$ is the graph with the same vertex set as $G$, in which two vertices are adjacent if their distance is not more that $2$.
In this paper we present results on the edge-connectivity of the square of a graph. We show that if the minimum degree of a connected graph $G$ of order $n$ is at least $\lfloor \frac{n+2}{4}\rfloor$, then $G^2$ is maximally edge-connected, and this result is best possible. We also give lower bounds on $λ(G^2)$ for the case that $G^2$ is not maximally edge-connected: We prove that $λ(G^2) \geq κ(G)^2 + κ(G)$, where $κ(G)$ denotes the connectivity of $G$, i.e., the minimum number of vertices whose removal renders $G$ disconnected, and this bound is sharp. We further prove that $λ(G^2) \geq \frac{1}{2}λ(G)^{3/2} - \frac{1}{2} λ(G)$, and we construct an infinite family of graphs to show that the exponent $3/2$ of $λ(G)$ in this bound is best possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09020 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Edge-Connectivity of the Square of a Graph Balbuena, Camino Dankelmann, Peter Combinatorics 05C40 Let $G$ be a connected graph. The edge-connectivity of $G$, denoted by $λ(G)$, is the minimum number of edges whose removal renders $G$ disconnected. Let $δ(G)$ be the minimum degree of $G$. It is well-known that $λ(G) \leq δ(G)$, and graphs for which equality holds are said to be maximally edge-connected. The square $G^2$ of $G$ is the graph with the same vertex set as $G$, in which two vertices are adjacent if their distance is not more that $2$. In this paper we present results on the edge-connectivity of the square of a graph. We show that if the minimum degree of a connected graph $G$ of order $n$ is at least $\lfloor \frac{n+2}{4}\rfloor$, then $G^2$ is maximally edge-connected, and this result is best possible. We also give lower bounds on $λ(G^2)$ for the case that $G^2$ is not maximally edge-connected: We prove that $λ(G^2) \geq κ(G)^2 + κ(G)$, where $κ(G)$ denotes the connectivity of $G$, i.e., the minimum number of vertices whose removal renders $G$ disconnected, and this bound is sharp. We further prove that $λ(G^2) \geq \frac{1}{2}λ(G)^{3/2} - \frac{1}{2} λ(G)$, and we construct an infinite family of graphs to show that the exponent $3/2$ of $λ(G)$ in this bound is best possible. |
| title | On the Edge-Connectivity of the Square of a Graph |
| topic | Combinatorics 05C40 |
| url | https://arxiv.org/abs/2408.09020 |