Characterization of the structure of $k$-edge-maximal graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918533697372160 |
|---|---|
| author | Xia, Zheng-Jiang Lai, Hong-Jian Lu, Jian Hong, Zhen-Mu |
| author_facet | Xia, Zheng-Jiang Lai, Hong-Jian Lu, Jian Hong, Zhen-Mu |
| contents | Let $κ^{\prime}(G)$ be the edge-connectivity of the graph $G$. The \textit{strength} of $G$, denoted by $\overlineκ^{\prime}(G)$, is the maximum edge-connectivity of its subgraphs. A simple graph $G$ is called $k$-\textit{edge-maximal} if $\overlineκ^{\prime}(G) \leq k$ but for any edge $e$ not in $G$, $\overlineκ^{\prime}(G+e) \geq k+1$. In this paper, we propose the concepts of kernel and closure of a graph and discuss the properties of closure. Utilizing these properties, we present the necessary and sufficient condition for a graph to be $k$-edge-maximal, which refines the results in [J. Graph Theory 14 (1990) 187--197], and prove that there exists a $k$-edge-maximal graph of order $n$ with $m$ edges if and only if $m=(n-1)k-\binom{k}{2}r$, for some integer $r$ with $1\leq r\leq \left\lfloor \frac{n}{k+2}\right\rfloor$. Furthermore, we characterize the structure of $k$-edge-maximal graphs with a given number of edges. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_00719 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Characterization of the structure of $k$-edge-maximal graphs Xia, Zheng-Jiang Lai, Hong-Jian Lu, Jian Hong, Zhen-Mu Combinatorics 05C35, 05C40, 05C75 Let $κ^{\prime}(G)$ be the edge-connectivity of the graph $G$. The \textit{strength} of $G$, denoted by $\overlineκ^{\prime}(G)$, is the maximum edge-connectivity of its subgraphs. A simple graph $G$ is called $k$-\textit{edge-maximal} if $\overlineκ^{\prime}(G) \leq k$ but for any edge $e$ not in $G$, $\overlineκ^{\prime}(G+e) \geq k+1$. In this paper, we propose the concepts of kernel and closure of a graph and discuss the properties of closure. Utilizing these properties, we present the necessary and sufficient condition for a graph to be $k$-edge-maximal, which refines the results in [J. Graph Theory 14 (1990) 187--197], and prove that there exists a $k$-edge-maximal graph of order $n$ with $m$ edges if and only if $m=(n-1)k-\binom{k}{2}r$, for some integer $r$ with $1\leq r\leq \left\lfloor \frac{n}{k+2}\right\rfloor$. Furthermore, we characterize the structure of $k$-edge-maximal graphs with a given number of edges. |
| title | Characterization of the structure of $k$-edge-maximal graphs |
| topic | Combinatorics 05C35, 05C40, 05C75 |
| url | https://arxiv.org/abs/2606.00719 |