Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.     

On the chromatic number of circulant graphs

Given a set D of a cyclic group C, we study the chromatic number of the circulant graph G(C,D) whose vertex set is C, and there is an edge ij whenever i−j∈D∪−D. For a fixed set D={a,b,c:a<b<c} of positive integers, we compute the chromatic number of circulant graphs G(Z_N,D) for all N≥4bc. We also show that, if there is a total order of D such that the greatest common divisors of the initial segments form a decreasing sequence, then the chromatic number of G(Z,D) is at most 4. In particular, the chromatic number of a circulant graph on Z_N with respect to a minimum generating set D is at most 4. The results are based on the study of the so-called regular chromatic number, an easier parameter to compute. The paper also surveys known results on the chromatic number of circulant graphs.     

Cyclic orthogonal double covers of 4-regular circulant graphs

An orthogonal double cover (ODC) of a graph H is a collection G={G_v:v∈V(H)} of |V(H)| subgraphs of H such that every edge of H is contained in exactly two members of G and for any two members G_u and G_v in G, |E(G_u)∩E(G_v)| is 1 if u and v are adjacent in H and it is 0 if u and v are nonadjacent in H. An ODC G of H is cyclic (CODC) if the cyclic group of order |V(H)| is a subgroup of the automorphism group of G. In this paper, we are concerned with CODCs of 4-regular circulant graphs.     

Well-covered circulant graphs

A graph is well-covered if every independent set can be extended to a maximum independent set. We show that it is co-NP-complete to determine whether an arbitrary graph is well-covered, even when restricted to the family of circulant graphs. Despite the intractability of characterizing the complete set of well-covered circulant graphs, we apply the theory of independence polynomials to show that several families of circulants are indeed well-covered. Since the lexicographic product of two well-covered circulants is also a well-covered circulant, our partial characterization theorems enable us to generate infinitely many families of well-covered circulants previously unknown in the literature.     

The asymptotic number of spanning trees in circulant graphs

Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s₁,i±s₂,…,i±s_k where all the operations are . We give a closed formula for the asymptotic limit as a function of s₁,s₂,…,s_k. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting s_i, d_i and e_i be arbitrary integers, and examining

     

Further analysis of the number of spanning trees in circulant graphs

Let 1?s₁<s₂<?<s_k?⌊n/2⌋ be given integers. An undirected even-valent circulant graph, has n vertices 0,1,2,…, n-1, and for each and j(0?j?n-1) there is an edge between j and . Let stand for the number of spanning trees of . For this special class of graphs, a general and most recent result, which is obtained in [Y.P. Zhang, X. Yong, M. Golin, [The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]], is that where a_n satisfies a linear recurrence relation of order 2^s_k-1. And, most recently, for odd-valent circulant graphs, a nice investigation on the number a_n is [X. Chen, Q. Lin, F. Zhang, The number of spanning trees in odd-valent circulant graphs, Discrete Math. 282 (2004) 69-79].In this paper, we explore further properties of the numbers a_n from their combinatorial structures. Comparing with the previous work, the differences are that (1) in finding the coefficients of recurrence formulas for a_n, we avoid solving a system of linear equations with exponential size, but instead, we give explicit formulas; (2) we find the asymptotic functions and therefore we ‘answer’ the open problem posed in the conclusion of [Y.P. Zhang, X. Yong, M. Golin, The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]. As examples, we describe our technique and the asymptotics of the numbers.     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

Testing set proportionality and the Ádám isomorphism of circulant graphs

Given two k element subsets , we give a quasi-linear algorithm to either find such that S=λT or prove that no such λ exists.This question is closely related to isomorphism testing of circulant graphs and has recently been studied in the literature.     

Path factors and parallel knock-out schemes of almost claw-free graphs

An H₁,{H₂}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H₁ and all other components (if there are any) isomorphic to the graph H₂. We completely characterise the class of connected almost claw-free graphs that have a P₇,{P₂}-factor, where P₇ and P₂ denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n^5.376) time algorithm for claw-free graphs on n vertices).     

Ternary codes from graphs on triples

For a set Ω of size n≥7 and Ω^{3} the set of subsets of Ω of size 3, we examine the ternary codes obtained from the adjacency matrix of each of the three graphs with vertex set Ω^{3}, with adjacency defined by two vertices as 3-sets being adjacent if they have zero, one or two elements in common, respectively.     

Projective two-weight codes with small parameters and their corresponding graphs

Projective two-weight codes with relatively small parameters are enumerated up to equivalence. Some properties of codes and related strongly-regular graphs are presented. I. Bouyukliev was partially supported by the Bulgarian National Science Fund under Contract MM1304/2003. J.Winne thanks the Fund for Scientific Research—Flanders (Belgium) for a Research grant.     

Bicyclic graphs with exactly two main eigenvalues

An eigenvalue of a graph G is called a main eigenvalue if it has an eigenvector the sum of whose entries is not equal to zero, and it is well known that a graph has exactly one main eigenvalue if and only if it is regular. In this work, all connected bicyclic graphs with exactly two main eigenvalues are determined.     

Strongly regular graphs associated with ternary bent functions

We prove a new characterization of weakly regular ternary bent functions via partial difference sets. Partial difference sets are combinatorial objects corresponding to strongly regular graphs. Using known families of bent functions, we obtain in this way new families of strongly regular graphs, some of which were previously unknown. One of the families includes an example in [N. Hamada, T. Helleseth, A characterization of some {3v₂+v₃,3v₁+v₂,3,3}-minihypers and some [15,4,9;3]-codes with B₂=0, J. Statist. Plann. Inference 56 (1996) 129-146], which was considered to be sporadic; using our results, this strongly regular graph is now a member of an infinite family. Moreover, this paper contains a new proof that the Coulter-Matthews and ternary quadratic bent functions are weakly regular.     

Error bounds for a class of subdivision schemes based on the two-scale refinement equation

Subdivision schemes are iterative procedures for constructing curves and constitute fundamental tools in computer aided design. Starting with an initial control polygon, a subdivision scheme refines the values computed in the previous step according to some basic rules. The scheme is said to be convergent if there exists a limit curve. The computed values define a control polygon in each step. This paper is devoted to estimating error bounds between the limit curve and the control polygon defined after k subdivision stages. In particular, a stop criterion of convergence is obtained. The refinement rules considered in the paper are widely used in practice and are associated with the well known two-scale refinement equation including as particular examples the schemes based on Daubechies’ filters. Our results generalize the previous analysis presented by Mustafa et al. in [G. Mustafa, F. Chen, J. Deng, Estimating error bounds for binary subdivision curves/surfaces, J. Comput. Appl. Math. 193 (2006) 596-613] and [G. Mustafa and M.S. Hashmi Subdivision depth computation for n-ary subdivision curves/surfaces, Vis. Comput. 26 (6-8) (2010) 841-851].     

Complete weight enumerators of a class of linear codes with two weights

In this paper, a class of $p$-ary linear codes with two weights is constructed by using the properties of cyclotomic classes of ${\mathbb{F}}_{p^2}^1$. The complete weight enumerators of these linear codes are also determined. In some cases, they are optimal and can be employed to obtain secret sharing schemes with interesting access structures and asymptotically optimal systematic authentication codes.