2
$\begingroup$

For any set $X$ let $[X]^2 = \big\{\{a,b\}: a\neq b\in X\big\}$. We say that a graph $G$ is self-complementary if $G\cong \bar{G}$ where $\bar{G} = (V, [V]^2\setminus E)$.

Given an infinite cardinal $\kappa$, is there a collection ${\cal C}$ of pairwise non-isomorphic self-complementary graphs on the vertex set $\kappa$ such that ${\cal C} = 2^\kappa$?

$\endgroup$
3
  • 1
    $\begingroup$ Do you have a family of $2^\kappa$ many pairwise no-isomorphic graphs on every cardinal $\kappa$? $\endgroup$ Commented Apr 16, 2020 at 21:10
  • $\begingroup$ Yes, see this thread. $\endgroup$ Commented Apr 17, 2020 at 8:22
  • $\begingroup$ Thank you! More precisely, one should look at this answer of @Wojowu: mathoverflow.net/a/281040/61536 $\endgroup$ Commented Apr 17, 2020 at 9:39

1 Answer 1

5
$\begingroup$

As you know, there are $2^\kappa $ nonisomorphic graphs of cardinality $\kappa$ for every infinite cardinal $\kappa$. (In fact there are $2^\kappa$ nonisomorphic trees of cardinality $\kappa$, see this answer.) I will show how to turn them into nonisomorphic self-complementary graphs of the same cardinality.

Given a graph $G$ of cardinality $\kappa$, let $G_1,G_2$ be two copies of $G$, and let $H_1,H_2$ be two copies of the complement of $G$, and add edges joining all vertices of $G_1$ to all vertices of $H_1$, all vertices of $H_1$ to all vertices of $H_2$, and all vertices of $H_2$ to all vertices of $G_2$. (In other words, we take the self-complementary graph $P_4$ and replace the end vertices with copies of $G$, the internal vertices with copies of $\overline G$.) In this way we get a self-complementary graph $S$ of cardinality $\kappa$.

To recover $G$ from $S$, choose a vertex $y_0$ of eccentricity $3$ and let $X$ be the set of all vertices $x$ such that $d(x,y_0)=3$; then the subgraph of $S$ induced by $X$ is a copy of $G$.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.