3
$\begingroup$

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.

$\endgroup$

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.