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

Abstract

Let ${\kappa }^{\prime }(G)$ be the edge-connectivity of the graph $G$. The \textit{strength} of $G$, denoted by ${\overline{\kappa }}^{\prime }(G)$, is the maximum edge-connectivity of its subgraphs. A simple graph $G$ is called $k$-\textit{edge-maximal} if ${\overline{\kappa }}^{\prime }(G)\le k$ but for any edge $e$ not in $G$, ${\overline{\kappa }}^{\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{}{}{0ex}{}{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.

arXiv comment17 pages, 2 figures