LAUSR.org creates dashboard-style pages of related content for over 1.5 million academic articles. Sign Up to like articles & get recommendations!

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

Photo from wikipedia

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$$T1,T2,…,Tr in G such that $$V(T_i)\cap V(T_j)=S$$V(Ti)∩V(Tj)=S for any $$i,j\in \{1,2,\ldots ,r\}$$i,j∈{1,2,…,r}… Click to show full 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$$T1,T2,…,Tr in G such that $$V(T_i)\cap V(T_j)=S$$V(Ti)∩V(Tj)=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)and|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}$$K2,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}$$H1,…,Hk in $$\mathcal {B}$$B ($$k\ge 1$$k≥1) by applying some operations recursively.

Keywords: graphs; connectivity; graphs generalized; kappa; minimally connected; connected graphs

Journal Title: Journal of Combinatorial Optimization
Year Published: 2017

Link to full text (if available)


Share on Social Media:                               Sign Up to like & get
recommendations!

Related content

More Information              News              Social Media              Video              Recommended



                Click one of the above tabs to view related content.