Characterization of the structure of $k$-edge-maximal graphs

Let ${\kappa }^{\mathrm{\prime }}(G)$ be the edge-connectivity of the graph $G$. The $\mathit{\text{strength}}$ of $G$, denoted by ${\bar{\kappa }}^{\mathrm{\prime }}(G)$, is the maximum edge-connectivity of its subgraphs. A simple graph $G$ is called $k$-$\mathit{\text{edge-maximal}}$ if ${\bar{\kappa }}^{\mathrm{\prime }}(G)\le k$ but for any edge $e$ not in $G$, ${\bar{\kappa }}^{\mathrm{\prime }}(G+e)\ge 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-\left(\genfrac{}{}{0px}{}{k}{2}\right)r$, for some integer $r$ with $1\le r\le \lfloor \frac{n}{k+2}\rfloor$. Furthermore, we characterize the structure of $k$-edge-maximal graphs with a given number of edges.