ABSTRACT

Diagnosability of a multiprocessor system is one important study topic. In 2015, Zhang et al. proposed a new measure for fault diagnosis of the system, namely, g-extra diagnosability, which restrains that every fault-free component has at least $\left(g+1\right)$ fault-free nodes. As a favorable topology structure of interconnection networks, the n-dimensional alternating group graph AG_n has many good properties. In this paper, we give that the 2-extra diagnosability of AG_n is $6n-17$ for $n\ge 5$ under the PMC model and MM* model.

Keywords:

Interconnection Network, Diagnosability, Alternating Group Graph

1. Introduction

Many multiprocessor systems take interconnection networks (networks for short) as underlying topologies and a network is usually represented by a graph where nodes represent processors and links represent communication links between processors. We use graphs and networks interchangeably. For a multiprocessor system, study on the topological properties of its network is important. Furthermore, some processors may fail in the system, so processor fault identification plays an important role for reliable computing. The first step to deal with faults is to identify the faulty processors from the fault-free ones. The identification process is called the diagnosis of the system. A system is said to be t-diagnosable if all faulty processors can be identified without replacement, provided that the number of faults presented does not exceed t. The diagnosability of a system G is the maximum value of t such that G is t-diagnosable [1] [2] [3] . For a t-diagnosable system, Dahbura and Masson [1] proposed an algorithm with time complex $O\left(n^{2.5}\right)$ , which can effectively identify the set of faulty processors.

Several diagnosis models were proposed to identify the faulty processors. One major approach is the Preparata, Metze, and Chien’s (PMC) diagnosis model introduced by Preparata et al. [4] . The diagnosis of the system is achieved through two linked processors testing each other. Another major approach, namely the comparison diagnosis model (MM model), was proposed by Maeng and Malek [5] . In the MM model, to diagnose a system, a node sends the same task to two of its neighbors, and then compares their responses. In 2005, Lai et al. [3] introduced a restricted diagnosability of multiprocessor systems called conditional diagnosability. They consider the situation that any fault set cannot contain all the neighbors of any vertex in a system. In 2012, Peng et al. [6] proposed a measure for fault diagnosis of the system, namely, g-good-neighbor diagnosability (which is also called g-good-neighbor conditional diagnosability), which requires that every fault-free node has at least g fault-free neighbors. In [6] , they studied the g-good-neighbor diagnosability of the n-dimensional hypercube under the PMC model. In [7] , Wang and Han studied the g-good-neighbor diagnosability of the n-dimensional hypercube under the MM* model. Yuan et al. [8] and [9] studied that the g-good-neighbor diagnosability of the k-ary n-cube $\left(k\ge 3\right)$ under the PMC model and MM* model. The Cayley graph $C{\Gamma }_n$ generated by the transposition tree ${\Gamma }_n$ has recently received considerable attention. In [10] [11] , Wang et al. studied the g-good-neighbor diagnosability of $C{\Gamma }_n$ under the PMC model and MM* model for $g=1,2$ . In 2015, Zhang et al. [12] proposed a new measure for fault diagnosis of the system, namely, g-extra diagnosability, which restrains that every fault-free component has at least $\left(g+1\right)$ fault-free nodes. In [12] , they studied the g-extra diagnosability of the n-dimensional hypercube under the PMC model and MM* model. The n-dimensional bubble-sort star graph $B{S}_n$ has many good properties. In 2016, Wang et al. [13] studied the 2-extra diagnosability of $B{S}_n$ under the PMC model and MM* model.

As a favorable topology structure of interconnection networks, the n-dimensional alternating group graph $A{G}_n$ has many good properties. In this paper, we give that the 2-extra diagnosability of $A{G}_n$ is $6n-17$ for $n\ge 5$ under the PMC model and MM* model.

2. Preliminaries

In this section, some definitions and notations needed for our discussion, the alternating group graph, the PMC model and the MM* model are introduced.

2.1. Notations

A multiprocessor system is modeled as an undirected simple graph $G=\left(V\mathrm{,}E\right)$ , whose vertices (nodes) represent processors and edges (links) represent communication links. Given a nonempty vertex subset $V^{\prime }$ of V, the induced subgraph by $V^{\prime }$ in G, denoted by $G\left[V^{\prime }\right]$ , is a graph, whose vertex set is $V^{\prime }$ and the edge set is the set of all the edges of G with both endpoints in $V^{\prime }$ . The degree $d_G\left(v\right)$ of a vertex v is the number of edges incident with v. The minimum degree of a vertex in G is denoted by $\delta \left(G\right)$ . For any vertex v, we define the neighborhood $N_G\left(v\right)$ of v in G to be the set of vertices adjacent to v. u is called a neighbor vertex or a neighbor of v for $u\in N_G\left(v\right)$ . Let $S\subseteq V$ . We use $N_G\left(S\right)$ to denote the set ${\cup }_{v\in S}{N}_G\left(v\right)\backslash S$ . For neighborhoods and degrees, we will usually omit the subscript for the graph when no confusion arises. A graph G is said to be k-regular if for any vertex v, $d_G\left(v\right)=k$ . The connectivity $\kappa \left(G\right)$ of a graph G is the minimum number of vertices whose removal results in a disconnected graph or only one vertex left when G is complete. Let $F_1$ and $F_2$ be two distinct subsets of V, and let the symmetric difference $F_1\Delta F_2=\left(F_1\backslash F_2\right)\cup \left(F_2\backslash F_1\right)$ . Let $B_1\mathrm{,}\cdots \mathrm{,}{B}_k$ $\left(k\ge 2\right)$ be the components of $G-F_1$ . If $\left|V\left(B_1\right)\right|\le \cdots \le \left|V\left(B_k\right)\right|$ $\left(k\ge 2\right)$ , then $B_k$ is called the maximum component of $G-F_1$ . For graph-theoretical terminology and notation not defined here we follow [14] .

