With the development of VLSI technology and software technology, multiprocessor systems with hundreds of thousands of processors have become available. With the continuous increase in the size of multiprocessor systems, the complexity of a system can adversely affect its fault tolerance and reliability. To the design and maintenance purpose of multiprocessor systems, appropriate measures of reliability should be found.
A network is often modeled by a graph with the vertices representing nodes such as processors or stations, and the edges representing links between the nodes. One fundamental consideration in the design of networks is reliability  . An edge cut of a connected graph is a set of edges whose removal disconnects . The edge connectivity or connectivity of is the minimum cardinality of an edge cut or vertex cut of . The edge connectivity or connectivity is an important feature determining reliability and fault-tolerance of the network. In the definitions of or , no restrictions are imposed on the components of . To compensate for this short coming, it would seem natural to generalize the notion of the classical connectivity by imposing some conditions or restrictions on the components of . Following this idea, conditional connectivity were proposed in  by Harary.
Let be a connected graph and be graph-theoretic property. The conditional edge connectivity or conditional connectivity is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects and each remaining component has property . In particular, we focus on that each component has the property of minimum degree . The k-conditional edge connectivity is the cardinality of the minimum edge cuts , if any, whose deletion disconnects and each component of has property of minimum degree . The k-conditional connectivity can be obtained similarly. In recent years, numerous results about many kind of connectivities on networks have been reported -.
Let be a connected graph, the neighbors of avertex in (simply ), the edges incident to . Moreover, for , is the subgraph induced by , , , and denotes the subgraph of induced by the vertex set of . If , denotes the length of a shortest -path. For , denote by the set of edges of with one end in and the other in . For graph-theo- retical terminology and notation not defined here we follow . All graphs considered in this paper are simple, finite and undirected.
Two binary strings and are pair-related, denoted , if and only if ; if and are not pair-related, we write .
The crossed cube with vertices was introduced by Efe . It can be defined inductively as follows: is , the complete graph with labels 0 and 1. For , contains and joined according to the following rule: the vertex from and the vertex from are adjacent if and only if
1) if is even, and
2) for .
From the definition, we can see that each vertex of with a leading 0 bit has exactly one neighbor with a leading 1 and vice versa. It is an n-regular graph. In fact, some pairs of parallel edges are changed to some pairs of cross edges. Furthermore, can be obtained by adding a perfect matching between and . Hence can be viewed as or briefly. For any vertex is the edge incident to in .
The crossed cube is an attractive alternative to hypercubes . The diameter of is approximately half that of . For more references, we can see - (Figure 1).
In this paper, we obtain that: , and we also prove other properties of .
2. Conditional Connectivity of Crossed Cubes
The crossed cube has an important property as follows.
Lemma 2.1. Any two vertices of have at most two common neighbors for if they have.
Proof: By induction. If , then the result holds. We assume that it is true for . Suppose and any such that have at most two common neighbors.
If , then the two common neighbors are in according to inductive hypothesis. And there is not a relation between the common neighbors of and the perfect matching added to . Hence have at most two common neighbors in .
By symmetry, we assume that . The common neighbors must be obtained by adding the perfect matching . Note that every vertex of has only one neighbor in and vice versa. Then we obtain the result.
Corollary 2.2. For any two vertices ,
1) if , then they have at most two common neighbors;
2) if , then they do not have common neighbors.
Figure 1. Crossed cube for .
Corollary 2.3. The girth of is .
According to the definition of , and similar to Lemma 2.1, we have
Lemma 2.4. Let and be any two vertices of such that have only two common neighbors.
1) If , then the one common neighbor is in , and the other one is in
2) If or , then the two common neighbors are in or .
Lemma 2.5. Let be an induced subgraph of and .
2) If , then .
3) If , then is a 4-cycle and .
Because and The girth of is 4, . If , then is a 4-cycle .
Assume that . Let . Since , has at least two neighbors in , which is a contracted to the definition of . Hence . If , then .
Take a 4-cycle in . Clearly, and is not connected and minimum degree of each component is at least two. Then .
We will show by induction. It is easy to check that holds for . So we suppose . Assume that it is true for . Let .
Let with . And is not connected and minimum degree of each component is at least two. We have or . Without loss of generality, we set . And is connected from the inductive hypothesis. We will show that every vertex of is connected to .
If there is a vertex of with , then by the hypothesis is connected to , a contradiction. Hence for any vertex of , we have . Let be an any component of . Since , we have and by Lemma 2.6. Suppose and . Let be a some vertex of . Because of , at least one vertex of has a neighbor in . Then is connected to . Moreover, is connected, a contradiction.
The conditional connectivity is a generalization of classical connectivity of graphs. We determined the r-conditional degree connectivity of for the small r. In the future, we will study other properties of crossed cubes.
The authors would like to thank the referees for kind help and valuable suggestions.
 Lin, L., Xu, L. and Zhou, S. (2016) Relating the Extra Connectivity and the Conditional Diagnosability of Regular Graphs under the Comparison Model. Theoretical Comput. Sci., 618, 21-29. https://doi.org/10.1016/j.tcs.2015.12.031
 Wang, S., Wang, Z. and Wang, M. (2016) The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks. The Computer Journal, 59, 1839-1856. https://doi.org/10.1093/comjnl/bxw037
 Zhang, M., Zhang, L. and Feng, X. (2016) Reliability Measures in Relation to the h-Extra Edge-Connectivity of Folded Hypercubes. Theoretical Comput. Sci., 615, 71-77. https://doi.org/10.1016/j.tcs.2015.11.049
 Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. https://doi.org/10.1016/0167-8191(94)90130-9