On the generalized (edge-)connectivity of graphs

MaRDI QIDQ2876013zbMATH OpenFDO

Authors Yaping Mao, Yuefang Sun, Xueliang Li

Publication date 15 August 2014

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.0127, http://ajc.maths.uq.edu.au/pdf/58/ajc_v58_p304.pdf

zbMATH Keywords

\(k\)-connectivityNordhaus-Gaddum-type results

Mathematics Subject Classification ID

Connectivity (05C40)

Abstract: The generalized $k$-connectivity $kapp{a}_k(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. It is natural to introduce the concept of generalized $k$-edge-connectivity $lambd{a}_k(G)$. For general $k$, the generalized $k$-edge-connectivity of a complete graph is obtained. For $kgeq3$, tight upper and lower bounds of $kapp{a}_k(G)$ and $lambd{a}_k(G)$ are given for a connected graph $G$ of order $n$, that is, $1leqkapp{a}_k(G)leqn-lceilfrack2ceil$ and $1leqlambd{a}_k(G)leqn-lceilfrack2ceil$. Graphs of order $n$ such that $kapp{a}_k(G)=n-lceilfrack2ceil$ and $lambd{a}_k(G)=n-lceilfrack2ceil$ are characterized, respectively. Nordhaus-Gaddum-type results for the generalized $k$-connectivity are also obtained. For $k=3$, we study the relation between the edge-connectivity and the generalized 3-edge-connectivity of a graph. Upper and lower bounds of $lambd{a}_3(G)$ for a graph $G$ in terms of the edge-connectivity $lambda$ of $G$ are obtained, that is, $frac3lambda-24leqlambd{a}_3(G)leqlambda$, and two graph classes are given showing that the upper and lower bounds are tight. From these bounds, we obtain that $lambda(G)-1leqlambd{a}_3(G)leqlambda(G)$ if $G$ is a connected planar graph, and the relation between the generalized 3-connectivity and generalized 3-edge-connectivity of a graph and its line graph.

Recommendations

• Graphs with large generalized (edge-)connectivity
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• On the difference of two generalized connectivities of a graph
• Sharp upper bounds for generalized edge-connectivity of product graphs
• Sharp bounds for the generalized connectivity \(\kappa _{3}(G)\)

Cited in

(51)

• On computing a conditional edge-connectivity of a graph
• Generalized edge theorem
• On two generalized connectivities of graphs
• The generalized 3-connectivity of graph products
• Constructing edge-disjoint Steiner paths in lexicographic product networks
• Steiner tree packing number and tree connectivity
• The \(\lambda_3\)-connectivity and \(\kappa_3\)-connectivity of recursive circulants
• The generalized connectivity of the line graph and the total graph for the complete bipartite graph
• Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs
• Extremal results for directed tree connectivity
• Minimally strong subgraph \((k,\ell ) \)-arc-connected digraphs
• Bounding \(\ell\)-edge-connectivity in edge-connectivity
• Path 3-(edge-)connectivity of lexicographic product graphs
• The \(\kappa_k\)-connectivity of line graphs
• The 4-set tree connectivity of (n, k)-star networks
• The minimum size of a graph with given tree connectivity
• \(k\)-tree connectivity of line graphs
• The g-component connectivity of graphs
• Two lower bounds for generalized 3-connectivity of Cartesian product graphs
• Nordhaus-Gaddum-type results for the generalized edge-connectivity of graphs
• On the maximum and minimum sizes of a graph with given \(k\)-connectivity
• A sharp lower bound for the generalized 3-edge-connectivity of strong product graphs
• The minimal size of a graph with given generalized 3-edge-connectivity.
• Generalized 3-(edge)-connectivity for undirected double-loop networks
• Component connectivity of generalized Petersen graphs
• Generalized Connectivity of Graphs
• A generalization of an edge-connectivity theorem of Chartrand
• Separation of Cartesian products of graphs on several connected components by the removal of edges
• Sharp upper bounds for generalized edge-connectivity of product graphs
• Graphs with large generalized (edge-)connectivity
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• scientific article; zbMATH DE number 1747384 (Why is no real title available?)
• scientific article; zbMATH DE number 2097434 (Why is no real title available?)
• Generalized connectivity of some total graphs
• Some graph theoretical aspects of generalized truncations
• Tree connectivities of Cayley graphs on abelian groups with small degrees
• A solution to a conjecture on the generalized connectivity of graphs
• On the difference of two generalized connectivities of a graph
• Generalized 3-edge-connectivity of Cartesian product graphs.
• On extremal graphs with exactly one Steiner tree connecting any k vertices
• Constructing internally disjoint pendant Steiner trees in Cartesian product networks
• scientific article; zbMATH DE number 5203325 (Why is no real title available?)
• The generalized 3-connectivity of random graphs
• Directed Steiner tree packing and directed tree connectivity
• Note for the conjecture on the generalized 4-connectivity of total graphs of the complete bipartite graph
• On the minimum size of graphs with given generalized connectivity
• Bounds of generalized edge-connectivity of lexicographic product graphs
• Constructing disjoint Steiner trees in Sierpiński graphs
• Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs
• Path connectivity of \(k\)-generalized projectors
• On extremal graphs with at most internally disjoint Steiner trees connecting any n-1 vertices

This page was built for publication: On the generalized (edge-)connectivity of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2876013)