Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\Gamma _n(S)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Γ</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> be the Cayley graph generated by a transposition generating tree G(S). Unidirectional Cayley graphs <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\overrightarrow{\Gamma }_n(S)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mover accent="true"> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">→</mo> </mover> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> are generalizations of Cayley graphs generated by transposition trees <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\Gamma _n(S)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi mathvariant="normal">Γ</mi> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> to digraphs. The super-<InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\lambda $</EquationSource> <EquationSource Format="MATHML"><math> <mi>λ</mi> </math></EquationSource> </InlineEquation> property of a digraph is an index for network reliability, which can be measured by the restricted arc connectivity quantitatively. Let D be a strong digraph. An arc subset F is a restricted arc cut of D if <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$D-F$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>-</mo> <mi>F</mi> </mrow> </math></EquationSource> </InlineEquation> has a strong component <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$D^\prime $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>D</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$|V(D^\prime )|\ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <msup> <mi>D</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$D-V(D')$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>D</mi> <mo>-</mo> <mi>V</mi> <mo stretchy="false">(</mo> <msup> <mi>D</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> contains an arc. D is called <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\lambda '$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>λ</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation>-connected if such a restricted arc cut exists. The restricted arc connectivity <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$\lambda '(D)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>λ</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>D</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> of a <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\lambda '$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>λ</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation>-connected digraph D is the minimum cardinality over all restricted arc cuts. In this paper, we prove that restricted arc connectivity of <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\overrightarrow{\Gamma }_n(S)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mover accent="true"> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">→</mo> </mover> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$n-2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> when n is odd and <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$n-3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> when n is even with <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$n\ge 5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>. As a consequence, we prove that <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$\overrightarrow{\Gamma }_n(S)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mover accent="true"> <mi mathvariant="normal">Γ</mi> <mo stretchy="false">→</mo> </mover> <mi>n</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is super-<InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\lambda $</EquationSource> <EquationSource Format="MATHML"><math> <mi>λ</mi> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$n\ge 5$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>5</mn> </mrow> </math></EquationSource> </InlineEquation>.

Restricted arc connectivity of unidirectional Cayley graphs generated by transposition trees

期刊论文
发表日期：

2026年2月15日

查看全文

Xiaohui Hua,
Rui Ma

摘要

Let $\Gamma _n(S)$ $Γ_{n} (S)$ be the Cayley graph generated by a transposition generating tree G(S). Unidirectional Cayley graphs $\overrightarrow{\Gamma }_n(S)$ ${\vec{Γ}}_{n} (S)$ are generalizations of Cayley graphs generated by transposition trees $\Gamma _n(S)$ $Γ_{n} (S)$ to digraphs. The super- $\lambda $ $λ$ property of a digraph is an index for network reliability, which can be measured by the restricted arc connectivity quantitatively. Let D be a strong digraph. An arc subset F is a restricted arc cut of D if $D-F$ $D - F$ has a strong component $D^\prime $ $D^{'}$ such that $|V(D^\prime )|\ge 2$ $| V (D^{'}) | \geq 2$ and $D-V(D')$ $D - V (D^{'})$ contains an arc. D is called $\lambda '$ $λ^{'}$ -connected if such a restricted arc cut exists. The restricted arc connectivity $\lambda '(D)$ $λ^{'} (D)$ of a $\lambda '$ $λ^{'}$ -connected digraph D is the minimum cardinality over all restricted arc cuts. In this paper, we prove that restricted arc connectivity of $\overrightarrow{\Gamma }_n(S)$ ${\vec{Γ}}_{n} (S)$ is $n-2$ $n - 2$ when n is odd and $n-3$ $n - 3$ when n is even with $n\ge 5$ $n \geq 5$ . As a consequence, we prove that $\overrightarrow{\Gamma }_n(S)$ ${\vec{Γ}}_{n} (S)$ is super- $\lambda $ $λ$ for $n\ge 5$ $n \geq 5$ .