I have recently encountered a family of graphs defined like this: given a set $G$, the elemental graph of $G$ has nodes from $G\times 2^G$ and an edge between $\langle g_1, U_1\rangle$ and $\langle g_2, U_2\rangle$ if and only if $g_1\in U_2$ and $g_2 \in U_1$.

The graph depends only on the number of elements of $G$. For $G=1, 2, 3$, the graphs look like this:

  1. $G=1$.
    enter image description here

  2. $G=2$.
    enter image description here

  3. $G=3$.
    enter image description here
    (In this final image, self-loops have been replaced with white dots for simplicity. The shaded regions indicate regions with the same first component $g \in G$, and the colors are for visual clarity but convey no meaning.)

These graphs have interesting properties such as, if we exclude the isolated $\varnothing$ nodes, having a graph diameter of 3 regardless of how large $|G|>1$ is. I'm wondering if these graphs have come up in other contexts.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.