Let $G=\left(V\mathrm{,}E\right)$ . A fault set $F\subseteq V$ is called a g-good-neighbor faulty set if $\left|N\left(v\right)\cap \left(V\backslash F\right)\right|\ge g$ for every vertex v in $V\backslash F$ . A g-good-neighbor cut of G is a g-good-neighbor faulty set F such that $G-F$ is disconnected. The minimum cardinality of g-good-neighbor cuts is said to be the g-good-neighbor connectivity of G, denoted by ${\kappa }^{\left(g\right)}\left(G\right)$ . A fault set $F\subseteq V$ is called a g-extra faulty set if every component of $G-F$ has at least $\left(g+1\right)$ vertices. A g-extra cut of G is a g-extra faulty set F such that $G-F$ is disconnected. The minimum cardinality of g-extra cuts is said to be the g-extra connectivity of G, denoted by ${\tilde{\kappa }}^{\left(g\right)}\left(G\right)$ .

Proposition 2.1 [15] Let G be a connected graph. Then ${\tilde{\kappa }}^{\left(g\right)}\left(G\right)\le {\kappa }^{\left(g\right)}\left(G\right)$ .

Proposition 2.2 [15] Let G be a connected graph. Then ${\kappa }^{\left(1\right)}\left(G\right)={\tilde{\kappa }}^{\left(1\right)}\left(G\right)$ .

2.2. The PMC Model and the MM^* Model

Under the PMC model [5] [8] , to diagnose a system G, two adjacent nodes in G are capable to perform tests on each other. For two adjacent nodes u and v in $V\left(G\right)$ , the test performed by u on v is represented by the ordered pair $\left(u\mathrm{,}v\right)$ . The outcome of a test $\left(u\mathrm{,}v\right)$ is 1 (resp. 0) if u evaluate v as faulty (resp. fault-free). We assume that the testing result is reliable (resp. unreliable) if the node u is fault-free (resp. faulty). A test assignment T for G is a collection of tests for every adjacent pair of vertices. It can be modeled as a directed testing graph $T=\left(V\left(G\right)\mathrm{,}L\right)$ , where $\left(u\mathrm{,}v\right)\in L$ implies that u and v are adjacent in G. The collection of all test results for a test assignment T is called a syndrome. Formally, a syndrome is a function $\sigma \mathrm{<mo>\; :\; </mo>}L\mapsto \left\{\mathrm{0,1}\right\}$ . The set of all faulty processors in G is called a faulty set. This can be any subset of $V\left(G\right)$ . For a given syndrome s, a subset of vertices $F\subseteq V\left(G\right)$ is said to be consistent with s if syndrome s can be produced from the situation that, for any $\left(u\mathrm{,}v\right)\in L$ such that $u\in V\backslash F$ , $\sigma \left(u\mathrm{,}v\right)\mathrm{<mo>\; =\; </mo>1}$ if and only if $v\in F$ . This means that F is a possible set of faulty processors. Since a test outcome produced by a faulty processor is unreliable, a given set F of faulty vertices may produce a lot of different syndromes. On the other hand, different faulty sets may produce the same syndrome. Let $\sigma \left(F\right)$ denote the set of all syndromes which F is consistent with. Under the PMC model, two distinct sets $F_1$ and $F_2$ in $V\left(G\right)$ are said to be indistinguishable if $\sigma \left(F_1\right)\cap \sigma {\left(F\right)}_2\ne \varnothing$ , otherwise, $F_1$ and $F_2$ are said to be distinguishable. Besides, we say $\left(F_1\mathrm{,}{F}_2\right)$ is an indistinguishable pair if $\sigma \left(F_1\right)\cap \sigma {\left(F\right)}_2\ne \varnothing$ ; else, $\left(F_1\mathrm{,}{F}_2\right)$ is a distinguishable pair.

Using the MM model, the diagnosis is carried out by sending the same testing task to a pair of processors and comparing their responses. We always assume the output of a comparison performed by a faulty processor is unreliable. The comparison scheme of a system $G=\left(V,E\right)$ is modeled as a multigraph, denoted by $M\left(V\left(G\right)\mathrm{,}L\right)$ , where L is the labeled-edge set. A labeled edge ${\left(u\mathrm{,}v\right)}_w\in L$ represents a comparison in which two vertices u and v are compared by a vertex w, which implies $uw\mathrm{,}vw\in E\left(G\right)$ . The collection of all comparison results in $M\left(V\left(G\right)\mathrm{,}L\right)$ is called the syndrome, denoted by ${\sigma }^{\mathrm{<mo>\; *\; </mo>}}$ , of the diagnosis. If the comparison ${\left(u\mathrm{,}v\right)}_w$ disagrees, then ${\sigma }^{\mathrm{<mo>\; *\; </mo>}}\left({\left(u\mathrm{,}v\right)}_w\right)=1$ . otherwise, ${\sigma }^{*}\left({\left(u,v\right)}_w\right)=0$ . Hence, a syndrome is a function from L to $\left\{\mathrm{0,1}\right\}$ . The MM* model is a special case of the MM model. In the MM* model, all comparisons of G are in the comparison scheme of G, i.e., if $uw\mathrm{,}vw\in E\left(G\right)$ , then ${\left(u\mathrm{,}v\right)}_w\in L$ . Similar to the PMC model, we can define a subset of vertices $F\subseteq V\left(G\right)$ is consistent with a given syndrome ${\sigma }^{\mathrm{<mo>\; *\; </mo>}}$ and two distinct sets $F_1$ and $F_2$ in $V\left(G\right)$ are indistinguishable (resp. distinguishable) under the MM* model.

A system $G=\left(V,E\right)$ is g-good-neighbor t-diagnosable if $F_1$ and $F_2$ are distinguishable for each distinct pair of g-good-neighbor faulty subsets $F_1$ and $F_2$ of V with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$ . The g-good-neighbor diagnosability $t_g\left(G\right)$ of G is the maximum value of t such that G is g-good-neighbor t-diagnosable.

Proposition 2.3 ( [6] ) For any given system G, $t_g\left(G\right)\le t_{g^{\prime }}\left(G\right)$ if $g\le g^{\prime }$ .

