3
$\begingroup$

A graph is perfect if it has no induced subgraph that is either an odd cycle (other than a triangle) or a complement thereof (note that the class of perfect graphs is closed under graph complement). A graph is self-complementary if it is isomorphic to its complement.

Question: How many self-complementary graphs are perfect? More precisly, which of the following cases are we in?:

  1. most self-complementary graphs are perfect in the sense that one can classify or concisely characterize the self-complementary graphs that are not perfect.
  2. most self-complementary graphs are not perfect in the sense that one can classify or concisely characterize the self-complementary perfect graphs.
  3. There is no significant relation between the self-complementary graphs and the perfect graphs.

Note that the self-complementary perfect graphs are exactly the self-complementary graphs that do not contain odd induced cycles other than triangles.

Some examples of self-complementary perfect graphs are: the single vertex graph, the path of length three, and (I believe) $C_3\times C_3$. More examples can be found in this list of small self-complementary graphs.

So far I am not aware of a way to generate an infinite family of self-complementary graphs that are either perfect or not perfect.

Improve this question
$\endgroup$
3
  • $\begingroup$ Every self-complementary graph of order 8 is perfect. And I can't prove it, but it seems every self-complementary graph of even order is perfect. $\endgroup$ Commented Aug 19, 2024 at 11:51
  • $\begingroup$ There are even self-complementary non-perfect graphs. Take for example 5 copies of $(\{1, 2, 3, 4\}, \{\{1, 2\}, \{2, 3\}, \{3, 4\}\})$ and call them $G_1, G_2, G_3, G_4, G_5$. Now connect all vertices in $G_i$ with all vertices in $G_{i+1 \text{ mod } 5}$ for all $i \in \{1,2,3,4,5\}$. This gives a self-complementary graph of order 20 with an induced cycle of length 5. $\endgroup$ Commented Aug 19, 2024 at 17:42
  • $\begingroup$ @1001 My bad, there actually is one non-perfect self-complementary graph on 8 vertices. It can be constructed by connecting ends of one $P_4$ with every vertex of another $P_4$. Now, if we have $m$ disjoint $P_4$ we can pairwise connect them in a way that creates a self-complementary graph on $4m$ vertices. If we never connect ends of one $P_4$ with every vertex of another $P_4$, then it seems the graph is perfect. However, I can be wrong about isomorphisms of self-complementary graphs. $\endgroup$ Commented Aug 19, 2024 at 22:45

1 Answer 1

Reset to default
2
$\begingroup$

I think this gives an infinite family of self-complementary perfect graphs:

$V = \{1,\ldots, 4n\}$

$E = \{\{i, j + 2n\} \mid i, j \in \{1, \ldots, 2n\} \wedge i \equiv j \mod 2 \} \cup \{\{i, j\} \mid i, j \in \{1, \ldots, 2n\}\wedge i \neq j\}$

Note that it is self-complementary (by mapping $i$ to $2n + i$ and $2n + i$ to $2n + 1 - i$ for all $i \in \{1 \ldots 2n\}$) and perfect (every cycle of length at least 5 must have three vertices in $\{1, \ldots, 2n\}$ which induce a triangle; similarly the graph contains no complement of a cycle of length at least 5 as an induced subgraph).

For a imperfect self-complementary graph, I think the following works:

$V = \{0,\{(i, j) \mid i \in \{1, 2\} \wedge j \in \{1,\ldots, 2n\}\}$

$E = \{\{0, (1, 1)\}, \{0, (1, 2n)\}\} \cup \{\{(1, i), (1, i+1)\}\mid i \in \{1, \ldots 2n - 1\}\}\cup \{\{0, (2, i)\} \mid i \in \{2, \ldots, 2n - 1\}\} \cup \{\{(2, i), (2, j)\}\mid i, j \in \{1, \ldots 2n\}\wedge |i - j| \neq 1\} \cup \{\{(1, i), (2, j)\}\mid i, j \in \{1, \ldots 2n\}\wedge i \equiv j \mod 2\}$

Note that it is self-complementary (by mapping $(1, i)$ to $(2, i)$ and $(2, i)$ to $(1, 2n + 1 - i)$) and imperfect ($\{0\} \cup \{(1, i) \mid i \in \{1, \ldots, 2n\}\}$ induces an odd cycle).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your answer! Since I don't know how you came up with your examples, let me ask: do you feel like you could build many more like this that do not obviously belong to any large family? $\endgroup$ Commented Aug 3, 2023 at 19:06
  • $\begingroup$ Not sure, but I think so. For the first one I started with a k-clique and its complement and wanted to include them in a k-partite self-complementary graph (because that is an equivalent definition of perfect). For the second one I started with an odd cycle and its complement and wanted to include them in a self-complementary graph. There are probably many more ways to do so, especially when adding more vertices. These were just the simplest I could come up with. $\endgroup$ Commented Aug 3, 2023 at 19:44

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.