论文标题
强大的亚图2-弧形连接性和弧形的弧形连通性
Strong subgraph 2-arc-connectivity and arc-strong connectivity of Cartesian product of digraphs
论文作者
论文摘要
令$ d =（v，a）$是订单$ n $，$ s $ $ v $的$ v $ $ k $和$ 2 \ le K \ leq n $的digraph。如果$ s \ subseteq v（h）$，则强大的子图$ h $ $ d $ $ d $。如果$ a（d_1）\ cap a（d_2）= \ emptySet $，则一对$ s $ strong子图$ d_1 $和$ d_2 $被称为arc-disjoint。令$λ_s（d）$为$ d $中的Arc-disjoint $ s $ strong子图的最大数量。强大的子图$ k $ -arc-connectitive定义为$$λ_K（d）= \ min \ {λ_s（d）\ mid s \ subSeteq v（d），| s | = k \}。 在本文中，我们首先获得了两个digraphs $ g $和$ h $ cartesian产品的弧形连接性的公式，并为Xu and Yang（2006）获得的两个无向图获得的笛卡尔连接产品的范围概括了笛卡尔连接的公式。然后，我们研究笛卡尔产品$λ_2（g \ box h）$的强段2- arc-connctitive h \ right | ，λ\左（h \右）\左| g \右|，δ^{+} \ left（g \右）+δ^{+} {+} \ left（h \ oright），δ^{ - } \ left（g \ f \ w \右） λ_2（g）+λ_2（h）-1。$上的$λ_2（g \ box h）$的上限很清晰，是$λ（g \ box h）$的公式的简单推论。 $λ_2（g \ box h）$的下限是锋利的或几乎尖锐的，即与锋利的界限有所不同。我们还获得了$λ_2（g \ box h）$的精确值，其中$ g $和$ h $是某些Digraph家族的挖掘。
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 strong subgraph $H$ of $D$ is called an $S$-strong subgraph if $S\subseteq V(H)$. A pair of $S$-strong subgraphs $D_1$ and $D_2$ are said to be arc-disjoint if $A(D_1)\cap A(D_2)=\emptyset$. Let $λ_S(D)$ be the maximum number of arc-disjoint $S$-strong subgraphs in $D$. The strong subgraph $k$-arc-connectivity is defined as $$λ_k(D)=\min\{λ_S(D)\mid S\subseteq V(D), |S|=k\}.$$ The parameter $λ_k(D)$ can be seen as a generalization of classical edge-connectivity of undirected graphs. In this paper, we first obtain a formula for the arc-connectivity of Cartesian product $λ(G\Box H)$ of two digraphs $G$ and $H$ generalizing a formula for edge-connectivity of Cartesian product of two undirected graphs obtained by Xu and Yang (2006). Then we study the strong subgraph 2-arc-connectivity of Cartesian product $λ_2(G\Box H)$ and prove that $ \min\left \{ λ\left ( G \right ) \left | H \right | , λ\left ( H \right ) \left |G \right |,δ^{+ } \left ( G \right )+ δ^{+ } \left ( H \right ),δ^{- } \left ( G \right )+ δ^{- } \left ( H \right ) \right \}\geλ_2(G\Box H)\ge λ_2(G)+λ_2(H)-1.$ The upper bound for $λ_2(G\Box H)$ is sharp and is a simple corollary of the formula for $λ(G\Box H)$. The lower bound for $λ_2(G\Box H)$ is either sharp or almost sharp i.e. differs by 1 from the sharp bound. We also obtain exact values for $λ_2(G\Box H)$, where $G$ and $H$ are digraphs from some digraph families.