In a system $G=\left(V,E\right)$ , a faulty set $F\subseteq V$ is called a conditional faulty set if it does not contain all the neighbor vertices of any vertex in G. A system G is conditional t-diagnosable if every two distinct conditional faulty subsets $F_1\mathrm{,}{F}_2\subseteq V$ with $\left|F_1\right|\le t\mathrm{,}\left|F_2\right|\le t$ , are distinguishable. The conditional diagnosability $t_c\left(G\right)$ of G is the maximum number of t such that G is conditional t-diagnosable. By [16] , $t_c\left(G\right)\ge t\left(G\right)$ .

Theorem 2.4 [10] For a system $G=\left(V\mathrm{,}E\right)$ , $t\left(G\right)=t_0\left(G\right)\le t_1\left(G\right)\le t_c\left(G\right)$ .

In [10] , Wang et al. proved that the 1-good-neighbor diagnosability of the Bubble-sort graph $B_n$ under the PMC model is $2n-3$ for $n\ge 4$ . In [17] , Zhou et al. proved the conditional diagnosability of $B_n$ is $4n-11$ for $n\ge 4$ under the PMC model. Therefore, $t_1\left(G\right)<t_c\left(G\right)$ when $n\ge 5$ and $t_1\left(G\right)=t_c\left(G\right)$ when $n=4$ .

In a system $G=\left(V\mathrm{,}E\right)$ , a faulty set $F\subseteq V$ is called a g-extra faulty set if every component of $G-F$ has more than g nodes. G is g-extra t -diagnosable if and only if for each pair of distinct faulty g-extra vertex subsets $F_1\mathrm{,}{F}_2\subseteq V\left(G\right)$ such that $\left|F_i\right|\le t$ , $F_1$ and $F_2$ are distinguishable. The g-extra diagnosability of G, denoted by ${\tilde{t}}_g\left(G\right)$ , is the maximum value of t such that G is g-extra t-diagnosable.

Proposition 2.5 [13] For any given system G, ${\tilde{t}}_g\left(G\right)\le {\tilde{t}}_{g^{\prime }}\left(G\right)$ if $g\le g^{\prime }$ .

Theorem 2.6 [13] For a system $G=\left(V\mathrm{,}E\right)$ , $t\left(G\right)={\tilde{t}}_0\left(G\right)\le {\tilde{t}}_g\left(G\right)\le t_g\left(G\right)$ .

Theorem 2.7 [13] For a system $G=\left(V\mathrm{,}E\right)$ , ${\tilde{t}}_1\left(G\right)=t_1\left(G\right)$ .

2.3. Alternating Group Graph

In this section, we give the definition and some properties of the alternating

group graph. In the permutation $\left(\begin{array}{c}12\cdots n\\ p_1{p}_2\cdots p_n\end{array}\right)$ , $i\to p_i$ . For the convenience, we denote the permutation $\left(\begin{array}{c}12\cdots n\\ p_1{p}_2\cdots p_n\end{array}\right)$ by $p_1{p}_2\cdots p_n$ . Every

permutation can be denoted by a product of cycles [18] . For example,

$\left(\begin{array}{c}123\\ 312\end{array}\right)=\left(132\right)$ . Specially, $\left(\begin{array}{c}12\cdots n\\ 12\cdots n\end{array}\right)=\left(1\right)$ . The product st of two

permutations is the composition function t followed by s, that is, $\left(12\right)\left(13\right)=\left(132\right)$ . For terminology and notation not defined here we follow [18] .

Let $\left[n\right]=\left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ , and let $S_n$ be the symmetric group on $\left[n\right]$ containing all permutations $p=p_1{p}_2\cdots p_n$ of $\left[n\right]$ . The alternating group $A_n$ is the subgroup of $S_n$ containing all even permutations. It is well known that $\left\{\left(12i\right)\mathrm{,}\left(1i2\right)\mathrm{,3}\le i\le n\right\}$ is a generating set for $A_n$ . The n-dimensional alternating group graph $A{G}_n$ is the graph with vertex set $V\left(A{G}_n\right)=A_n$ in which two vertices u, v are adjacent if and only if $u=v\left(12i\right)$ or $u=v\left(1i2\right)$ , $3\le i\le n$ . The identity element of $A_n$ is (1). The graphs $A{G}_3$ and $A{G}_4$ are depicted in Figure 1. It is easy to see from the definition that $A{G}_n$ is a $2\left(n-2\right)$ -regular graph on $n!/2$ vertices.

As a favorable topology structure of interconnection networks, alternating group graphs have been shown to have many desirable properties such as strong hierarchy, high connectivity, small diameter and average distance, etc. For details, see [19] for a comparison of the hypercube, the star graph and the alternating group graph.

Theorem 2.8 ( [19] ) $A{G}_n$ is vertex transitive and edge transitive.

Theorem 2.9 ( [20] ) ${\tilde{\kappa }}^{\left(2\right)}\left(A{G}_n\right)=6n-19$ for $n\ge 5$ .

We can partition $A{G}_n$ into n subgraphs $A{G}_n^1,A{G}_n^2\mathrm{,}\cdots \mathrm{,}A{G}_n^n$ , where every vertex $u=x_1{x}_2\cdots x_n\in V\left(A{G}_n\right)$ has a fixed integer i in the last position $x_n$ for $i\in \left[n\right]$ . It is obvious that $A{G}_n^i$ is isomorphic to $A{G}_{n-1}$ for $i\in \left[n\right]$ .

Proposition 2.10 [20] Let $A{G}_n^i$ be defined as above. Then there are $\left(n-2\right)!$ independent cross-edges between two different $A{G}_n^i$ ‘s.

Proposition 2.11 [8] $\kappa \left(A{G}_n\right)=\delta \left(A{G}_n\right)=2n-4$ for $n\ge 3$ . Furthermore, $A{G}_n$ is tightly hyper connected for $n\ge 4$ , that is to say, each minimum vertex cut creates exactly two components, one of which is an isolated vertex.

Proposition 2.12 ( [20] ) Let F be a vertex-cut of $A{G}_n$ ( $n\ge 5$ ) such that $\left|F\right|\le 6n-20$ . Then, $A{G}_n-F$ satisfies one of the following conditions:

1) $A{G}_n-F$ has two components, one of which is an isolated vertex or an

edge;

2) $A{G}_n-F$ has three components, two of which are isolated vertices.

