Characterizations of minimal graphs with equal edge connectivity and spanning tree packing number

arXiv1410.5486MaRDI QIDQ6255679FDOQ6255679

Authors: Xiaofeng Gu, Hong-Jian Lai, Ping Li, Senmei Yao 

Publication date: 20 October 2014

Abstract: With graphs considered as natural models for many network design problems, edge connectivity $kapp{a}^{\prime }(G)$ and maximum number of edge-disjoint spanning trees $au(G)$ of a graph $G$ have been used as measures for reliability and strength in communication networks modeled as graph $G$ (see cite{Cunn85, Matula87}, among others). Mader cite{Mader71} and Matula cite{Matula72} introduced the maximum subgraph edge connectivity $overlinekapp{a}^{\prime }(G)=maxkapp{a}^{\prime }(H):HmboxisasubgraphofG$. Motivated by their applications in network design and by the established inequalities [ overline{kappa'}(G)ge kappa'(G) ge au(G), ] we present the following in this paper: (i) For each integer $k>0$, a characterization for graphs $G$ with the property that $overlinekapp{a}^{\prime }(G)lek$ but for any edge $e$ not in $G$, $overlinekapp{a}^{\prime }(G+e)gek+1$. (ii) For any integer $n>0$, a characterization for graphs $G$ with $|V(G)|=n$ such that $kapp{a}^{\prime }(G)=au(G)$ with $|E(G)|$ minimized.

This page was built for publication: Characterizations of minimal graphs with equal edge connectivity and spanning tree packing number

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