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

Zheng-Jiang Xia, Hong-Jian Lai, Jian Lu, Zhen-Mu Hong · 2026

Read Characterization of the structure of k k -edge-maximal graphs by Zheng-Jiang Xia, Hong-Jian Lai, Jian Lu, Zhen-Mu Hong (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00719.txt.

Introduction

Xia and co-authors study a class of graphs at the edge of a strength limit in this 2026 maths paper. A graph's strength is the best edge-connectivity found in any of its subgraphs. A graph is k-edge-maximal when its strength stays at or below k. Yet adding any missing edge pushes some subgraph past k.

The team defines two new tools, the kernel and the closure of a graph, and works out how closure behaves. With those tools they give an exact test for when a graph is k-edge-maximal. Their test sharpens a known result from 1990. They also pin down which edge counts can occur for such graphs on n nodes. The count must match a set formula tied to a small whole-number parameter. Last, they describe the full shape of these graphs for each set edge count.

Catalog record

CREATORZheng-Jiang Xia, Hong-Jian Lai, Jian Lu, Zhen-Mu Hong
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE38 KB
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00719

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characterization of the structure of k k -edge-maximal graphs Zheng-Jiang Xia, Hong-Jian Lai, Jian Lu, Zhen-Mu Hong Abstract Abstract Let \kappa^{\prime}(G) be the edge-connectivity of the graph G . The strength of G , denoted by \overline{\kappa}^{\prime}(G) , is the maximum edge-connectivity of its subgraphs. A simple graph G is called k - edge-maximal if \overline{\kappa}^{\prime}(G)\leq k but for any edge e not in G , \overline{\kappa}^{\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. Keywords: Edge-connectivity; Strength; k -maximal graph; Closure AMS Subject Classification: 05C35, 05C40, 05C75 1 Introduction We consider finite and simple graphs in this paper. Undefined notation and terminologies will follow Bondy and Murty [ 2 ] . Let G^{c} denote the complement of a simple graph G . If X\subseteq E(G^{c}) , then G+X is the simple graph with vertex-set V(G) and edge-set E(G)\cup X . We will use G+e for G+\{e\} . Denote by H\subseteq G if H is a subgraph of G and by H\cong G if H is isomorphic to G . If X is a subset of V(G) or of E(G) , then G[X] denotes the subgraph of G induced by X . Let d_{G}(v) denote the degree of a vertex v of G and let \delta(G) denote the minimum degree of G . An edge-cut of a graph G is an edge subset whose removal increases the number of components of G . An edge-cut of size k is called a k - edge-cut . The graph G has edge-connectivity k if G contains a k -edge-cut but no smaller edge-cuts. The edge-connectivity of G is denoted by \kappa^{\prime}(G) . The graph G is k -edge-connected if \kappa^{\prime}(G)\geq k . Throughout this paper, \mathbb{N} denotes the set of all positive integers. For any k\in\mathbb{N} , we define \binom{k}{2}=\frac{1}{2}k(k-1) and so \binom{1}{2}=0 . The join of two graphs G_{1} and G_{2} , denoted by G_{1}\vee G_{2} , is a graph with V(G_{2}\vee G_{2})=V(G_{1})\cup V(G_{2}) and E(G_{1}\vee G_{2})=E(G_{1})\cup E(G_{2})\cup\{xy:x\in V(G_{1})\text{ and }y\in V(G_{2})\}. In [ 7 ] , Matula formally defined the strength of a graph G , denoted by \overline{\kappa}^{\prime}(G) , to be the maximum edge-connectivity of its subgraphs. More precisely, we have \overline{\kappa}^{\prime}(G)=\max_{H\subseteq G}\kappa^{\prime}(H), where the optimum are taken over all subgraphs H of G . Mader [ 6 ] investigated the extremal size of a simple graph with bounded strength. For a positive integer k , a simple graph G is called k -edge-maximal if \overline{\kappa}^{\prime}(G)\leq k but \overline{\kappa}^{\prime}(G+e)\geq k+1 , for any edge e\notin E(G) . The maximum subgraph edge-connectivity problem was earlier investigated by Mader [ 6 ] and Matula [ 7 ] , and has been intensively studied by many researchers, as found in [ 1 , 3 , 4 , 5 , 8 , 9 , 10 , 11 , 12 , 14 , 15 , 16 , 17 , 18 ] , among others. For more references, one can see the survey [ 13 ] and the references therein. For integers n and k with n\geq k+1 , we define F(n,k)=\max\{|E(G)|:G\text{ is a $k$-edge-maximal graph of order }n\}, f(n,k)=\min\{|E(G)|:G\text{ is a $k$-edge-maximal graph of order }n\}, \mathcal{G}(F;n,k)=\{G:G\text{ is a $k$-edge-maximal graph of order $n$ and }|E(G)|=F(n,k)\},\text{ and } \mathcal{G}(f;n,k)=\{G:G\text{ is a $k$-edge-maximal graph of order $n$ and }|E(G)|=f(n,k)\}. Mader [ 6 ] and Lai [ 3 ] determined the parameters F(n,k) and f(n,k) , respectively. Theorem 1.1 . Let k\geq 1 be an integer, and let G be a k -edge-maximal graph of order n . Each of the following holds. (i) (Mader [ 6 ] ) For n\geq k+1 , |E(G)|\leq F(n,k)=(n-1)k-\binom{k}{2} . (ii) (Lai [ 3 ] ) For n\geq k+2 , |E(G)|\geq f(n,k)=(n-1)k-\binom{k}{2}\left\lfloor\frac{n}{k+2}\right\rfloor . Let k be an integer and let H_{1} and H_{2} be two graphs with disjoint vertex sets and with \max\left\{|V(H_{1})|,|V(H_{2})|\right\}\geq k+1 . A k -edge-join of H_{1} and H_{2} is a simple graph obtained from the disjoint union of H_{1} and H_{2} by adding k new edges e_{1},e_{1},\ldots,e_{k} between H_{1} and H_{2} such that each e_{i} is incident to a vertex of V(H_{1}) and a vertex of V(H_{2}) . Denote by \left[H_{1},H_{2}\right]_{k} the set of all k -edge joins of H_{1} and H_{2} . For notational convenience, we also use [H_{1},H_{2}]_{k} to denote any graph in the family [H_{1},H_{2}]_{k} . The following theorem, published in [ 3 ] , contains a flaw. Theorem 1.2 (Lai [ 3 ] ) . Let k\geq 1 be an integer, let H_{1} be a k -edge-maximal graph and let H_{2} be either a K_{1} or a k -edge-maximal graph. Then all graphs in \left[H_{1},H_{2}\right]_{k} are k -edge-maximal. It is straightforward to verify that none of the graphs in [K_{3},K_{3}]_{2} are 2 -edge-maximal, which are counterexamples to Theorem 1.2 . This implies the k -edge-join of two k -edge-maximal graphs does not always result in a k -edge-maximal graph. A natural problem arises: under what conditions can the graph obtained by the k -edge-join operation be k -edge-maximal? This problem motivates the current research. In this paper, we establish the necessary and sufficient condition for [H_{1},H_{2}]_{k} to be k -edge-maximal, where H_{1} and H_{2} are arbitrary graphs. In order to present our main results, we first propose the concepts of kernel and closure of k -edge-maximal graphs. Definition 1.3 . Let G and H be two k -edge-maximal graphs, where H is a subgraph of G . The graph H is a k -kernel of G , if G can be obtained from H via some k -edge-join operations, or equivalently, H can be obtained from G by recursively deleting a k -edge-cut of a remaining component, in the sense that H is one of the components after deleting such a series of edge-cuts from G . When no confusion arises, we abbreviate a k -kernel as a kernel . Definition 1.4 . Let G be a k -edge-maximal graph and let H be a subgraph of G . A k -closure of H is a minimal k -kernel of G that contains H as a subgraph. When no confusion arises, we abbreviate a k -closure as a closure . Investigating the properties of the closures of k -edge-maximal graphs, we establish our main results as follows. Theorem 1.5 . Let H_{1} and H_{2} be two graphs, and let G\in[H_{1},H_{2}]_{k} be a graph of order n>k+1>2 . Denote V_{i} as the set of vertices in H_{i} that are incident with the edges joining H_{1} and H_{2} in G for each i\in\{1,2\} . Then G is k -edge-maximal if and only if one of the following holds: (i) H_{i}\cong K_{1} and H_{3-i} is a k -edge-maximal graph; (ii) Both H_{1} and H_{2} are k -edge-maximal graphs with

Read the complete text