The generalized connectivity of complete bipartite graphs.

MaRDI QIDQ4909681zbMATH OpenFDO

Authors Shasha Li, Wei Li, Xueliang Li

Publication date 21 March 2013

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

zbMATH Keywords

\(k\)-connectivitycomplete bipartite graphedge-disjoint spanning trees

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40)

Abstract: Let $G$ be a nontrivial connected graph of order $n$, and $k$ an integer with $2leqkleqn$. For a set $S$ of $k$ vertices of $G$, let $kappa(S)$ denote the maximum number $ell$ of edge-disjoint trees $T_1,T_2,\mathrm{...},T_{e}ll$ in $G$ such that $V(T_i)capV(T_j)=S$ for every pair $i,j$ of distinct integers with $1leqi,jleqell$. Chartrand et al. generalized the concept of connectivity as follows: The $k$-$connectivity$, denoted by $kapp{a}_k(G)$, of $G$ is defined by $kapp{a}_k(G)=$min$kappa(S)$, where the minimum is taken over all $k$-subsets $S$ of $V(G)$. Thus $kapp{a}_2(G)=kappa(G)$, where $kappa(G)$ is the connectivity of $G$. Moreover, $kapp{a}_n(G)$ is the maximum number of edge-disjoint spanning trees of $G$. This paper mainly focus on the $k$-connectivity of complete bipartite graphs $K_{a,b}$. First, we obtain the number of edge-disjoint spanning trees of $K_{a,b}$, which is $lfloorfracaba+b-1floor$, and specifically give the $lfloorfracaba+b-1floor$ edge-disjoint spanning trees. Then based on this result, we get the $k$-connectivity of $K_{a,b}$ for all $2leqkleqa+b$. Namely, if $k>b-a+2$ and $a-b+k$ is odd then $kapp{a}_k(K_{a,b})=fraca+b-k+12+lfloorfrac(a-b+k-1)(b-a+k-1)4(k-1)floor,$ if $k>b-a+2$ and $a-b+k$ is even then $kapp{a}_k(K_{a,b})=fraca+b-k2+lfloorfrac(a-b+k)(b-a+k)4(k-1)floor,$ and if $kleqb-a+2$ then $kapp{a}_k(K_{a,b})=a.$

Recommendations

• The generalized connectivity of complete equipartition 3-partite graphs
• The tree connectivity of regular complete bipartite graphs
• Internally disjoint trees in the line graph and total graph of the complete bipartite graph
• The minimal size of a graph with generalized connectivity _3=2
• Graphs with large generalized (edge-)connectivity

Cited in

(43)

• The generalized connectivity of alternating group graphs and \((n, k)\)-star graphs
• The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles
• A result on the 3-generalized connectivity of a graph and its line graph
• Two kinds of generalized connectivity of dual cubes
• The generalized 3-connectivity of graph products
• Note on the hardness of generalized connectivity
• The generalized 4-connectivity of exchanged hypercubes
• The generalized connectivity of the line graph and the total graph for the complete bipartite graph
• The generalized 3-connectivity of the Mycielskian of a graph
• The 3-path-connectivity of the hypercubes
• Generalized 4-connectivity of hierarchical star networks
• The generalized 4-connectivity of pancake graphs
• Internally disjoint trees in the line graph and total graph of the complete bipartite graph
• The \(\kappa_k\)-connectivity of line graphs
• The 4-set tree connectivity of (n, k)-star networks
• The generalized 4-connectivity of hierarchical cubic networks
• The reliability analysis based on the generalized connectivity in balanced hypercubes
• The generalized 3-connectivity of two kinds of regular networks
• Two lower bounds for generalized 3-connectivity of Cartesian product graphs
• On minimally 2-connected graphs with generalized connectivity \(\kappa_3=2\)
• The generalized connectivity of complete equipartition 3-partite graphs
• The (k,)-rainbow index of random graphs
• Reliability assessment of the divide-and-swap cube in terms of generalized connectivity
• The tree connectivity of regular complete bipartite graphs
• scientific article; zbMATH DE number 1390507 (Why is no real title available?)
• Generalized connectivity of some total graphs
• The generalized connectivity of data center networks
• A solution to a conjecture on the generalized connectivity of graphs
• On generalized 3-connectivity of the strong product of graphs
• The generalized connectivity of bubble-sort star graphs
• Note for the conjecture on the generalized 4-connectivity of total graphs of the complete bipartite graph
• The generalized 3-connectivity of burnt pancake graphs and godan graphs
• Connectivity, super connectivity and generalized 3-connectivity of folded divide-and-swap cubes
• The 4-set tree connectivity of hierarchical folded hypercube
• The generalized 4-connectivity of burnt pancake graphs
• The generalized 3-connectivity of star graphs and bubble-sort graphs
• The pendant-tree connectivity of some regular graphs
• The lower bounds of 4-tree connectivity of Cartesian product graphs
• Reliability analysis of godan graphs in terms of generalized 4-connectivity
• The generalized 3-connectivity of a family of regular networks
• The 4-set tree connectivity of folded hypercube
• The generalized 4-connectivity of a family of regular graphs
• On extremal graphs with at most internally disjoint Steiner trees connecting any n-1 vertices

This page was built for publication: The generalized connectivity of complete bipartite graphs.

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