On congruence in Z^ n and the dimension of a multidimensional circulant

DOI10.1016/0012-365X(94)00361-LMaRDI QIDQ1894764zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 27 November 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1209.4984

zbMATH Keywords

abelian groupsCayley digraphCayley graphcirculantcongruencedimensionintegral matrixmultidimensional circulants

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: From a generalization to $Z^n$ of the concept of congruence we define a family of regular digraphs or graphs called multidimensional circulants, which turn out to be Cayley (di)graphs of Abelian groups. This paper is mainly devoted to show the relationship between the Smith normal form for integral matrices and the dimensions of such (di)graphs, that is the minimum ranks of the groups they can arise from. In particular, those 2-step multidimensional circulants which are circulants, that is Cayley (di)graphs of cyclic groups, are fully characterized. In addition, a reasoning due to Lawrence is used to prove that the cartesian product of $n$ circulants with equal number of vertices $p>2$, $p$ a prime, has dimension $n$.

Review text

If \(\mathbb{Z}^n\) denotes integer vectors and \(M\) is an integral matrix, then \(\mathbb{Z}^n/ M\mathbb{Z}^n\) is the abelian group of congruence classes modulo \(M\) (that is, modulo the lattice of integer linear combinations of the columns of \(M\)). Selecting a subset \(A\) of this group defines a Cayley (di)graph, whose vertices are the elements of the group, with edges joining each vertex \(x\) to \(x+a\) for \(a\in A\). If \(n=1\) the group is cyclic and the Cayley graph is called a circulant. In this paper the author studies multidimensional circulants (Cayley digraphs of abelian groups) in terms of integral matrices \(M\) and the Smith normal form of \(M\). Isomorphic graphs may arise from matrices of more than one size, and the minimum such \(n\) is called the dimension of the multidimensional circulant. This equals the minimum rank (minimum number of generators) of the (abelian) groups for which the graph is a Cayley digraph. The author proves that the cartesian product of \(n\) circulants of order \(p\) has dimension \(n\), for primes \(p>2\) (unlike the case \(p=2\), as Leighton showed in 1983 that the \(n\)-dimensional hypercube graph has dimension \(\lfloor (n+ 1)/2 \rfloor\) in this sense). For 2-step multidimensional circulants (where \(|A|=2\) so the dimension is at most two), the author proves a characterization of precisely when the dimension is one (in terms of the \(n\times n\) matrix \(M\) and the two vectors in \(A\)).

Recommendations

• Isomorphisms of circulant digraphs
• Cayley graphs of more than one abelian group
• scientific article; zbMATH DE number 4135988
• Undirected loop networks
• On digraphs with circulant adjacent matrices

Cites work

• Circulants and the Characterization of Vertex-Transitive Graphs
• Circulants and their connectivities
• Congruences in \({\mathbb{Z}}^ n\), finite Abelian groups and the Chinese remainder theorem
• Double commutative-step digraphs with minimum diameters
• Graphs with circulant adjacency matrices
• scientific article; zbMATH DE number 4201663 (Why is no real title available?)
• scientific article; zbMATH DE number 4004216 (Why is no real title available?)
• scientific article; zbMATH DE number 4057538 (Why is no real title available?)
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• scientific article; zbMATH DE number 3781457 (Why is no real title available?)
• Isomorphism of circulant graphs and digraphs
• Isomorphism problem for a special class of graphs
• Isomorphisms of Cayley multigraphs of degree 4 on finite Abelian groups
• On a Class of Fixed-Point-Free Graphs
• Point-symmetric graphs with a prime number of points
• Two theorems on matrices

Cited in

(13)

• New dense families of triple loop networks
• Endo-circulant digraphs: Connectivity and generalized cycles
• On the nonmonotonicity of \((|Im(z^n)|)\)
• Triple loop networks with small transmission delay
• On the critical group of the \(n\)-cube
• New Moore-like bounds and some optimal families of abelian Cayley mixed graphs
• Identifying codes of degree 4 Cayley graphs over abelian groups
• Abelian Cayley digraphs with asymptotically large order for any given degree
• On rational matrix exact covering systems of \(\mathbb{Z}^n\) and its applications to Ramanujan's forty identities
• The dilating method to obtain dense Cayley digraphs on finite abelian groups
• A geometric approach to dense Cayley digraphs of finite abelian groups
• Parallel optimization and performance tuning on a Kunpeng cluster of genetic algorithm for synthesis of circulant networks
• An improved Moore bound and some new optimal families of mixed abelian Cayley graphs

This page was built for publication: On congruence in \(\mathbb{Z}^ n\) and the dimension of a multidimensional circulant

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894764)