On the difference of two generalized connectivities of a graph

Yuefang Sun () and Xueliang Li ()
Additional contact information
Yuefang Sun: Shaoxing University
Xueliang Li: Nankai University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 1, No 20, 283-291

Abstract: Abstract The concept of k-connectivity $$\kappa '_{k}(G)$$ κ k ′ ( G ) of a graph G, introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. Another generalized connectivity of a graph G, named the generalized k-connectivity $$\kappa _{k}(G)$$ κ k ( G ) , mentioned by Hager in 1985, is a natural generalization of the path-version of the classical connectivity. In this paper, we get the lower and upper bounds for the difference of these two parameters by showing that for a connected graph G of order n, if $$\kappa '_k(G)\ne n-k+1$$ κ k ′ ( G ) ≠ n - k + 1 where $$k\ge 3$$ k ≥ 3 , then $$0\le \kappa '_k(G)-\kappa _k(G)\le n-k-1$$ 0 ≤ κ k ′ ( G ) - κ k ( G ) ≤ n - k - 1 ; otherwise, $$-\lfloor \frac{k}{2}\rfloor +1\le \kappa '_k(G)-\kappa _k(G)\le n-k$$ - ⌊ k 2 ⌋ + 1 ≤ κ k ′ ( G ) - κ k ( G ) ≤ n - k . Moreover, all of these bounds are sharp. Some specific study is focused for the case $$k=3$$ k = 3 . As results, we characterize the graphs with $$\kappa '_3(G)=\kappa _3(G)=t$$ κ 3 ′ ( G ) = κ 3 ( G ) = t for $$t\in \{1, n-3, n-2\}$$ t ∈ { 1 , n - 3 , n - 2 } , and give a necessary condition for $$\kappa '_3(G)=\kappa _3(G)$$ κ 3 ′ ( G ) = κ 3 ( G ) by showing that for a connected graph G of order n and size m, if $$\kappa '_3(G)=\kappa _3(G)=t$$ κ 3 ′ ( G ) = κ 3 ( G ) = t where $$1\le t\le n-3$$ 1 ≤ t ≤ n - 3 , then $$m\le {n-2\atopwithdelims ()2}+2t$$ m ≤ n - 2 2 + 2 t . Moreover, the unique extremal graph is given for the equality to hold.

Keywords: k-connectivity; Generalized k-connectivity; Tree connectivity; 05C40 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9956-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:1:d:10.1007_s10878-015-9956-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9956-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().