Content area
Abstract
(ProQuest: ... denotes formulae and/or non-USASCII text omitted; see image)
Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, 2009 ). For a graph G and an integer s > 0 and for ... with u [not =] v, an (s; u, v)-path-system of G is a subgraph H consisting of s internally disjoint (u,v)-paths. A graph G is spanning s-connected if for any ... with u [not =] v, G has a spanning (s; u, v)-path-system. The spanning connectivity [kappa]*(G) of a graph G is the largest integer s such that G has a spanning (k; u, v)-path-system, for any integer k with 1 <= k <= s, and for any ... with u [not =] v. An edge counter-part of [kappa]*(G), defined as the supereulerian width of a graph G, has been investigated in Chen et al. (Supereulerian graphs with width s and s-collapsible graphs, 2012 ). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207-222, 1991 ) proved that if a graph G has 2 edge-disjoint spanning trees, and if L(G) is the line graph of G, then [kappa]*(L(G)) >= 2 if and only if [kappa](L(G)) >= 3. In this paper, we extend this result and prove that for any integer k >= 2, if G ^sub 0^, the core of G, has k edge-disjoint spanning trees, then [kappa]*(L(G)) >= k if and only if [kappa](L(G)) >= max{3, k}.[PUBLICATION ABSTRACT]