% Template article for preprint document class `elsart'
% SP 2001/01/05
% Modified 2007/01/09 for CTW 2010
% Please find the original file at http://www.elsevier.com/
\documentclass{ctwart}
% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}
% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}
% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
\begin{document}
\begin{frontmatter}
% Title, authors and addresses
% use the thanksref command within \title, \author or \address for footnotes;
% use the corauthref command within \author for corresponding author footnotes;
% use the ead command for the email address,
% and the form \ead[url] for the home page:
% \title{Title\thanksref{label1}}
% \thanks[label1]{}
% \author{Name\corauthref{cor1}\thanksref{label2}}
% \ead{email address}
% \ead[url]{home page}
% \thanks[label2]{}
% \corauth[cor1]{}
% \address{Address\thanksref{label3}}
% \thanks[label3]{}
\title{Cycle embedding in alternating group graphs with faulty vertices and faulty edges}
% use optional labels to link authors explicitly to addresses:
% \author[label1,label2]{}
% \address[label1]{}
% \address[label2]{}
\author{Ping-Ying Tsai\corauthref{cor}}
\corauth[cor]{corresponding author}
\ead{bytsai@math.sinica.edu.tw}
\address{Institute of Mathematics, Academia Sinica, Taipei 10617, Taiwan, ROC}
\begin{keyword}
Alternating group graph \sep Pancyclicity \sep Fault-tolerant \sep Cayley graph
\sep Cycle embedding \sep Interconnection network.
% keywords here, in the form: keyword \sep keyword
\end{keyword}
\end{frontmatter}
% main text
\section{Introduction}
\label{sec:intro}
Let $G$ be a graph with the vertex set $V(G)$ and the edge set $E(G)$.
Unless otherwise stated, we follow \cite{Bondy} for graph terminologies and notations.
A path $P_{v_0,v_k} = \left\langle v_0, v_1, \ldots, v_k\right\rangle$
is a sequence of distinct vertices except possibly $v_0 = v_k$
such that every two consecutive vertices are adjacent.
The \textit{length} of a path is the number of edges on the path.
The \textit{distance} between $u$ and $v$ is denoted by $d(u,v)$,
which is the length of a shortest path between $u$ and $v$.
A \textit{cycle} is a special path with at least three vertices
such that the first vertex is the same as the last one.
A cycle of length $l$ is referred to as an \textit{l-cycle}.
An interconnection network is usually modeled as an undirected simple graph,
where the vertices represent processors
and the edges represent communication links between processors.
Study of the topological properties of an interconnection network
is an important part of the study of any parallel or distributed system.
The alternating group graph~\cite{Jwo93}, which is an instance of Cayley graphs,
is suitable to serve as a network
because of its scalability and other favorable properties,
e.g., regularity, recursiveness, symmetry, sublogarithmic degree and diameter,
and maximal fault tolerance.
Let $u = a_1a_2 \cdots a_n$ be a permutation of $1$, $2$, \ldots, $n$,
i.e., $a_i \in \{1, 2, \ldots, n\}$ and $a_i \neq a_j$ for $i \neq j$.
A pair of symbols $a_i$ and $a_j$ of $u$ are said to be an inversion
if $a_i < a_j$ whenever $i > j$.
An even permutation is a permutation that contains an even number of inversions.
Let $A_n$ denote the set of all even permutations over $\{1, 2, \ldots, n\}$.
For $3 \leq i \leq n$, we define two operations, $g_i^+$ and $g_i^-$, on $A_n$ by setting
$ug_i^+$ (respectively, $ug_i^-$) to be the permutation obtained from $u$ by rotating
the symbols $a_1$, $a_2$, $a_i$ from left to right (respectively, from right to left),
while retaining the other $n-3$ symbols stationary.
For example, we have $12345g_4^+ = 41325$ and $12345g_4^- = 24315$.
The $n$-dimensional alternating group graph $AG_n$, has the vertex set $V(AG_n) = A_n$
and the edge set $E(AG_n) = \{(u,v) | u,v \in V(AG_n)$
and $v = ug_i^+$ or $v = ug_i^-$ for some $3 \leq i \leq n\}$.
It is not difficult to see that $AG_n$ is regular with vertex degree $2(n-2)$,
$|V(AG_n)| = n!/2$, and $|E(AG_n)| = (n-2)n!/2$.
In addition, $AG_n$ is both vertex symmetric and edge symmetric \cite{Jwo93}.
For $n \geq 3$ and $1 \leq i \leq n$, let $A_n^{(i)}$ be the subset of $A_n$
that consists of all even permutations with element $i$ in the rightmost position,
and let $AG_n^{(i)}$ be the subgraph of $AG_n$ induced by $A_n^{(i)}$.
Obviously, $AG_n^{(i)}$ is isomorphic to $AG_{n-1}$ for every $i \in \{1, 2, \ldots, n\}$.
Due to the hierarchical structure, $AG_n$ can also be defined recursively as follows.
$AG_n$ is constructed from $n$ disjoint copies of
$(n-1)$-dimensional alternating group graphs $AG_n^{(i)}$ for $i \in \{1, 2, \ldots, n\}$
such that $AG_n^{(i)}$ and $AG_n^{(j)}$, $i \neq j$,
are connected by $(n-2)!$ edges, called \textit{external edges},
of the form $(kj \cdots i, ik \cdots j)$ or $(jk \cdots i, ki \cdots j)$
for $k \in \{1, 2, \ldots, n\} \setminus \{i,j\}$.
By contrast,
edges joining vertices in the same subgraph $AG_n^{(i)}$ are called \textit{internal edges}.
In particular,
for each internal edge $(u,v)$ with $u = kj \cdots i$ and $v = jk' \cdots i$ in $AG_n^{(i)}$,
there exist two adjacent vertices $s = ik \cdots j$ and $t = k'i \cdots j$ in $AG_n^{(j)}$
such that $s = ug_n^+$, $t = vg_n^-$,
and $\left\langle u,s,t,v,u \right\rangle$ forms a $4$-cycle in $AG_n$.
For convenience, such a property is called the $4$-\textit{cycle structure} of $(u,v)$.
Note that the pair of vertices $s$ and $t$ is uniquely determined
by the 4-cycle structure of $(u,v)$.
As a result, every vertex $u \in V(AG_n^{(i)})$ is connected to
exactly $2$ external edges and $2n-6$ internal edges.
A path (or cycle) in $G$ is called a \textit{Hamiltonian path} (or \textit{Hamiltonian cycle})
if it contains every vertex of $G$ exactly once.
A graph $G$ is called \textit{Hamiltonian} if it has a Hamiltonian cycle.
$G$ is called \textit{Hamiltonian-connected}
if every two vertices of $G$ are connected by a Hamiltonian path.
For an integer $r \geq 3$, $G$ is called \textit{r-pancyclic}
if it contains an $l$-cycle for each $l$ with $r \leq l \leq |V(G)|$.
In particular, $G$ is called \textit{vertex r-pancyclic} (or \textit{edge r-pancyclic})
if every vertex (or edge) of $G$ belongs to an $l$-cycle
for each $l$ with $r \leq l \leq |V(G)|$.
A 3-pancyclic graph, a vertex 3-pancyclic graph, and an edge 3-pancyclic graph are called
\textit{pancyclic}, \textit{vertex-pancyclic}, and \textit{edge-pancyclic}, respectively.
Exploring the pancyclicity of the given graph
has attracted a lot of mathematicians \cite{Bondy71,Kouider02,Randerath02}.
Recently, some researchers have focused on the problem on interconnection networks
because networks with cycle topology are suitable for
designing simple algorithms with low communication costs
(for example, \cite{Germa98,Hsieh07,Xu06,Yang04}).
A graph $G$ is \textit{panconnected} if, for any two distinct vertices $u, v \in V(G)$
and for each integer $l$ with $d(u,v) \leq l \leq |V(G)|-1$,
there is a $P_{u,v}$ of length $l$ in $G$.
It was shown in \cite{Chang04} that the alternating group graph is panconnected.
\textbf{Lemma 1} (\cite{Chang04})
\emph{For $n \geq 3$, $AG_n$ is panconnected.}
Since faults may occur in networks,
the consideration of fault-tolerance ability is a major factor
in evaluating the performance of networks.
Cycle embedding is also concerned extensively in many interconnection networks
with faulty elements \cite{Hsieh08,Tsai08,MXu06}.
Suppose $F_v \subset V(G)$, $F_e \subset E(G)$, and $F = F_v \cup F_e$.
A graph $G$ is \emph{k-vertex-fault-tolerant pancyclic}
if $G - F_v$ remains pancyclic whenever $|F_v| \leq k$.
A graph $G$ is called \emph{k-edge-fault-tolerant pancyclic}
if $G - F_e$ is pancyclic whenever $|F_e| \leq k$.
A graph $G$ is called \emph{k-fault-tolerant pancyclic}
if $G - F$ remains pancyclic when $|F| \leq k$.
The notion for \emph{k-fault-tolerant Hamiltonian},
\emph{k-fault-tolerant Hamiltonian-connected},
\emph{k-fault-tolerant vertex r-pancyclic},
and \emph{k-fault-tolerant edge r-pancyclic} can also be defined similarly.
\textbf{Lemma 2} (\cite{Chang08})
\emph{$AG_n$ is $(n-4)$-vertex-fault-tolerant edge 4-pancyclic
and $(n-3)$-vertex-fault-tolerant vertex-pancyclic, where $n \geq 4$.}
\textbf{Lemma 3} (\cite{Xue09})
\emph{$AG_n$ is $(2n-6)$-vertex-fault-tolerant pancyclic, where $n \geq 3$.}
\textbf{Lemma 4} (\cite{Tsai09})
\emph{$AG_n$ is $(2n-6)$-edge-fault-tolerant pancyclic, where $n \geq 3$.}
\textbf{Lemma 5} (\cite{Tsai09})
\emph{$AG_n$ is $(2n-7)$-fault-tolerant Hamiltonian-connected, where $n \geq 4$.}
\section{Main results}
\label{section:results}
We improve previous results in Lemma 2, Lemma 3, and Lemma 4,
by showing that the $n$-dimensional alternating group graph $AG_n$ is
$(n-4)$-fault-tolerant edge 4-pancyclic, $(n-3)$-fault-tolerant vertex-pancyclic,
and $(2n-6)$-fault-tolerant pancyclic,
while considering both faulty vertices and faulty edges.
All the results we achieved here are optimal
with respect to the number of faulty elements tolerated.
\textbf{Theorem 1}
\emph{$AG_n$ is $(n-4)$-fault-tolerant edge 4-pancyclic, where $n \geq 4$.}
\textbf{Theorem 2}
\emph{$AG_n$ is $(n-3)$-fault-tolerant vertex-pancyclic, where $n \geq 3$.}
\textbf{Theorem 3}
\emph{$AG_n$ is $(2n-6)$-fault-tolerant pancyclic, where $n \geq 3$.}
Since a graph is Hamiltonian if it is pancyclic, we have the following Corollary.
\textbf{Corollary 1}
\emph{$AG_n$ is $(2n-6)$-fault-tolerant Hamiltonian, where $n \geq 3$.}
% The Appendices part is started with the command \appendix;
% appendix sections are then done as normal sections
% \appendix
% \section{}
% \label{}
\begin{thebibliography}{00}
% \bibitem{label}
% Text of bibliographic item
% notes:
% \bibitem{label} \note
% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}
%
\bibitem{Bondy71}
J. A. Bondy.
\newblock Pancyclic graphs.
\newblock {\em Journal of Combinatorial Theory - Series B}, 11(1):80-84, 1971.
%
\bibitem{Bondy}
J. A. Bondy and U. S. R. Murty.
\newblock {\em Graph Theory,} volume 244 of {\em Graduate Texts in Mathematics}.
\newblock Springer, Berlin, 2008.
%
\bibitem{Chang08}
J. M. Chang and J. S. Yang.
\newblock Fault-tolerant cycle-embedding in alternating group graphs.
\newblock {\em Applied Mathematics and Computation}, 197(2):760-767, 2008.
%
\bibitem{Chang04}
J. M. Chang, J. S. Yang, Y. L. Wang, and Y. Cheng.
\newblock Panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-Connectivity in alternating group graphs.
\newblock {\em Networks}, 44(4):302-310, 2004.
%
\bibitem{Germa98}
A. Germa, M. C. Heydemann, and D. Sotteau.
\newblock Cycles in the cube-connected cycles graph.
\newblock {\em Discrete Applied Mathematics}, 83(1-3):135-155, 1998.
%
\bibitem{Hsieh07}
S. Y. Hsieh and J. Y. Shiu.
\newblock Cycle embedding of augmented cubes.
\newblock {\em Applied Mathematics and Computation}, 191(2):314-319, 2007.
%
\bibitem{Hsieh08}
S. Y. Hsieh and T. H. Shen.
\newblock Edge-bipancyclicity of a hypercube with faulty vertices and edges.
\newblock {\em Discrete Applied Mathematics}, 156(10):1802-1808, 2008.
%
\bibitem{Jwo93}
J. S. Jwo, S. Lakshmivarahan, and S. K. Dhall.
\newblock A new class of interconnection networks based on the alternating group.
\newblock {\em Networks}, 23:315-326, 1993.
%
\bibitem{Kouider02}
M. Kouider and A. Marczyk.
\newblock On pancyclism in Hamiltonian graphs.
\newblock {\em Discrete Mathematics}, 251(1-3):119-127, 2002.
%
\bibitem{Randerath02}
B. Randerath, I. Schiermeyer, M. Tewes, and L. Volkmann.
\newblock Vertex pancyclic graphs.
\newblock {\em Discrete Applied Mathematics}, 120(1-3):219-237, 2002.
%
\bibitem{Tsai08}
C. H. Tsai.
\newblock Fault-tolerant cycles embedded in hypercubes with mixed link and node failures.
\newblock {\em Applied Mathematics Letters}, 21(8):855-860, 2008.
%
\bibitem{Tsai09}
P. Y. Tsai, J. S. Fu, and G. H. Chen.
\newblock Edge-fault-tolerant pancyclicity of alternating group graphs.
\newblock {\em Networks}, 53(3):307-313, 2009.
%
\bibitem{Xu06}
J. M. Xu and M. J. Ma.
\newblock Cycles in folded hypercubes.
\newblock {\em Applied Mathematics Letters}, 19(2):140-145, 2006.
%
\bibitem{MXu06}
M. Xu, X. D. Hu, and Q. Zhu.
\newblock Edge-bipancyclicity of star graphs under edge-fault tolerant.
\newblock {\em Applied Mathematics and Computation}, 183(2):972-979, 2006.
%
\bibitem{Xue09}
Z. J. Xue and S. Y. Liu.
\newblock An optimal result on fault-tolerant cycle-embedding in alternating group graphs.
\newblock {\em Information Processing Letters}, 109(21-22):1197-1201, 2009.
%
\bibitem{Yang04}
X. F. Yang, G. M. Megson, and D. J. Evans.
\newblock Locally twisted cubes are 4-pancyclic.
\newblock {\em Applied Mathematics Letters}, 17(8):919-925, 2004.
%
\end{thebibliography}
\end{document}