On minimally 2-connected graphs with generalized connectivity $$\kappa _{3}=2$$ κ 3 = 2

Shasha Li (), Wei Li (), Yongtang Shi () and Haina Sun ()
Additional contact information
Shasha Li: Zhejiang University
Wei Li: Guangxi Normal University
Yongtang Shi: Nankai University
Haina Sun: Zhejiang University

Journal of Combinatorial Optimization, 2017, vol. 34, issue 1, No 9, 164 pages

Abstract: Abstract For $$S\subseteq G$$ S ⊆ G , let $$\kappa (S)$$ κ ( S ) denote the maximum number r of edge-disjoint trees $$T_1, T_2, \ldots , T_r$$ T 1 , T 2 , … , T r in G such that $$V(T_i)\cap V(T_j)=S$$ V ( T i ) ∩ V ( T j ) = S for any $$i,j\in \{1,2,\ldots ,r\}$$ i , j ∈ { 1 , 2 , … , r } and $$i\ne j$$ i ≠ j . For every $$2\le k\le n$$ 2 ≤ k ≤ n , the k-connectivity of G, denoted by $$\kappa _k(G)$$ κ k ( G ) , is defined as $$\kappa _k(G)=\hbox {min}\{\kappa (S)| S\subseteq V(G)\ and\ |S|=k\}$$ κ k ( G ) = min { κ ( S ) | S ⊆ V ( G ) a n d | S | = k } . Clearly, $$\kappa _2(G)$$ κ 2 ( G ) corresponds to the traditional connectivity of G. In this paper, we focus on the structure of minimally 2-connected graphs with $$\kappa _{3}=2$$ κ 3 = 2 . Denote by $$\mathcal {H}$$ H the set of minimally 2-connected graphs with $$\kappa _{3}=2$$ κ 3 = 2 . Let $$\mathcal {B}\subseteq \mathcal {H}$$ B ⊆ H and every graph in $$\mathcal {B}$$ B is either $$K_{2,3}$$ K 2 , 3 or the graph obtained by subdividing each edge of a triangle-free 3-connected graph. We obtain that $$H\in \mathcal {H}$$ H ∈ H if and only if $$H\in \mathcal {B}$$ H ∈ B or H can be constructed from one or some graphs $$H_{1},\ldots ,H_{k}$$ H 1 , … , H k in $$\mathcal {B}$$ B ( $$k\ge 1$$ k ≥ 1 ) by applying some operations recursively.

Keywords: k-connectivity; Internally disjoint trees; Minimally 2-connected; Operation; 05C40; 05C05; 05C75 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0075-z 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:34:y:2017:i:1:d:10.1007_s10878-016-0075-z

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

DOI: 10.1007/s10878-016-0075-z

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 ().