Enumerating cliques in direct product graphs

DOI10.4310/JOC.2020.V11.N2.A6MaRDI QIDQ2288018zbMATH OpenWikidataFDO

Authors Colin Defant

Publication date 16 January 2020

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

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

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)

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.

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} \)

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)