I'm looking for numerical graph invariants that are bounded by a constant either for a graph $G$ or its complement $\bar{G}$. (The complement graph $\bar{G}$ has the same set of vertices as $G$ but the edges are complemented.) More specifically I’m looking for what numerical “Invariant $X$” is out there for which the following statement is true:

“Invariant $X$ is bounded by a constant $c$ either for $G$ or $\bar{G}$”.

One example is diameter $d(G)$ of a graph $G$ where it is known that:

"Either $d(G) \leq 3$ or $d(\bar{G}) \leq 3$"

(Reference: F. Harary, R. W. Robinson: The diameter of a graph and its complement , The American Mathematical Monthly, Vol. 92, No. 3. (Mar., 1985), pp. 211-212”)

My question is what other such numerical graph invariants are out there? I looked at the list of invariants on wikipedia but there was no mention of such bound on their respective pages. Again, all I’m interested is that the condition holds for either $G$ or its complement $\bar{G}$ and not necessarily for both.

  • $\begingroup$ what about (the number of generators) of graph homology or cohomology?Or C* algebraic invariants of the corresponding "graph c* algebras"? $\endgroup$ – Ali Taghavi Feb 7 '16 at 8:04
  • 1
    $\begingroup$ @AliTaghavi The number of generators for the homology group of $G$ is $|E(G)|-|V(G|+1$, so this will be big for either $G$ or $\overline{G}$. $\endgroup$ – Tony Huynh Feb 7 '16 at 13:43
  • $\begingroup$ Well, I should've signed up to mathoverflow before asking the question :) Now I cannot reply to individual comments or accept an answer (because of the 50 reputation score limitation - which is a good thing to eliminate spam). So I'm posting this: - Tony: Thanks for the two examples and spending effort for a proof. - David: Yours is my favorite among all. Especially the connection to Ramsey's theorem is quite interesting. Thank you! - Shahrooz: I was asking for "upper" bounds as Gordon also commented. Thanks for spending time on it. $\endgroup$ – user86410 Feb 8 '16 at 23:27

Let $c(G)$ be the number of connected components of $G$. Then for all graphs $G$, $$ c(G)=1 \text{ or } c(\overline{G})=1. $$

Here is a slightly more interesting family of examples. For a fixed integer $k$, define $d_k(G)$ to be the number of degree-$k$ vertices of $G$.

Claim. For all graphs $G$, $$d_k(G) \leq 2k \text{ or } d_k(\overline{G}) \leq 2k. $$

Proof. Suppose that $G$ contains more than $2k$ degree-$k$ vertices. Let $X$ be a set of degree-$k$ vertices of $G$ with $|X|=2k+1$. Let $N_G(X)$ be the neighbours of $X$ in $G$. Let $Y$ be the set of degree-$k$ vertices in $\overline{G}$. Since the vertices in $V(G) \setminus N_G(X)$ are not adjacent to any vertex in $X$, it follows that $Y \subseteq N_G(X)$. Towards a contradiction, suppose $|Y| \geq 2k+1$. Since $|X|=2k+1$, each vertex in $Y$ must send at least $k+1$ edges (in $G$) to $X$. Thus, there are at least $(2k+1)(k+1)$ edges between $N_G(X)$ and $X$. On the other hand, the number of edges between $X$ and $N_G(X)$ is at most $k|X|=k(2k+1)$, so we have a contradiction.


Another one: girth. By Ramsey's theorem, for every graph $G$ on six or more vertices, either it or its complement has girth at most three.

  • $\begingroup$ Nice one. +1ed. It is a bit funny that girth is usually defined to be $\infty$ for acyclic graphs, and there are obviously small graphs $G$ such that $G$ and $\overline{G}$ are both acyclic. $\endgroup$ – Tony Huynh Feb 7 '16 at 19:32

There are a lot of properties which $G$ and $\overline{G}$ both have them: number of vertices (edges), automorphism group, and etc. So, naturally this question is interesting for me. I want to mention a spectral property. Let $G$ be a graph with $n$ vertices, and $\rho(G)$ denotes the largest eigenvalue of the adjacency matrix of $G$. Then we have: $$\rho(G)\geq \frac{n-1}{2}\; \; \text{or}\;\; \rho(\overline{G})\geq \frac{n-1}{2}.$$

I will give the simplified proof for the above fact.

For any $n\times n$ Hermitian matrices $A$ and $B$, we have: $$\lambda_i(A+B)\leq \lambda_j(A)+\lambda_{i-j+1}(B),\;\; n\geq i\geq j\geq 1,$$ where, $\lambda_i(A)$ denotes the $i$th greatest eigenvalue of the matrix $A$. Now, for graph $G$, let $A$ be the adjacency matrix of $G$ and $B$ be the adjacency matrix of $\overline{G}$. Since we have $A+B=J-I$, which is the adjacency matrix of complete graph, the result is clear.

  • $\begingroup$ I think the OP is after constant upper bounds. $\endgroup$ – Gordon Royle Feb 7 '16 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.