1. Restricted arc-connectivity of unidirectional star graphs.
- Author
-
Zhao, Xiaojun, Deng, Qingying, and Wang, Zhiyi
- Subjects
- *
GRAPH connectivity , *DIRECTED graphs - Abstract
The restricted arc-connectivity is an effective assessment of the reliability of directed networks, which is an extended notion of arc-connectivity. Let D be a digraph. An arc set S of D is a restricted arc-cut of D if D − S has a strong connected component D ′ such that | V (D ′ ) | ≥ 2 and D − V (D ′ ) contains an arc. The digraph D is called λ ′ -connected if there exists a restricted arc-cut in D. The restricted arc-connectivity λ ′ (D) of a λ ′ -connected digraph D is the minimum cardinality over all restricted arc-cuts. We can get a unidirectional star graph by orienting the star graph with Day-Tripathi orientation. In this paper, we first show that the restricted arc-connectivity of the n -dimensional unidirectional star graph is n − 2 when n is odd and n − 3 when n is even for n ≥ 4. As a consequence, we prove that n -dimensional unidirectional star graph is super- λ when n ≥ 3 and n ≠ 4. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF