Enumerating cliques in direct product graphs

DOI10.4310/JOC.2020.V11.N2.A6zbMATH Open1430.05052arXiv1707.05406WikidataQ126355357 ScholiaQ126355357MaRDI QIDQ2288018FDOQ2288018

Authors: Colin Defant 

Publication date: 16 January 2020

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: The unitary Cayley graph of $mathbbZ/nmathbbZ$, denoted $G_{mathbbZ/nmathbbZ}$, is the graph with vertices $0,1,ldots,$ $n-1$ in which two vertices are adjacent if and only if their difference is relatively prime to $n$. These graphs are central to the study of graph representations modulo integers, which were originally introduced by ErdH{o}s and Evans. We give a brief account of some results concerning these beautiful graphs and provide a short proof of a simple formula for the number of cliques of any order $m$ in the unitary Cayley graph $G_{mathbbZ/nmathbbZ}$. This formula involves an exciting class of arithmetic functions known as Schemmel totient functions, which we also briefly discuss. More generally, the proof yields a formula for the number of cliques of order $m$ in a direct product of balanced complete multipartite graphs.

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

Recommendations

• Unitary Cayley graphs of Dedekind domain quotients
• scientific article; zbMATH DE number 798645
• Unit and unitary Cayley graphs for the ring of Eisenstein integers modulo \(n\)
• Some properties of unitary Cayley graphs
• Domination parameters of the unitary Cayley graph of \(\mathbb{Z}/n \mathbb{Z} \)

zbMATH Keywords

cliqueunitary Cayley graphcomplete multipartite graphSchemmel totient functiondirect product graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Cited In (3)

• Isoperimetry, stability, and irredundance in direct products
• Unitary Cayley graphs of Dedekind domain quotients
• Clique immersion in graph products

This page was built for publication: Enumerating cliques in direct product graphs

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