Polynomially determining spanning connectivity of locally connected line graphs
| Autor: | Sulin Song, Wei Xiong, Hong-Jian Lai, Yikang Xie, Mingquan Zhan |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Applied Mathematics
0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Disjoint sets 01 natural sciences Graph law.invention Combinatorics Integer 010201 computation theory & mathematics law Line graph Path (graph theory) Discrete Mathematics and Combinatorics Mathematics |
| Zdroj: | Discrete Applied Mathematics. 295:102-111 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2021.02.019 |
| Popis: | For a graph G , an integer s ≥ 0 and distinct vertices u , v ∈ 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 κ ∗ ( G ) is the largest integer s such that for any k with 0 ≤ k ≤ s and for any u , v ∈ V ( G ) with u ≠ v , G has a spanning ( k ; u , v ) -path-system. It is known that κ ∗ ( G ) ≤ κ ( G ) , and determining if κ ∗ ( G ) > 0 is an NP-complete problem. A graph G is maximally spanning connected if κ ∗ ( G ) = κ ( G ) . Let m s c ( G ) and s k ( G ) be the smallest integers m and m ′ such that L m ( G ) is maximally spanning connected and κ ∗ ( L m ′ ( G ) ) ≥ 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 m s c ( G ) and s 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect