Extremal results for directed tree connectivity

DOI10.1007/S40840-021-01237-1MaRDI QIDQ2117576zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 21 March 2022

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

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

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)

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$.

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

Cites work

• A Hamiltonian decomposition of \(K^*_{2m},2m\geq 8\)
• A theorem on n-connected graphs
• Digraphs
• Generalized Connectivity of Graphs
• Hardness and approximation results for packing Steiner trees
• 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
• On the generalized (edge-)connectivity of graphs
• Pendant tree-connectivity
• Strong subgraph k‐connectivity
• Strong subgraph connectivity of digraphs
• Tree connectivities of Cayley graphs on abelian groups with small degrees

Cited in

(4)

• Strong subgraph connectivity of digraphs
• Minimally strong subgraph \((k,\ell ) \)-arc-connected digraphs
• 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)