Proposition 2.13 ( [20] ) Let F be a vertex-cut of $A{G}_n$ ( $n\ge 5$ ) such that $\left|F\right|\le 6n-19$ . Then, $A{G}_n-F$ satisfies one of the following conditions:

1) $A{G}_n-F$ has two components, one of which is an isolated vertex, an edge or a path of length 2;

2) $A{G}_n-F$ has three components, two of which are isolated vertices.

Proposition 2.14 [20] For $u\in V\left(A{G}_n^r\right)$ , $u^{+}\in V\left(A{G}_n^i\right)$ , $u^{-}\in V\left(A{G}_n^j\right)$ for $n\ge 4$ and $i\ne j$ .

Lemma 2.15 ( [21] ) Any 4-cycle in $A{G}_n$ has the form $u_1{u}_2{u}_3{u}_4{u}_1$ where $u_2=u_1\left(12i\right)$ , $u_3=u_2\left(12j\right)$ , $u_4=u_3\left(12i\right)$ , $u_1=u_4\left(12j\right)$ for some $i\mathrm{,}j$ with $i\ne j$ .

3. The 2-Extra Diagnosability of Alternating Group Graphs under the PMC Model

In this section, we will give 2-extra diagnosability of alternating group graph networks under the PMC model.

Theorem 3.1 ( [8] ) A system $G=\left(V\mathrm{,}E\right)$ is g-extra t-diagnosable under the PMC model if and only if there is an edge $uv\in E$ with $u\in V\backslash \left(F_1\cup F_2\right)$ and $v\in F_1\Delta F_2$ for each distinct pair of g-extra faulty subsets $F_1$ and $F_2$ of V with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$ .

Lemma 3.2 Let $A=\left\{\left(1\right),\left(132\right),\left(142\right)\right\}$ , $n\ge 4$ and let $F_1=N_{A{G}_n}\left(A\right)$ , $F_2=A\cup N_{A{G}_n}\left(A\right)$ . Then $\left|F_1\right|=6n-19$ , $\left|F_2\right|=6n-16$ , $F_1$ is a 2-extra cut of $A{G}_n$ , and $A{G}_n-F_1$ has two components $A{G}_n-F_2$ and $A{G}_n\left[A\right]$ .

Proof. By $A=\left\{\left(1\right),\left(132\right),\left(142\right)\right\}$ , we have that $A{G}_n\left[A\right]$ is a path $\left(132\right)$ , $\left(1\right)$ , $\left(142\right)$ . Suppose $n=4$ . Then $\left|N\left(A\right)\right|=\left|\left\{2314,4132,1423,4321,3241\right\}\right|=5$ (see Figure 1). We prove this lemma (part) by induction on n. The result holds for $n=4$ . Assume $n\ge 5$ and the result holds for $A{G}_{n-1}$ , i.e., $\left|F_1\right|=6\left(n-1\right)-19=6n-25$ . We decompose $A{G}_n$ into n sub-alternating group graph, $A{G}_n^1\mathrm{,}A{G}_n^2\mathrm{,}\cdots \mathrm{,}A{G}_n^n$ , where each $A{G}_n^i$ has a fixed i in the last position of the label strings which represents the vertices and is isomorphic to $A{G}_{n-1}$ . Note

that $\left|N\left(A\right)\cap V\left(A{G}_n^1\right)\right|=\left|\left\{\left(12n\right)\mathrm{<mo\; stretchy="false">\; )\; </mo>,}\left(1n\right)\left(23\right)\mathrm{,}\left(1n\right)\left(24\right)\right\}\right|=3$ , $\left|N\left(A\right)\cap V\left(A{G}_n^2\right)\right|=\left|\left\{\left(1n2\right)\right\}\right|=1$ , $\left|N\left(A\right)\cap V\left(A{G}_n^3\right)\right|=\left|\left\{\left(2n3\right)\right\}\right|=1$ , $\left|N\left(A\right)\cap V\left(A{G}_n^4\right)\right|=\left|\left\{\left(2n4\right)\right\}\right|=1$ and $\left|N\left(A\right)\cap V\left(A{G}_n^i\right)\right|=0$ for $i=5,\cdots ,n-1$ . Therefore, $\left|F_1\right|=6n-25+6=6n-19$ and $\left|F_2\right|=6n-16$ .

Let $F_i^{\mathrm{<mo>\; *\; </mo>}}=F_1\cap V\left(A{G}_n^i\right)$ for $i\in \left\{\mathrm{1,2,}\cdots \mathrm{,}n\right\}$ . Note that

$A{G}_4-F_2=1342,2143,4213,3412,1342$ is a 4-cycle. We prove this lemma (part) by induction on n. The result holds for $n=4$ . Assume $n\ge 5$ and the result holds for $A{G}_{n-1}$ , i.e., $F_1$ is a 2-extra cut of $A{G}_{n-1}$ , and $A{G}_{n-1}-F_1$ has two components $A{G}_{n-1}-F_2$ and $A{G}_{n-1}\left[A\right]$ . Since $\left|N\left(A\right)\cap V\left(A{G}_n^1\right)\right|=\left|\left\{\left(12n\right)\mathrm{,}\left(1n\right)\left(23\right)\mathrm{,}\left(1n\right)\left(24\right)\right\}\right|=3$ , $\left|N\left(A\right)\cap V\left(A{G}_n^2\right)\right|=\left|\left\{\left(1n2\right)\right\}\right|=1$ , $\left|N\left(A\right)\cap V\left(A{G}_n^3\right)\right|=\left|\left\{\left(2n3\right)\right\}\right|=1$ , $\left|N\left(A\right)\cap V\left(A{G}_n^4\right)\right|=\left|\left\{\left(2n4\right)\right\}\right|=1$ and $\left|N\left(A\right)\cap V\left(A{G}_n^i\right)\right|=0$ for $i=5,\cdots ,n-1$ , by Propositions 2.10 and 2.11, $A{G}_n\left[V\left(A{G}_n^2-F_2^{\mathrm{<mo>\; *\; </mo>}}\right)\cup V\left(A{G}_n^3-F_3^{\mathrm{<mo>\; *\; </mo>}}\right)\cup \cdots \cup V\left(A{G}_n^n-F_n^{\mathrm{<mo>\; *\; </mo>}}\right)\right]$ is connected for $n\ge 5$ . By inductive hypothesis, $A{G}_{n-1}-F_2$ is connected. Since $F_i^{\mathrm{<mo>\; *\; </mo>}}=F_1\cap V\left(A{G}_n^i\right)$ , by Proposition 2.14, $\left(N\left(x\right)\cap V\left(A{G}_n^i\right)\right)\cap F_i^{\mathrm{<mo>\; *\; </mo>}}=\varnothing$ for $x\in V\left(A{G}_{n-1}-F_2\right)$ . Therefore, $A{G}_n\left[V\left(A{G}_n^1-F_2\right)\cup V\left(A{G}_n^2-F_2^{\mathrm{<mo>\; *\; </mo>}}\right)\cup V\left(A{G}_n^3-F_3^{\mathrm{<mo>\; *\; </mo>}}\right)\cup \cdots \cup V\left(A{G}_n^n-F_n^{\mathrm{<mo>\; *\; </mo>}}\right)\right]=A{G}_n-F_2$ is connected. Note that $\left|V\left(A{G}_n-F_2\right)\right|\ge 3$ and $\left|V\left(A{G}_n\left[A\right]\right)\right|=3$ . Therefore, $F_1$ is a 2-extra cut of $A{G}_n$ , and $A{G}_n-F_1$ has two components $A{G}_n-F_2$ and $A{G}_n\left[A\right]$ . The proof is complete.

A connected graph G is super g-extra connected if every minimum g-extra cut F of G isolates one connected subgraph of order $g+1$ . If, in addition, $G-F$ has two components, one of which is the connected subgraph of order $g+1$ , then G is tightly super g-extra connected.

Corollary 3.3 Let $n\ge 5$ . Then $A{G}_n$ is tightly $\left(6n-19\right)$ super 2-extra connected.

Proof. Let $F_1\subseteq A_n$ . By Lemma 3.2, there is one $\left|F_1\right|=6n-19$ such that F is a 2-extra cut of $A{G}_n$ . Let F be a minimum 2-extra cut of $A{G}_n$ ( $n\ge 5$ ). Then $\left|F\right|\le \left|F_1\right|$ . Suppose that $\left|F\right|\le 6n-20$ . By Lemma 3.3, F is not a 2-extra cut of $A{G}_n$ . Therefore, $\left|F\right|\mathrm{<mo>\; =\; </mo>6}n-19$ . Since F is a 2-extra cut of $A{G}_n$ , by Lemma 2.14, $A{G}_n-F$ has two components, one of which is a path of order 3. The proof is complete.

Lemma 3.4 Let $n\ge 4$ . Then the 2-extra diagnosability of the n-dimensional alternating group graph $A{G}_n$ under the PMC model, ${\tilde{t}}_2\left(A{G}_n\right)\le 6n-17$ .

Proof. Let $A=\left\{\left(1\right),\left(132\right),\left(142\right)\right\}$ , and let $F_1=N_{A{G}_n}\left(A\right)$ , $F_2=A\cup N_{A{G}_n}\left(A\right)$ . By Lemma 3.2, $\left|F_1\right|=6n-19$ , $\left|F_2\right|=6n-16$ , $F_1$ is a 2-extra cut of $A{G}_n$ , and $A{G}_n-F_1$ has two components $A{G}_n-F_2$ and $A{G}_n\left[A\right]$ . Therefore, $F_1$ and $F_2$ are both 2-extra faulty sets of $A{G}_n$ with $\left|F_1\right|=6n-19$ and $\left|F_2\right|=6n-16$ . Since $A=F_1\Delta F_2$ and $N_{A{G}_n}\left(A\right)=F_1\subset F_2$ , there is no edge of $A{G}_n$ between $V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ . By Theorem 3.1, we can deduce that $A{G}_n$ is not 2-extra $\mathrm{<mo\; stretchy="false">\; (\; </mo>6}n-\mathrm{16\; <mo\; stretchy="false">\; )\; </mo>}$ -diagnosable under PMC model. Hence, by the definition of 2-extra diagnosability, we conclude that the 2-extra diagnosability of $A{G}_n$ is less than $6n-16$ , i.e., ${\tilde{t}}_2\left(A{G}_n\right)\le 6n-17$ . The proof is complete.

Lemma 3.5 Let $n\ge 5$ . Then the 2-extra of the n-dimensional alternating group graph $A{G}_n$ under the PMC model, ${\tilde{t}}_2\left(A{G}_n\right)\ge 6n-17$ .

Proof. By the definition of 2-extra diagnosability, it is sufficient to show that $A{G}_n$ is 2-extra $\left(6n-17\right)$ -diagnosable. By Theorem 3.1, to prove $A{G}_n$ is 2-extra $\left(6n-17\right)$ -diagnosable, it is equivalent to prove that there is an edge $uv\in E\left(A{G}_n\right)$ with $u\in V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)$ and $v\in F_1\Delta F_2$ for each distinct pair of 2-extra faulty subsets $F_1$ and $F_2$ of $V\left(A{G}_n\right)$ with $\left|F_1\right|\le 6n-17$ and $\left|F_2\right|\le 6n-17$ .

We prove this statement by contradiction. Suppose that there are two distinct 2-extra faulty subsets $F_1$ and $F_2$ of $A{G}_n$ with $\left|F_1\right|\le 6n-17$ and $\left|F_2\right|\le 6n-17$ , but the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with the condition in Theorem 3.1, i.e., there are no edges between $V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ . Without loss of generality, assume that $F_2\backslash F_1\ne \varnothing$ . Assume $V\left(A{G}_n\right)=F_1\cup F_2$ . By the definition of $A_n$ , $\left|F_1\cup F_2\right|=\left|A_n\right|=n!/2$ . We claim that $n!/2>12n-34$ for $n\ge 5$ , i.e., $n!>24n-68$ for $n\ge 5$ . When $n=5$ , $n!=120$ , $24n-68=52$ . So $n!>24n-68$ for $n=5$ . Assume that $n!>24n-68$ for $n\ge 5$ . $\left(n+1\right)!=n!\left(n+1\right)>\left(n+1\right)\left(24n-68\right)=n\left(24n-68\right)+\left(24n-44\right)-24=$ $\left[24\left(n+1\right)-68\right]+n\left(24n-68\right)-24=\left[24\left(n+1\right)-68\right]+4\left(6n^2-17n-6\right)$. It is sufficient to show that $6n^2-17n-6\ge 0$ for $n\ge 5$ . Let $y=6x^2-17x-6$ . Then $y=6x^2-17x-6$ is a quadratic function. When $x\ge 5$ , $y=6x^2-17x-6\ge 0$ .

