On Spanning Disjoint Paths in Line Graphs |
| |
Authors: | Ye Chen Zhi-Hong Chen Hong-Jian Lai Ping Li Erling Wei |
| |
Institution: | 1. Department of Mathematics, West Virginia University, Morgantown, WV, 26506, USA 2. Department of Computer Science, Butler University, Indianapolis, IN, 46208, USA 3. College of Mathematics and System Sciences, Xinjiang University, Urumqi, Xinjiang, 830046, People’s Republic of China 4. Department of Mathematics, Beijing Jiaotong University, Beijing, 100044, People’s Republic of China 5. Department of Mathematics, Renming University of China, Beijing, 100872, People’s Republic of China
|
| |
Abstract: | 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 ${u, v \in V(G)}$ with u ≠ 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 ${u, v \in V(G)}$ with u ≠ v, G has a spanning (s; u, v)-path-system. The spanning connectivity κ*(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 ${u, v \in V(G)}$ with u ≠ v. An edge counter-part of κ*(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 κ*(L(G)) ≥ 2 if and only if κ(L(G)) ≥ 3. In this paper, we extend this result and prove that for any integer k ≥ 2, if G 0, the core of G, has k edge-disjoint spanning trees, then κ*(L(G)) ≥ k if and only if κ(L(G)) ≥ max{3, k}. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|