Rainbow tetrahedra in Cayley graphs
Italo Jose Dejter · Discussiones Mathematicae Graph Theory · 2015
Let n be the complete undirected Cayley graph of the odd cyclic group Z n . Connected graphs whose vertices are rainbow tetrahedra in n are studied, with any two such vertices adjacent if and only if they share (as tetrahedra) precisely two distinct triangles. This yields graphs G of largest degree 6, asymptotic diameter |V (G)| 1/3 and almost all vertices with degree: (a) 6 in G; (b) 4 in exactly six connected subgraphs of the (3, 6, 3, 6)-semiregular tessellation; and (c) 3 in exactly four connected subgraphs of the {6, 3}-regular hexagonal tessellation. These vertices have as closed neighborhoods the union (in a fixed way) of closed neighborhoods in the ten respective resulting tessellations.