Skip to main content
edited body
Source Link
bof
  • 13.4k
  • 2
  • 43
  • 66

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?

What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complimentarycomplementary graph on $n$ vertices.

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?

What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complimentary graph on $n$ vertices.

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?

What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complementary graph on $n$ vertices.

Source Link
Aaron Hill
  • 303
  • 2
  • 7

How many vertices can a self-complementary graph have?

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?

What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complimentary graph on $n$ vertices.