Given a graph G and a non-negative integer h, the h-restricted connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, in which at least h neighbors of any vertex is not included, if any, whos...Given a graph G and a non-negative integer h, the h-restricted connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, in which at least h neighbors of any vertex is not included, if any, whose deletion disconnects G and every remaining component has the minimum degree of vertex at least h; and the h-extra connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, if any, whose deletion disconnects G and every remaining component has order more than h. This paper shows that for the hypercube Qn and the folded hypercube FQn, κ1（Qn）=κ（1）（Qn）=2n-2 for n≥3, κ2（Qn）=3n-5 for n≥4, κ1（FQn）=κ（1）（FQn）=2n for n≥4 and κ（2）（FQn）=4n-4 for n≥8.展开更多
Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Ba...Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Basing on which, we has proved that in generalized hypercubes, every edge can be contained on a cycle of every length from 3 to IV（G）I inclusive and all kinds of length cycles have been constructed. The edgepanciclieity and node-pancilicity of generalized hypercubes can be applied in the topology design of computer networks to improve the network performance.展开更多
文摘Given a graph G and a non-negative integer h, the h-restricted connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, in which at least h neighbors of any vertex is not included, if any, whose deletion disconnects G and every remaining component has the minimum degree of vertex at least h; and the h-extra connectivity κh（G） of G is the minimum cardinality of a set of vertices of G, if any, whose deletion disconnects G and every remaining component has order more than h. This paper shows that for the hypercube Qn and the folded hypercube FQn, κ1（Qn）=κ（1）（Qn）=2n-2 for n≥3, κ2（Qn）=3n-5 for n≥4, κ1（FQn）=κ（1）（FQn）=2n for n≥4 and κ（2）（FQn）=4n-4 for n≥8.
基金This project is supported by National Natural Science Foundation of China （10671081）
文摘Generalized hypercubes （denoted by Q（d1,d2,... ,dn）） is an important network topology for parallel processing computer systems. Some methods of forming big cycle from small cycles and links have been developed. Basing on which, we has proved that in generalized hypercubes, every edge can be contained on a cycle of every length from 3 to IV（G）I inclusive and all kinds of length cycles have been constructed. The edgepanciclieity and node-pancilicity of generalized hypercubes can be applied in the topology design of computer networks to improve the network performance.
