Rainbow Tetrahedra in Cayley Graphs

摘要

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)-semi- regular tessellation; and (c) 3 in exactly four connected subgraphs of the {6, 3}-regular hexagonal tessellation. These vertices have as closed neigh- borhoods the union (in a fixed way) of closed neighborhoods in the ten respective resulting tessellations.