Since $n\ge 5$ , we have that $n!/2=\left|V\left(A{G}_n\right)\right|=\left|F_1\cup F_2\right|=\left|F_1\right|+\left|F_2\right|-\left|F_1\cap F_2\right|\le$ $\left|F_1\right|+\left|F_2\right|\le 2\left(6n-17\right)=12n-34$, a contradiction to $n!/2>12n-34$ . Therefore, let $V\left(A{G}_n\right)\ne F_1\cup F_2$ as follows.

Since there are no edges between $V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ , and $F_1$ is a 2-extra faulty set, $A{G}_n-F_1$ has two parts $A{G}_n-F_1-F_2$ and $A{G}_n\left[F_2\backslash F_1\right]$ (for convenience). Thus, every component $G_i$ of $A{G}_n-F_1-F_2$ has $\left|V\left(G_i\right)\right|\ge 3$ and every component ${B^{\prime }}_i$ of $A{G}_n\left[F_2\backslash F_1\right]$ has $\left|V\left({B^{\prime }}_i\right)\right|\ge 3$ . Similarly, every component ${B^{″}}_i$ of $A{G}_n\left[F_1\backslash F_2\right]$ has $\left|V\left(B^{″}\right)\right|\ge 3$ when $F_1\backslash F_2\ne \varnothing$ . Therefore, $F_1\cap F_2$ is also a 2-extra faulty set of $A{G}_n$ . Note that $F_1\cap F_2=F_1$ is also a 2-extra faulty set when $F_1\backslash F_2=\varnothing$ . Since there are no edges between $V\left(A{G}_n-F_1-F_2\right)$ and $F_1\Delta F_2$ , $F_1\cap F_2$ is a 2-extra cut of $A{G}_n$ . If $F_1\cap F_2=\varnothing$ , this is a contradiction to that $A{G}_n$ is connected. Therefore, $F_1\cap F_2\ne \varnothing$ . Since $n\ge 5$ , by Theorem 2.9, $\left|F_1\cap F_2\right|\ge 6n-19$ . Therefore, $\left|F_2\right|=\left|F_2\backslash F_1\right|+\left|F_1\cap F_2\right|\ge 3+6n-19=6n-16$ , which contradicts with that $\left|F_2\right|\le 6n-17$ . So $A{G}_n$ is 2-extra $\left(6n-17\right)$ -diagnosable. By the definition of ${\tilde{t}}_2\left(A{G}_n\right)$ , ${\tilde{t}}_2\left(A{G}_n\right)\ge 6n-17$ . The proof is complete.

Combining Lemma 3.4 and 3.5, we have the following theorem.

Theorem 3.6 Let $n\ge 5$ . Then the 2-extra diagnosability of the n-dimensional alternating group graph $A{G}_n$ under the PMC model is $6n-17$ .

4. The 2-Extra Diagnosability of Alternating Group Graphs under the MM* Model

Before discussing the 2-extra diagnosability of the n-dimensional alternating group graph $A{G}_n$ under the MM* model, we first give a theorem.

Theorem 4.1 ( [1] [18] ) A system $G=\left(V,E\right)$ is g-extra t-diagnosable under the MM* model if and only if for each distinct pair of g-extra faulty subsets $F_1$ and $F_2$ of V with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$ satisfies one of the following conditions.

1) There are two vertices $u\mathrm{,}w\in V\backslash \left(F_1\cup F_2\right)$ and there is a vertex $v\in F_1\Delta F_2$ such that $uw\in E$ and $vw\in E$ .

2) There are two vertices $u\mathrm{,}v\in F_1\backslash F_2$ and there is a vertex $w\in V\backslash \left(F_1\cup F_2\right)$ such that $uw\in E$ and $vw\in E$ .

3) There are two vertices $u\mathrm{,}v\in F_2\backslash F_1$ and there is a vertex $w\in V\backslash \left(F_1\cup F_2\right)$ such that $uw\in E$ and $vw\in E$ .

Lemma 4.2 Let $n\ge 5$ . Then the 2-extra diagnosability of the n-dimensional alternating group graph $A{G}_n$ under the MM* model, ${\tilde{t}}_2\left(A{G}_n\right)\le 6n-17$ .

Proof. Let $A=\left\{\left(1\right),\left(132\right),\left(142\right)\right\}$ , and let $F_1=N_{A{G}_n}\left(A\right)$ , $F_2=A\cup N_{A{G}_n}\left(A\right)$ . By Lemma 3.2, $\left|F_1\right|=6n-19$ , $\left|F_2\right|=6n-16$ , $F_1$ is a 2-extra cut of $A{G}_n$ , and $A{G}_n-F_1$ has two components $A{G}_n-F_2$ and $A{G}_n\left[A\right]$ . Therefore, $F_1$ and $F_2$ are both 2-extra faulty sets of $A{G}_n$ with $\left|F_1\right|=6n-19$ and $\left|F_2\right|=6n-16$ . By the definitions of $F_1$ and $F_2$ , $F_1\Delta F_2=A$ . Note $F_1\backslash F_2=\varnothing$ , $F_2\backslash F_1=A$ and $\left(V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)\right)\cap A=\varnothing$ . Therefore, both $F_1$ and $F_2$ are not satisfied with any one condition in Theorem 4.1, and $A{G}_n$ is not 2-extra $\left(6n-16\right)$ diagnosable. Hence, ${\tilde{t}}_2\left(A{G}_n\right)\le 6n-17$ . Thus, the proof is complete.

