GCD-graphs and NEPS of complete graphs

Walter Klotz, Torsten Sander


A gcd-graph is a Cayley graph over a finite abelian group defined by greatest common divisors. Such graphs are known to have integral spectrum. A non-complete extended p-sum, or NEPS in short, is well-known general graph product. We show that the class of gcd-graphs and the class of NEPS of complete graphs coincide. Thus, a relation between the algebraically defined Cayley graphs and the combinatorially defined NEPS of complete graphs is established. We use this link to show that gcd-graphs have a particularly simple eigenspace structure, to be precise, that every eigenspace of the adjacency matrix of a gcd-graph has a basis with entries − 1, 0, 1 only.


Integral graphs, Cayley graphs, graph products

Full Text:


DOI: https://doi.org/10.26493/1855-3974.309.129

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications