- Tytuł:
- Minimally Strong Subgraph (k, ℓ)-Arc-Connected Digraphs
- Autorzy:
-
Sun, Yuefang
Jin, Zemin - Powiązania:
- https://bibliotekanauki.pl/articles/32304302.pdf
- Data publikacji:
- 2022-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
strong subgraph k -connectivity
strong subgraph k -arc-connectivity
subdigraph packing - Opis:
- Let $D = (V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and $ 2 \le k \le 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) = \text{min} \{ \lambda_S (D) | S \subseteq V, |S| = k \} $. A digraph $ D = (V, A) $ is called minimally strong subgraph $ (k, \mathcal{l})$-arc-connected if $ \lambda_k (D) \ge \mathcal{l} $ but for any arc $ e \in A $, $ \lambda_k(D − e) \le \mathcal{l} − 1 $. Let \( \mathfrak{G}(n, k, \mathscr{l} ) \) be the set of all minimally strong subgraph $ (k, \mathcal{l} )$-arc-connected digraphs with order $n$. We define $ G(n, k, \mathcal{l} ) = $ \( \max \{ |A(D)| \ | D \in \mathfrak{G} (n, k, \mathcal{l} ) \} \) and $ g(n, k, \mathcal{l} ) = $ \( \min \{ |A(D)| \ | D \in \mathfrak{G}(n, k, \mathcal{l} ) \} \). In this paper, we study the minimally strong subgraph $ (k, \mathcal{l} ) $-arc-connected digraphs. We give a characterization of the minimally strong sub-graph $ (3, n − 2) $-arc-connected digraphs, and then give exact values and bounds for the functions $ g(n, k, \mathcal{l} )$ and $ G(n, k, \mathcal{l} ) $.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 759-770
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł