1
$\begingroup$

I am attempting a list of graph classes that are self-complementary. So far the best known ones seem to be: (1) Self-complementary graphs; (2) Perfect Graphs and several subclasses of these graphs: cograph, split, threshold, permutation; (3) Symmetry type graphs such as Vertex-transitive, Strongly Regular, Regular, Paley etc. Reconstructible Graphs. (4)...?

Are there any natural examples I could add to the list?

$\endgroup$
1

2 Answers 2

2
$\begingroup$

Generalizing perfect graphs, the class of graphs with no induced $C_5$ is self-complementary. (In general, for any self-complementary family $\mathcal F$ of graphs, the class of graphs with no induced copy of any $F \in \mathcal F$ is self-complementary, but for complicated $\mathcal F$ this looks less natural.)

A bunch of graph classes that can be said to "resemble random graphs" in some way are self complementary. For example:

  • The class of Ramsey graphs (graphs with no homogeneous set of size $C \log n$ or more) is self-complementary. If we relax $C \log n$ to any bound, this is still true, but the class of graphs we get that way is less interesting.
  • The class of $k$-universal graphs (graphs that have every graph of size $k$ as an induced subgraph) is self-complementary.
  • For most definitions of "pseudorandom", the class of pseudorandom graphs should be self-complementary. For example, if we ask that for any two vertex sets $X,Y$, the number of edges between $X$ and $Y$ should be $p|X||Y| \pm O(\sqrt{p n |X||Y|})$, where $p$ is the edge density, we get a self-complementary class of graphs.
  • Paley graphs, which you've mentioned, are a special case of the previous bullet point.
$\endgroup$
1
$\begingroup$

The bull is a self-complementary graph. The bull graph is a graph on 5 vertices, four of which induce a $P_4$ (a,b,c,d) and a fifth vertex adjacent to only b and c. So bull-free graphs are self-complementary.

The intersections of self-complementary classes is also self-complementary. For example, $(C_5$,bull)-free is a self-complementary class. Also the class formed by any class $C \cup C^c$ will be self-complementary. Notably, chordal $\cup$ co-chordal graphs is a self complementary class which includes the chordal graphs yet is a subclass of the weakly chordal graphs.

Weakly chordal graphs are another one that is self-complimentary.

Generalizations of cographs like the $P_4$-sparse graphs and $P_4$-lite graphs are self-complementary, as well as all of the (q,t)-generalizations that characterize a graph by forbidding numbers of $P_4$s.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .