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

(48)

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

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)