A component of a graph G is odd according as it has an odd number of vertices. We denote by $o\left(G\right)$ the number of add component of G.

Lemma 4.3 ( [13] Tutte’s Theorem) A graph $G=\left(V,E\right)$ has a perfect matching if and only if $o\left(G-S\right)\le \left|S\right|$ for all $S\subseteq V$ .

Lemma 4.4 Let $n\ge 4$ . Then $A{G}_n$ has a perfect matching.

Proof. Note that a perfect matching of $A{G}_4$ is $\{\left[\mathrm{1342,4132}\right]\mathrm{,}\left[\mathrm{2431,1234}\right]\mathrm{,}$ $\left[\mathrm{3241,4321}\right]\mathrm{,}\left[\mathrm{1423,3124}\right]\mathrm{,}\left[\mathrm{3412,2314}\right]\mathrm{,}\left[\mathrm{2143,4213}\right]\}$ (see Figure 1). We prove this lemma by induction on n. The result holds for $n=4$ . Assume $n\ge 5$ and the result holds for $A{G}_{n-1}$ , i.e., $A{G}_{n-1}$ has a perfect matching. We decompose $A{G}_n$ into n sub-alternating group graph, $A{G}_n^1\mathrm{,}A{G}_n^2\mathrm{,}\cdots \mathrm{,}A{G}_n^n$ , where each $A{G}_n^i$ has a fixed i in the last position of the label strings which represents the vertices and is isomorphic to $A{G}_{n-1}$ . Therefore, $A{G}_n^i$ has a perfect matching. Let $M_i$ be a perfect matching of $A{G}_n^i$ . Then $M_1\cup \cdots \cup M_n$ is a perfect matching of $A{G}_n$ . The proof is complete.

Lemma 4.5 Let $n\ge 5$ . Then the 2-extra diagnosability of the n-dimensional alternating group graph $A{G}_n$ under the MM* model, ${\tilde{t}}_2\left(A{G}_n\right)\ge 6n-17$ .

Proof. By the definition of 2-extra diagnosability, it is sufficient to show that $A{G}_n$ is 2-extra $\left(6n-17\right)$ -diagnosable.

Suppose, on the contrary, that there are two distinct 2-extra faulty subsets $F_1$ and $F_2$ of $A{G}_n$ with $\left|F_1\right|\le 6n-17$ and $\left|F_2\right|\le 6n-17$ , but the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with any one condition in Theorem 4.1. Without loss of generality, assume that $F_2\backslash F_1\ne \varnothing$ . Assume $V\left(A{G}_n\right)=F_1\cup F_2$ . By the definition of $A_n$ , $\left|F_1\cup F_2\right|=\left|A_n\right|=n!/2$ . Similar to the discussion on $V\left(A{G}_n\right)\ne F_1\cup F_2$ in Lemma 3.5, we can deduce $V\left(A{G}_n\right)=F_1\cup F_2$ . Therefore, $V\left(A{G}_n\right)\ne F_1\cup F_2$ .

Claim 1. $A{G}_n-F_1-F_2$ has no isolated vertex.

Suppose, on the contrary, that $A{G}_n-F_1-F_2$ has at least one isolated vertex $w_1$ . Since $F_1$ is one 2-extra faulty set, there is a vertex $u\in F_2\backslash F_1$ such that u is adjacent to $w_1$ . Meanwhile, since the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with any one condition in Theorem 4.1, by the condition (3) of Theorem 4.1, there is at most one vertex $u\in F_2\backslash F_1$ such that u is adjacent to $w_1$ . Thus, there is just a vertex $u\in F_2\backslash F_1$ such that u is adjacent to $w_1$ . If $F_1\backslash F_2=\varnothing$ , then $F_1\subseteq F_2$ . Since $F_2$ is a 2-extra faulty set, every component $G_i$ of $A{G}_n-F_1-F_2=A{G}_n-F_2$ has $\left|V\left(G_i\right)\right|\ge 3$ . Therefore, $A{G}_n-F_1-F_2$ has no isolated vertex. Thus, let $F_1\backslash F_2\ne \varnothing$ . Similarly, we can deduce that there is just a vertex $a\in F_1\backslash F_2$ such that a is adjacent to $w_1$ . Let $W\subseteq A_n\backslash \left(F_1\cup F_2\right)$ be the set of isolated vertices in $A{G}_n\left[A_n\backslash \left(F_1\cup F_2\right)\right]$ , and let H be the induced subgraph by the vertex set $A_n\backslash \left(F_1\cup F_2\cup W\right)$ . Then for any $w\in W$ , there are $\left(2n-6\right)$ neighbors in $F_1\cap F_2$ .

By Lemmas 4.3 and 4.4, $\left|W\right|\le o\left(A{G}_n-\left(F_1\cup F_2\right)\right)\le \left|F_1\cup F_2\right|=\left|F_1\right|+\left|F_2\right|-$ $\left|F_1\cap F_2\right|\le 2\left(6n-17\right)-\left(2n-6\right)=10n-28$. Since $n\ge 5$ , $n!/4>10n-28$ . Therefore, $\left|W\right|\le n!/4$ . Suppose $V\left(H\right)=\varnothing$ . Then $n!/2=\left|V\left(A{G}_n\right)\right|=\left|F_1\cup F_2\right|+$ $\left|W\right|=\left|F_1\right|+\left|F_2\right|-\left|F_1\cap F_2\right|+\left|W\right|\le 2\left(6n-17\right)-\left(2n-6\right)+\left|W\right|=10n-28+\left|W\right|<n!/4$$+10n-28$ and hence $n!/4<10n-28$ , a contradiction to that $n\ge 5$ . So $V\left(H\right)\ne \varnothing$ .

