2
$\begingroup$

If $\ X\ $ is a set, we let $\ \binom X2\,=\, \big\{\{a,b\}: a \neq b \in X \big\}.\ $ Given a simple, undirected graph $\ G=(V,E),\ $ we let $\ \delta(G)\ $ be its minimum degree, and $\ \Delta(G)\ $ its maximum degree. We say that $\ G\ $ is self-complementary if $\ G \cong \bar{G}\ $ where $\ \bar{G} = \left(V, \binom V2\setminus E\right)$.

Given $\ N\in\mathbb{N},\ $ is there a self-complementary graph $\ G\ $ with $\ \Delta(G) \geq N\cdot \delta(G)\,$?

$\endgroup$
1
  • 2
    $\begingroup$ For $n=4,5,8,9,12,13,16$ there is a self-complementary graph with $\delta=1$ and (therefore) $\Delta=n-2$. It shouldn't be hard to identify the general construction. Tomorrow, if nobody gets in first. $\endgroup$ Commented Apr 14, 2020 at 12:13

2 Answers 2

7
$\begingroup$

Self-complementary graphs exist if $n\equiv0,1\pmod 4$.

Take a self-complementary graph $G$ with $n$ vertices. Append to it a path $u{-}v{-}w{-}x$ of 4 vertices and join $v$ and $w$ to all of $G$. Now you have a self-complementary graph with $n+4$ vertices, $\delta=1$ and $\Delta=n+2$. This gives all sizes from 4 onwards.

$\endgroup$
3
$\begingroup$

This is really just a comment on Brendan McKay's answer, but I'd like to point out that there are also infinite self-complementary graphs with minimum degree $\delta=1$. Here are two different ways to see that.

I. From the existence of arbitrarily large finite self-complementary graphs with $\delta=1$ it follows, by the compactness theorem of first-order logic, that there is an infinite self-complementary graph with $\delta=1$. This is because the class of structures $(V,E,f)$, where $(V,E)$ is a graph with $\delta=1$ and $f:V\to V$ is an isomorphism from that graph to its complement, can be characterized by first-order sentences.

II. Start with any self-complementary infinite graph $G$. (For example the random infinite graph or Rado graph is self-complementary; of course every vertex of Rado's graph has infinite degree.) Now you can construct a self-complementary infinite graph with $\delta=1$ by appending to $G$ a $4$-point path, as in Brendan McKay's answer.

$\endgroup$

You must log in to answer this question.

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