The super-connected property of recursive circulant graphs

In a graph G, a k-container C_k(u,v) is a set of k disjoint paths joining u and v. A k-container C_k(u,v) is k∗-container if every vertex of G is passed by some path in C_k(u,v). A graph G is k∗-connected if there exists a k∗-container between any two vertices. An m-regular graph G is super-connected if G is k∗-connected for any k with 1?k?m. In this paper, we prove that the recursive circulant graphs G(2^m,4), proposed by Park and Chwa [Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m≠2.     

Maximum induced subgraph of a recursive circulant

The recursive circulant RC(n²,4) enjoys several attractive topological properties. Let max_?G(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. In this paper, we show that , where p₀>p₁>?>pr are nonnegative integers defined by . We then apply this formula to find the bisection width of RC(n²,4). The conclusion shows that, as n-dimensional cube, RC(n²,4) enjoys a linear bisection width.     

On the partition dimension of a class of circulant graphs

For a vertex v   of a connected graph G(V,E)$G(V,E)$ and a subset S of V, the distance between a vertex v and S   is defined by d(v,S)=min{d(v,x):x∈S}$d(v,S)=\min \{d(v,x):x\in S\}$. For an ordered k  -partition π={_S1,_S2…_Sk}$\pi =\{S_1,S_2\dots S_k\}$ of V, the partition representation of v with respect to π is the k  -vector r(v|π)=(d(v,_S1),d(v,_S2)…d(v,_Sk))$r(v|\pi )=(d(v,S_1),d(v,S_2)\dots d(v,S_k))$. The k-partition π is a resolving partition if the k  -vectors r(v|π)$r(v|\pi )$, v∈V(G)$v\in V(G)$ are distinct. The minimum k for which there is a resolving k-partition of V is the partition dimension of G. Salman et al. [1] in their paper which appeared in Acta Mathematica Sinica, English Series   proved that partition dimension of a class of circulant graph G(n,±{1,2})$G(n,\pm \{1,2\})$, for all even n?6$n?6$ is four. In this paper we prove that it is three.     

On the number of spanning trees of circulant graphs

In this paper, we derive a simple formula for the number of spanning trees of the circulant graphs. Some special cases of the circulant graphs are also taken into account.     

A sufficient condition for pancyclic graphs

In 2005, Rahman and Kaykobad proved that if G is a connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for each pair x, y of distinct nonadjacent vertices in G, where d(x,y) is the length of a shortest path between x and y in G, then G has a Hamiltonian path [Inform. Process. Lett. 94 (2005) 37–41]. In 2006 Li proved that if G is a 2-connected graph of order n3 such that d(x)+d(y)+d(x,y)n+2 for each pair x,y of nonadjacent vertices in G, then G is pancyclic or G=K_n/2,n/2 where n4 is an even integer [Inform. Process. Lett. 98 (2006) 159–161]. In this work we prove that if G is a 2-connected graph of order n such that d(x)+d(y)+d(x,y)n+1 for all pairs x, y of distinct nonadjacent vertices in G, then G is pancyclic or G belongs to one of four specified families of graphs.     

网络拓扑的超能整循环图构造

循环图是一类重要的网络拓扑结构图,在并行计算和分布计算中发挥重要作用。图[G]的能量[E(G)]定义为图的特征值的绝对值之和。具有[n]个顶点的图[G]称为超能图如果图[G]的能量[E(G)>2n-2]。一个图称为循环图,若它是循环群上的Cayley图,即它的邻接矩阵是一个循环矩阵;整循环图是指循环图的特征值全为整数。借助Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性。利用Cartesian积图给出了一个构造超能整循环图的方法。     

Honeycomb toroidal graphs are Cayley graphs

There is a particular family of trivalent vertex-transitive graphs that have been called generalized honeycomb tori by some and brick products by others. They have been studied as hexagonal embeddings on the torus as well. We show that all these graphs are Cayley graphs on generalized dihedral groups.     

Conditional matching preclusion for the arrangement graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper we find this number and classify all optimal sets for the arrangement graphs, one of the most popular interconnection networks.     

Edge-bipancyclicity of star graphs with faulty elements

In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph S_n. Given a set F comprised of faulty vertices and/or edges in S_n with |F|≤n−3 and any fault-free edge e in S_n−F, we show that there exist cycles of every even length from 6 to n!−2|F_v| in S_n−F containing e, where n≥3. Our result is optimal because the star graph is both bipartite and regular with the common degree n−1. The length of the longest fault-free cycle in the bipartite S_n is n!−2|F_v| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!−2|F_v|+2 to n!−2|F_v| can be embedded.     

A note about some properties of BC graphs

BC graphs is an important class of hypercube-like interconnection networks. In this paper, some properties—vertex-pancyclicity, super-connectivity and the maximum number of edges joining vertices are studied.     

Super p-restricted edge connectivity of line graphs

Super restricted connectivity and super restricted edge connectivity are more refined network reliability indices than connectivity and edge connectivity. In this paper, we first introduce the concepts of super restricted connectivity and super restricted edge connectivity and then give a property of graphs with equal p-restricted edge connectivity and 1-p-restricted connectivity. Applying this property, we show a sufficient condition for a line graph to be super p-restricted edge-connected and a relationship between super 1-p-restricted connected graphs and super p-restricted edge-connected graphs.     

Conditional connectivity of Cayley graphs generated by transposition trees

Given a graph G and a non-negative integer h, the Rh-(edge)connectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has minimum degree at least h. Similarly, given a non-negative integer g, the g-(edge)extraconnectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has more than g vertices. In this paper, we determine R₂-(edge)connectivity and 2-extra(edge)connectivity of Cayley graphs generated by transposition trees.     

One conjecture of bubble-sort graphs

The bubble-sort graph is an important interconnection network designed from Cayley graph model. One conjecture is proposed in Shi and Lu (2008) [10] as follows: for any integer n?2, if n is odd then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles; if n is even then bubble-sort graph Bn is a union of edge-disjoint hamiltonian cycles and its perfect matching that has no edges in common with the hamiltonian cycles. In this paper, we prove that conjecture is true for n=5,6.     

Edge-fault-tolerant pancyclicity and bipancyclicity of Cartesian product graphs with faulty edges

Let r≥ 4 be an even integer. Graph G is r-bipancyclic if it contains a cycle of every even length from r to $2\lfloor \frac{n(G)}{2}\rfloor$, where $n(G)$ is the number of vertices in G. A graph G is r-pancyclic if it contains a cycle of every length from r to $n(G)$, where $r\ge 3$. A graph is k-edge-fault Hamiltonian if, after deleting arbitrary k edges from the graph, the resulting graph remains Hamiltonian. The terms k-edge-fault r-bipancyclic and k-edge-fault r-pancyclic can be defined similarly. Given two graphs G and H, where $n(G)$, $n(H)\ge$ 9, let $k_1$, $k_2\ge 5$ be the minimum degrees of G and H, respectively. This study determined the edge-fault r-bipancyclic and edge-fault r-pancyclic of Cartesian product graph $G\times H$ with some conditions. These results were then used to evaluate the edge-fault pancyclicity (bipancyclicity) of ${\mathit{NQ}}_{m_r,\dots ,m_1}$ and ${\mathit{GQ}}_{m_r,\dots ,m_1}$.     

Distance monotonicity and a new characterization of Hamming graphs

Hamming graphs are simply Cartesian products of complete graphs. Several characterizations of these graphs involve the notion of intervals in a graph and related topics. The notion of interval distance monotonicity has already been used in order to obtain a characterization of hypercubes. Here, we revisit this notion and use it to obtain a new characterization of Hamming graphs by performing a combination of the hypercube characterization and the interval hypercube characterization.     

Feedback vertex sets in star graphs

In a graph G=(V,E), a subset F⊂V(G) is a feedback vertex set of G if the subgraph induced by V(G)?F is acyclic. In this paper, we propose an algorithm for finding a small feedback vertex set of a star graph. Indeed, our algorithm can derive an upper bound to the size of the feedback vertex set for star graphs. Also by applying the properties of regular graphs, a lower bound can easily be achieved for star graphs.     

Efficient dominating sets in circulant graphs with domination number prime

Cayley graphs of finite cyclic group ${\mathbb{Z}}_n$ are called circulant graphs and denoted by $\mathrm{Cay}({\mathbb{Z}}_n,S)$. For $\mathrm{Cay}({\mathbb{Z}}_n,S)$ with $\frac{n}{|S|+1}$ prime, we give a necessary and sufficient condition for the existence of efficient dominating sets and characterize completely all its efficient dominating sets.     

Linearly many faults in Cayley graphs generated by transposition trees

We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices.     

Embedding of special classes of circulant networks,hypercubes and generalized Petersen graphs

Hypercubes are a very popular model for parallel computation because of their regularity and the relatively small number of interprocessor connections. In this paper, we present an algorithm for embedding special class of circulant networks into their optimal hypercubes with dilation 2 and prove its correctness. Also, we embed special class of circulant networks into special class of generalized Petersen graphs with dilation 2 and vice versa.