A Theory of Cartesian Product and Factorization of Circulant Graphs

We determine when the Cartesian product of two circulant graphs is also a circulant graph. This leads to a theory of factorization of circulant graphs. 1. Introduction Just as integers can be factored into prime numbers, there are many results on decomposition of structures throughout mathematics [1]. The standard products—Cartesian, lexicographic, tensor, and strong—all belong to a class of products introduced by Imrich and Izbicki [2] and called -products [3]. Properties of circulant graphs are extensively studied by many authors [2–19] and products of graphs have been studied for almost 50 years now. Sabidussi [20] proved that every (nonnull) graph is the unique product of prime graphs. Broere and Hattingh [3] established that the lexicographic product of two circulant graphs is again circulant. They and Sanders and George [12] established that this is not the case with other products. Alspach and Parsons [5] introduced metacirculant graphs as a generalization of circulant graphs and characterized metacirculant graphs in terms of their automorphism groups. Sanders [11] established that any -product of two circulant graphs is always a metacirculant graph with parameters that are easily described in terms of the product graphs and also established that any metacirculant graph with the appropriate structure is isomorphic to the -product of a pair of circulant graphs. After a graph is identified as a circulant graph, its properties can be derived easily. This paper gives a detailed study of Cartesian product and factorization of circulant graphs similar to the theory of product and factorization of natural numbers. For more details on circulant graphs, see [9, 10]. Let be a positive integer and let be a subset of . The circulant graph has vertices with adjacent to for each , subscript addition taken modulo . When discussing circulant graphs, we will often assume, without further comment, that the vertices are the corners of a regular -gon, labeled clockwise. Circulant graphs and are shown in Figures 1(a) and 1(b). Figure 1: (a) . (b) . When , edge is taken as a single edge while considering the degree of a vertex, but as a double edge while counting number of edges or cycles in [3, 6–10, 13, 14, 17, 18, 21]. We generally write for and for , the null graph on vertices. Note that if a graph is circulant, then its adjacency matrix is circulant. It follows that if the first row of the adjacency matrix of a circulant graph is , then and =？ , . Throughout this paper, for a set denotes where ; we consider only connected circulant graphs of finite order greater