6
$\begingroup$

Take the cycle on $5$ vertices, $C_5$. The clique and independence number of this graph are both $2$. If we add any edge to $C_5$ we get a triangle. Meanwhile, if we remove any edge we get a triangle in the complement.

So whatever edge we change, we get either an increase (from $2$ to $3$) of the clique number, or of the independence number. Is $C_5$ the only graph with this property, or are there others?

$\endgroup$
1
  • $\begingroup$ Interesting question. Trivially, any complete graph can only be changed by removing an edge and thus changing the independence number. (Similarly in complement, an edgeless graph) $\endgroup$
    – Joffan
    Commented Aug 16, 2017 at 15:58

2 Answers 2

3
$\begingroup$

Here are a few graphs with your property.

Let $\alpha(G),\ \omega(G),$ and $n(G)$ denote the independence number, the clique number, and the order of a (finite) graph $G.$

The Ramsey number $R(s,t)$ is defined by the property that $R(s,t)-1$ is the maximum possible order of a graph $G$ with $\alpha(G)\lt s$ and $\omega(G)\lt t.$ Thus, by definition (and by Ramsey's theorem which tells us that $R(s,t)$ exists), there is a graph $G_{s,t}$ (not necessarily unique) such that $\alpha(G_{s,t})=s-1,\ \omega(G_{s,t})=t-1,$ and $n(G_{s,t})=R(s,t)-1.$ In some cases such a graph $G_{s,t}$ will have your property:

Lemma. If $R(s,t)=R(s-1,t)+R(s,t-1),$ then $G_{s,t}$ has the property that removing any edge will increase the independence number, while adding any edge will increase the clique number.

Proof. The graph $G=G_{s,t}$ is regular of degree $R(s,t-1)-1.$ Adding an edge $uv$ will create a vertex $v$ of degree $R(s,t-1).$ Since $\alpha(G+uv)\le\alpha(G)\lt s,$ it follows that $v$ is in a $t$-clique of $G+uv,$ and so $\omega(G+uv)\ge t\gt\omega(G).$ Similarly, removing an edge will increase the independence number.

It's a basic lemma in Ramsey theory that the inequality $R(s,t)\le R(s-1,t)+R(s,t-1)$ always holds; it seems that the inequality is usually strict, but the equality cases give us graphs with your property.

Examples:

$R(3,3)=6=3+3=R(2,3)+R(3,2);\ G_{3,3}=C_5.$

$R(n+1,2)=n+1=R(n,2)+R(n+1,1);\ G_{n+1,2}=K_n.$

$R(2,n+1)=n+1=R(2,n)+R(1,n+1);\ G_{2,n+1}=\overline{K_n}.$

$R(3,5)=14=5+9=R(2,5)+R(3,4);$ for $G_{3,5}$ we can take $C_{13}$ and add all chords of length $5.$

$R(4,4)=18=9+9=R(3,4)+R(4,3);$ see this question or any textbook on Ramsey theory.

$\endgroup$
3
$\begingroup$

Nice question! No, this isn't the only nontrivial example. Take $p=13$ and construct the graph whose vertices are the residue classes mod $p$, with an edge between any two whose difference is a quadratic residue. This is well-defined (because $p\equiv 1\pmod 4$, $x-y$ is a quadratic residue if and only if $y-x$ is).

enter image description here

The graph is edge-transitive, since $x\mapsto a^2x+b$ is an automorphism for any $a,b\in \mathbb Z_p$ with $a\neq 0.$ It is also self-complementary (multiply by any quadratic non-residue). Thus it suffices to show that adding some edge (say $0$-$2$) increases the clique number. The clique number is $3$: the only vertices which form a triangle with $0$-$1$ are $10$ and $4$, and these four vertices don't form a clique, so $0$-$1$ isn't in a clique of size $4$ (and by transitivity neither is any other edge). But if $0$-$2$ is added then $12$-$0$-$2$-$3$ is a clique of size $4$.

It may well be that this construction works for any prime $p\equiv 1\pmod 4,$ but I can't see how to prove that.

$\endgroup$
1
  • $\begingroup$ Forgot to point out: $C_5$ is the same construction for $p=5$. $\endgroup$ Commented Aug 22, 2017 at 13:03

You must log in to answer this question.

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