Extremal results for directed tree connectivity

DOI10.1007/S40840-021-01237-1zbMATH Open1485.05028arXiv2012.06698OpenAlexW4205348704MaRDI QIDQ2117576FDOQ2117576

Authors: Yanyan Li 

Publication date: 21 March 2022

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Abstract: For a digraph $D=(V(D),A(D))$, and a set $SsubseteqV(D)$ with $rinS$ and $|S|geq2$, an $(S,r)$-tree is an out-tree $T$ rooted at $r$ with $SsubseteqV(T)$. Two $(S,r)$-trees $T_1$ and $T_2$ are said to be arc-disjoint if $A(T_1)capA(T_2)=emptyset$. Two arc-disjoint $(S,r)$-trees $T_1$ and $T_2$ are said to be internally disjoint if $V(T_1)capV(T_2)=S$. Let $kapp{a}_{S,r}(D)$ and $lambd{a}_{S,r}(D)$ be the maximum number of internally disjoint and arc-disjoint $(S,r)$-trees in $D$, respectively. The generalized $k$-vertex-strong connectivity of $D$ is defined as ${\displaystyle }$kappa_k(D)= min {kappa_{S,r}(D)mid Ssubset V(D), |S|=k, rin S}.${\displaystyle }$ Similarly, the generalized $k$-arc-strong connectivity of $D$ is defined as ${\displaystyle }$lambda_k(D)= min {lambda_{S,r}(D)mid Ssubset V(D), |S|=k, rin S}.${\displaystyle }$ The generalized $k$-vertex-strong connectivity and generalized $k$-arc-strong connectivity are also called directed tree connectivity which could be seen as a generalization of classical connectivity of digraphs. A digraph $D=(V(D),A(D))$ is called minimally generalized $(k,ell)$-vertex (respectively, arc)-strongly connected if $kapp{a}_k(D)geqell$ (respectively, $lambd{a}_k(D)geqell$) but for any arc $einA(D)$, $kapp{a}_k(D-e)leqell-1$ (respectively, $lambd{a}_k(D-e)leqell-1$). In this paper, we study the minimally generalized $(k,ell)$-vertex (respectively, arc)-strongly connected digraphs. We compute the minimum and maximum sizes of these digraphs, and give characterizations of such digraphs for some pairs of $k$ and $ell$.

Full work available at URL: https://arxiv.org/abs/2012.06698

Recommendations

• Trees of extremal connectivity index
• On connectivities of tree graphs
• Extremum sum-connectivity index of trees and unicyclic graphs
• On trees with maximum algebraic connectivity
• Algebraic connectivity of trees with the maximum degree
• Trees and unicyclic graphs extremal with respect to sum connectivity index
• Extremal problems for directed graphs
• \(m\)-trees with the extremal general connectivity index
• On the extremal connectivity index of trees with \(k\) pendant vertices
• On the connectivity index of trees

zbMATH Keywords

out-branchingout-treedirected Steiner tree packingdirected tree connectivitygeneralized \(k\)-arc-strong connectivitygeneralized \(k\)-vertex-strong connectivity

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

• Digraphs
• A theorem on n-connected graphs
• Hardness and approximation results for packing Steiner trees
• Pendant tree-connectivity
• On the generalized (edge-)connectivity of graphs
• Tree connectivities of Cayley graphs on abelian groups with small degrees
• Generalized Connectivity of Graphs
• A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
• Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs)
• Note on Halin's theorem on minimally connected graphs
• On Vertices of outdegree n in minimally n‐connected digraphs
• Strong subgraph connectivity of digraphs
• Strong subgraph k‐connectivity

Cited In (2)

• Directed Steiner tree packing and directed tree connectivity
• A note on extremal results on directed acyclic graphs

This page was built for publication: Extremal results for directed tree connectivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117576)