DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


Authors:

Y. Sun

Yuefang Sun

Department of Mathematics
Shaoxing University
Zhejiang 312000, P. R. China

email: yuefangsun2013@163.com (Corresponding author)

Z. Jin

Zemin Jin

Department of Mathematics
Zhejiang Normal University
Zhejiang 321004, P. R. China

email: zeminjin@zjnu.cn

Title:

Minimally strong subgraph $(k,\ell)$-arc-connected digraphs

PDF

Source:

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:

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. J.A. Bondy and U.S.R. Murty, Graph Theory, GTM 244 (Springer, Berlin, 2008).
  7. 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
  8. M. Hager, Pendant tree-connectivity, J. Combin. Theory Ser. B 38 (1985) 179–189.
    https://doi.org/10.1016/0095-8956(85)90083-8
  9. X. Li and Y. Mao, Generalized Connectivity of Graphs (Springer, Switzerland, 2016).
    https://doi.org/10.1007/978-3-319-33828-6
  10. X. Li, Y. Mao and Y. Sun, On the generalized $($edge-$)$connectivity of graphs, Australas. J. Combin. 58 (2014) 304–319.
  11. Y. Sun and G. Gutin, Strong subgraph $k$-arc-connectivity (1805.01687v1).
  12. Y. Sun and G. Gutin, Strong subgraph connectivity of digraphs: A survey (1808.02740v1).
  13. 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
  14. 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
  15. 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