On the generalized (edge-)connectivity of graphs

zbMATH Open1296.05107arXiv1112.0127MaRDI QIDQ2876013FDOQ2876013

Authors: Yaping Mao, Yuefang Sun, Xueliang Li 

Publication date: 15 August 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1112.0127

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)\)

zbMATH Keywords

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

Mathematics Subject Classification ID

Connectivity (05C40)

Cited In (48)

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

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)