Publications

Polynomially determining spanning connectivity of locally connected line graphs

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Discrete Applied Mathematics
Year: 2020
Abstract: Keywords Polynomial decision problem; Connectivity; Spanning connectivity; Maximally spanning connected; Locally connected graphs; Iterated line graph Abstract For a graph G, an integer s[greater than or equal to]0 and distinct vertices u,v[element of]V(G), an (s;u,v)-path-system of G is a subgraph H consisting of s internally disjoint (u,v)-paths. The spanning connectivity [kappa].sup.*(G) is the largest integer s such that for any k with 0[less than or equal to]k[less than or equal to]s and for any u,v[element of]V(G) with u[not equal to]v, G has a spanning (k;u,v)-path-system. It is known that [kappa].sup.*(G)[less than or equal to][kappa](G), and determining if [kappa].sup.*(G)>0 is an NP-complete problem. A graph G is maximally spanning connected if [kappa].sup.*(G)=[kappa](G). Let msc(G) and s.sub.k(G) be the smallest integers m and m.sup.' such that L.sup.m(G) is maximally spanning connected and [kappa].sup.*(L.sup.m.sup.'(G))[greater than or equal to]k, respectively. We show that every locally-connected line graph with connectivity at least 3 is maximally spanning connected, and that the spanning connectivity of a locally-connected line graph can be polynomially determined. As applications, we also determine best possible upper bounds for msc(G) and s.sub.k(G), and characterize the extremal graphs reaching the upper bounds. Consequently, former results in Asratian (1996), Sheng et al. (1999) and Xiong et al. (2014) are extended. Author Affiliation: (a) College of Mathematics and System Sciences, Xinjiang University, Urumqi Xinjiang, 830046, PR China (b) Department of Mathematics, West Virginia University, Morgantown, WV 26506, USA (c) Department of Mathematics, Millersville University, Millersville University of Pennsylvania, Millersville, PA 17551, USA * Corresponding author. Article History: Received 26 April 2020; Revised 7 December 2020; Accepted 4 February 2021 Byline: Wei Xiong [xingheng-1985@163.com] (a), Sulin Song [ss0148@mix.wvu.edu] (b), Yikang Xie [yx0010@mix.wvu.edu] (b), Mingquan Zhan [Mingquan.Zhan@millersville.com] (c), Hong-Jian Lai [hjlai@math.wvu.edu] (b,*)
Link: Polynomially determining spanning connectivity of locally connected line graphs