is there a relation between regular graphs and power set graphs?

525 Views Asked by At

The title says it. Let $G(V,E)$ be a $k$-regular graph and $H(\hat{V},\hat{E})$ be the graph of the power set of $[k]$ elements (that is, $H$ resulted from the inclusion relation over the elements of $[k]$) for $k\geq 2$.

Is there any relation between the two? because when $k=3$ (i.e. cubic graph) I see they are isomorphic.

1

There are 1 best solutions below

1
On BEST ANSWER

The class of $k$-regular graphs is, in general, very large. There is not, as you seem to suggest, a single $k$-regular graph for each $k$. For each $k$, the class of $k$-regular graphs includes the power set graph for a set with $k$ elements, but in general this is only one of the many members of the class of all $k$-regular graphs.

Here are some 3-regular graphs with 8 vertices. Only the fourth from the left is the power set graph.

Six 3-regular graphs with 8 vertices

(Image adapted from Wolfram MathWorld.)