Some Results About the Reliability of Folded Hypercubes
- PDF / 467,344 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 60 Downloads / 159 Views
Some Results About the Reliability of Folded Hypercubes Mohsen Ghasemi1 Received: 19 March 2020 / Revised: 8 August 2020 / Accepted: 11 August 2020 © Malaysian Mathematical Sciences Society and Penerbit Universiti Sains Malaysia 2020
Abstract In this paper we investigate some reliability measures, including super-connectivity, cyclic edge connectivity, etc., in the folded hypercubes. Keywords Restricted edge-connectivity · Edge-transitive · Folded hypercubes Mathematics Subject Classification 05C40 · 05C90
1 Introduction Suppose that is a finite, simple and undirected graph. We use V (), E(), A() and Aut() for showing the vertex set, edge set, arc set and the automorphism group of , respectively. We say that is vertex-transitive, edge-transitive and arc-transitive if Aut() acts transitive on V (), E(), A(), respectively. We remind that hypercube Q n is a graph with 2n vertices, each vertex with a distinct binary string x1 x2 · · · xn on the set {0, 1}. Two vertices are linked by an edge if and only if their strings differ in exactly one bit. It is well known that Q n is an arc-transitive graph. As a variant of the hypercube, the n-dimensional folded hypercube F Q n , proposed first by El-Amawy and Latifi [1], is a graph obtained from the hypercube Q n by adding an edge, called a complementary edge, between any two vertices x = (x1 x2 · · · xn ) and x = (x1 x2 · · · xn ), where xi = 1 − xi . The graphs shown in Figs. 1 and 2 are F Q 3 and F Q 4 , respectively. By an easy observation, F Q n is an (n + 1)-regular and its order is 2n . Like Q n , F Q n is arc-transitive (see [15]). Also by [1], it has diameter of n/2 which is smaller than the diameter of Q n . In the literature, F Q n has received considerable attention, and a lot of its properties have been investigated. For example see ([7–9,13,22,23,25,29,34]).
Communicated by Rosihan M. Ali.
B 1
Mohsen Ghasemi [email protected] Department of Mathematics, Urmia University, Urmia 57135, Iran
123
M. Ghasemi Fig. 1 (F Q 3 )
Fig. 2 (F Q 4 )
Zhou et al. (see [33]) studied some reliability measures such as super-connectivity, cyclically connectivity in the balanced hypercube by using its symmetric properties. In this paper we get the similar results for n-dimensional folded hypercube F Q n .
2 Preliminaries In this section, we give some terminology and notation. For notation and terminology not define here we follow [3]. Let n be a positive integer. Denote by Cn the cyclic graph of order n. For a vertex v in a graph , use N (v) to denote the neighborhood of v, that is, the set of vertices adjacent to v. Also for a positive integer m, m K 1 represents the null graph with m vertices and a graph is trivial if it is a vertex.
123
Some Results About the Reliability of Folded Hypercubes
The vertex-connectivity of a graph denoted by κ() is the minimum number of vertices whose removal results in a disconnected graph or a trivial graph. Similarly, we can define edge-connectivity of a graph which is denoted by λ(). In fact κ() and λ() are
Data Loading...
