Article in volume
Authors:
Title:
Minimally strong subgraph $(k,\ell)$-arc-connected digraphs
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 759-770
Received: 2018-09-14 , Revised: 2020-01-14 , Accepted: 2020-01-14 , Available online: 2020-02-07 , https://doi.org/10.7151/dmgt.2301
Abstract:
Let $D=(V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and
$2\le k\leq n$. A subdigraph $H$ of $D$ is called an $S$-strong subgraph if
$H$ is strong and $S\subseteq V(H)$. Two $S$-strong subgraphs $D_1$ and $D_2$
are said to be arc-disjoint if $A(D_1)\cap A(D_2)=\emptyset$. Let $\lambda_S(D)$
be the maximum number of arc-disjoint $S$-strong digraphs in $D$. The strong
subgraph $k$-arc-connectivity is defined as $\lambda_k(D)=\min\{\lambda_S(D)
| S\subseteq V, |S|=k\}.$ A digraph $D=(V, A)$ is called minimally strong
subgraph $(k,\ell)$-arc-connected if $\lambda_k(D)\geq \ell$ but for any arc
$e\in A$, $\lambda_k(D-e)\leq \ell-1$. Let $\mathfrak{G}(n,k,\ell)$ be the set
of all minimally strong subgraph $(k,\ell)$-arc-connected digraphs with order
$n$. We define $G(n,k,\ell)=\max\{|A(D)| | D\in \mathfrak{G}(n,k,\ell)\}$
and $g(n,k,\ell)=\min\{|A(D)| | D\in \mathfrak{G}(n,k,\ell)\}.$
In this paper, we study the minimally strong subgraph $(k,\ell)$-arc-connected
digraphs. We give a characterization of the minimally strong subgraph
$(3,n-2)$-arc-connected digraphs, and then give exact values and bounds for
the functions $g(n,k,\ell)$ and $G(n,k,\ell)$.
Keywords:
strong subgraph $k$-connectivity, strong subgraph, $k$-arc-connectivity, subdigraph packing
References:
- J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications, 2nd Edition (Springer, London, 2009).
https://doi.org/10.1007/978-1-84800-998-1 - J. Bang-Jensen and J. Huang, Decomposing locally semicomplete digraphs into strong spanning subdigraphs, J. Combin. Theory Ser. B 102 (2012) 701–714.
https://doi.org/10.1016/j.jctb.2011.09.001 - J. Bang-Jensen and M. Kriesell, Disjoint sub$($di$)$graphs in digraphs, Electron. Notes Discrete Math. 34 (2009) 179–183.
https://doi.org/10.1016/j.endm.2009.07.030 - J. Bang-Jensen and A. Yeo, Decomposing $k$-arc-strong tournaments into strong spanning subdigraphs, Combinatorica 24 (2004) 331–349.
https://doi.org/10.1007/s00493-004-0021-z - J. Bang-Jensen and A. Yeo, Arc-disjoint spanning sub$($di$)$graphs in digraphs, Theoret. Comput. Sci. 438 (2012) 48–54.
https://doi.org/10.1016/j.tcs.2012.03.003 - J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244 (Springer, Berlin, 2008).
- J. Cheriyan and M.R. Salavatipour, Hardness and approximation results for packing Steiner trees, Algorithmica 45 (2006) 21–43.
https://doi.org/10.1007/s00453-005-1188-4 - M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189.
https://doi.org/10.1016/0095-8956(85)90083-8 - X. Li and Y. Mao, Generalized Connectivity of Graphs (Springer, Switzerland, 2016).
https://doi.org/10.1007/978-3-319-33828-6 - X. Li, Y. Mao and Y. Sun, On the generalized $($edge-$)$connectivity of graphs, Australas. J. Combin. 58 (2014) 304–319.
- Y. Sun and G. Gutin, Strong subgraph $k$-arc-connectivity (1805.01687v1).
- Y. Sun and G. Gutin, Strong subgraph connectivity of digraphs: A survey (1808.02740v1).
- Y. Sun, G. Gutin and J. Ai, Arc-disjoint strong spanning subdigraphs in compositions and products of digraphs, Discrete Math. 342 (2019) 2297–2305.
https://doi.org/10.1016/j.disc.2019.05.003 - Y. Sun, G. Gutin, A. Yeo and X. Zhang, Strong subgraph $k$-connectivity, J. Graph Theory 92 (2019) 5–18.
https://doi.org/10.1002/jgt.22437 - T.W. Tillson, A Hamiltonian decomposition of $K^*_{2m}$, $2m \geq 8$, J. Combin. Theory Ser. B 29 (1980) 68–74.
https://doi.org/10.1016/0095-8956(80)90044-1
Close