Since the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with the condition (1) of Theorem 4.1, and any vertex of $V\left(H\right)$ is not isolated in H, we induce that there is no edge between $V\left(H\right)$ and $F_1\Delta F_2$ . Thus, $F_1$ is a vertex cut of $A{G}_n$ . Since $F_1$ is a 2-extra faulty set of $A{G}_n$ , we have that every component $H_i$ of H has $\left|V\left(H_i\right)\right|\ge 3$ and every component $B_i$ of $A{G}_n\left[W\cup \left(F_2\backslash F_1\right)\right]$ has $\left|V\left(B_i\right)\right|\ge 3$ . Therefore, $F_1$ is also a 2-extra cut of $A{G}_n$ . If $F_1\cap F_2=\varnothing$ , then this is a contradiction to that $A{G}_n$ is connected. Therefore, $F_1\cap F_2\ne \varnothing$ . By Theorem 2.9, $\left|F_1\right|\ge 6n-19$ . Since $\left|F_1\right|\le 6n-17$ , we have $6n-19\le \left|F_1\right|\le 6n-17$ . Since every component $B_i$ of $A{G}_n\left[W\cup \left(F_2\backslash F_1\right)\right]$ has $\left|V\left(B_i\right)\right|\ge 3$ , we have $\left|F_2\backslash F_1\right|\ge 2$ and hence $\left|F_1\right|=6n-17$ and $\left|F_2\backslash F_1\right|=2$ . Since $F_2$ is a 2-extra faulty set of $A{G}_n$ , we have that $W=\varnothing$ when $F_1\backslash F_2=\varnothing$ . Therefore, let $F_1\backslash F_2\cancel{=}\varnothing$ . Similarly, we can deduce that $F_2$ is also a 2-extra cut of $A{G}_n$ , $\left|F_2\right|=6n-17$ and $\left|F_1\backslash F_2\right|=2$ . Let $F_2\backslash F_1=\left\{u,v\right\}$ , $F_1\backslash F_2=\left\{a,b\right\}$ , and let $vu{w}_{1}ab$ be a path in $A{G}_n$ (see Figure 2).

Since there is no edge between $V\left(H\right)$ and $F_1\Delta F_2$ , $V\left(H\right)\ne \varnothing$ and $F_2\backslash F_1\ne \varnothing$ , $F_1\cap F_2$ is a cut of $A{G}_n$ . By the above result, $\left|F_1\cap F_2\right|=6n-19$ . Since every component $H_i$ of H has $\left|V\left(H_i\right)\right|\ge 3$ , every component $B_i$ of $A{G}_n\left[W\cup \left(F_2\backslash F_1\right)\right]$ has $\left|V\left(B_i\right)\right|\ge 3$ and every component ${B^{\prime }}_i$ of $A{G}_n\left[W\cup \left(F_2\backslash F_1\right)\right]$ has $\left|V\left({B^{\prime }}_i\right)\right|\ge 3$ , we have that every component $H_i$ of H has $\left|V\left(H_i\right)\right|\ge 3$ and every component $G_i$ of $A{G}_n\left[W\cup \left(F_2\backslash F_1\right)\cup \left(F_1\backslash F_2\right)\right]$ has $\left|V\left(G_i\right)\right|\ge 3$ . By Theorem 2.9, ${\tilde{\kappa }}^{\left(2\right)}\left(A{G}_n\right)=6n-19$ and $F_1\cap F_2$ is a minimum 2-extra cut of $A{G}_n$ . Therefore, $\left|F_1\cap F_2\right|=6n-19$ . By Corollary 3.3, $A{G}_n$ is tightly $\left(6n-19\right)$ super 2-extra connected, i.e., $A{G}_n-\left(F_1\cap F_2\right)$ has two components, one of which is the path of length 3. Since $\left|F_2\backslash F_1\right|+\left|F_1\backslash F_2\right|+\left|W\right|\ge 5$ , we have that $\left|V\left(A{G}_n-F_1-F_2-W\right)\right|=3$ . Thus,

$n!/2=\left|V\left(A{G}_n\right)\right|=\left|V\left(A{G}_n-F_1-F_2-W\right)\right|+\left|F_2\backslash F_1\right|+\left|F_1\backslash F_2\right|+\left|W\right|+\left|F_2\cap F_1\right|<3+$ $2+2+n!/4+6n-19=6n-12+n!/4$and hence $n!/4<6n-12$ , a contradiction to $n\ge 5$ . The proof Claim 1 is complete.

Let $u\in V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)$ . By Claim 1, u has at least one neighbor in $A{G}_n-F_1-F_2$ . Since the vertex set pair $\left(F_1\mathrm{,}{F}_2\right)$ is not satisfied with any one condition in Theorem 4.1, by the condition (1) of Theorem 4.1, for any pair of adjacent vertices $u\mathrm{,}w\in V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)$ , there is no vertex $v\in F_1\Delta F_2$ such that $uw\in E\left(A{G}_n\right)$ and $vw\in E\left(A{G}_n\right)$ . It follows that u has no neighbor in $F_1\Delta F_2$ . By the arbitrariness of u, there is no edge between $V\left(A{G}_n\right)\backslash \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$ . Since $F_2\backslash F_1\ne \varnothing$ and $F_1$ is a 2-extra faulty set, every component $H_i$ of $A{G}_n-F_1-F_2$ has $\left|V\left(H_i\right)\right|\ge 3$ and every component $G_i$ of $A{G}_n\left(\left[F_2\backslash F_1\right]\right)$ has $\left|V\left(G_i\right)\right|\ge 3$ . Suppose that $F_1\backslash F_2\mathrm{<mo>\; =\; </mo>}\varnothing$ . Then $F_1\cap F_2=F_1$ . Since $F_1$ is a 2-extra faulty set of $A{G}_n$ , we have that $F_1\cap F_2\mathrm{<mo>\; =\; </mo>}{F}_1$ is a 2-extra faulty set of $A{G}_n$ . Since $\left|V\left(A{G}_n-F_1-F_2\right)\right|=\left|V\left(A{G}_n-F_2\right)\right|\ge 3$ and $\mathrm{<mo>\; |\; </mo>}{F}_2\backslash F_1\mathrm{<mo>\; |\; </mo>}\ge 3$ , $F_1\cap F_2=F_1$ is a 2-extra cut of $A{G}_n$ . Suppose that $F_1\backslash F_2\ne \varnothing$ . If $F_1\cap F_2=\varnothing$ , then this is a contradiction to that $A{G}_n$ is connected. Therefore,