Characterizations of Strength Extremal Graphs |
| |
Authors: | Xiaofeng Gu Hong-Jian Lai Ping Li Senmei Yao |
| |
Affiliation: | 1. Department of Mathematics and Computer Science, University of Wisconsin-Superior, Superior, WI, 54880, USA 2. Department of Mathematics, West Virginia University, Morgantown, WV, 26506, USA 3. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, Xinjiang, People’s Republic of China 4. Department of Mathematics, Beijing Jiaotong University, Beijing, 100044, People’s Republic of China 5. Department of Mathematics, School of Arts and Sciences, Marian University, Fond du Lac, WI, 54935, USA
|
| |
Abstract: | With graphs considered as natural models for many network design problems, edge connectivity κ′(G) and maximum number of edge-disjoint spanning trees τ(G) of a graph G have been used as measures for reliability and strength in communication networks modeled as graph G (see Cunningham, in J ACM 32:549–561, 1985; Matula, in Proceedings of 28th Symposium Foundations of Computer Science, pp 249–251, 1987, among others). Mader (Math Ann 191:21–28, 1971) and Matula (J Appl Math 22:459–480, 1972) introduced the maximum subgraph edge connectivity ({overline{kappa'}(G) = {rm max} {kappa'(H) : H {rm is} , {rm a} , {rm subgraph} , {rm of} G }}) . Motivated by their applications in network design and by the established inequalities $$overline{kappa'}(G) ge kappa'(G) ge tau(G),$$ we present the following in this paper: - For each integer k > 0, a characterization for graphs G with the property that ({overline{kappa'}(G) le k}) but for any edge e not in G, ({overline{kappa'}(G + e) ge k+1}) .
- For any integer n > 0, a characterization for graphs G with |V(G)| = n such that κ′(G) = τ(G) with |E(G)| minimized.
|
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|