Given $G$ a regular graph on $n$ vertices, denote $\alpha(G)>1$ to be independence number.

Denote $\Gamma(G)$ to be collection of possible subset of independent vertices in $G$ of cardinality $\alpha(G)-1$.

To each $\gamma\in\Gamma(G)$, assign number $N(\gamma)$ reflecting number of ways $\gamma$ could be extended by an additional vertex so that augmented subset remains independent (attains cardinality number $\alpha(G)$).

Denote $N(G)=\max_{\gamma\in\Gamma(G)}N(\gamma)$.

Denote $M(G)$ to be maximum number of disjoint independent sets of $G$ that attain cardinality $\alpha(G)$ (that is each subset in $M(G)$ should be disjoint with cardinality $\alpha(G)$).

Easy to observe that $M(G)\leq\frac{|V|}{\alpha(G)}$.

Given fixed real $r>3$ (example $3.00002$), is there a graph (family) such that $$M(G)>|V|^{\frac{r-1}{f(r)}}>|V|^{\frac{1}{f(r)}}> \max(N(G),\alpha(G))$$ where $|V|$ is vertex number with some function $f(r)\geq r$?

  • $\begingroup$ Your notion $\ f(\alpha(G)\ N(G))\ :=\ \max(\alpha(G)\ N(G)),\ $ and similar functions $\ f(\alpha(G)\ N(G))\ $ introduce an interesting internal pressure to the graphs, and it should lead to a whole subtopic. $\endgroup$ Jan 25, 2015 at 21:27
  • $\begingroup$ Turbo, about def. of $\ M(G).\ $ Is $\ M(G)\ $ the maximal cardinality of a family of pairwise disjoint independent sets of cardinality $\ \alpha(G)\ $? -- so we would have $\ M(G)\ \le\ \binom n{\alpha(G)}\ $ (where $\ n\ $ is the number of vertices). $\endgroup$ Jan 27, 2015 at 5:41
  • $\begingroup$ Thank you. But at least what I called my small EXAMPLE was fine, I was not confused at that stage. $\endgroup$ Jan 27, 2015 at 6:11
  • 1
    $\begingroup$ I think that only my accidental conclusion was wrong (a result of a mistaken thinking at that moment--my concentration gave up when I mixed the general definition and the peculiarities of my construction). Another equivalent formulation: $\ m:=M(G)\ $ is the largest integer such that there exists $\ W\subseteq V\ $ such that $\ |W|=\alpha(G)\cdot m\ $ and W is a union of $\ m\ $ maximal independent sets (i.e. od independent sets $\ J\subseteq V\ $ such that $\ |J|=\alpha(G)$). $\endgroup$ Jan 27, 2015 at 9:42
  • 1
    $\begingroup$ Yes, as an upper bound. These are trivially equivalent (sorry to inertially waste time on my talking). $\endgroup$ Jan 27, 2015 at 9:50

3 Answers 3


Take $G = K_n$ the complete graph on $n$ vertices. Then $\alpha(G) = 1<N(G) = n$.

  • 1
    $\begingroup$ Consider $K_n$ with an additional isolated vertex. Or if you want a connected graph connect this vertex to some vertex of the complete graph. $\endgroup$ Jan 25, 2015 at 8:14

EXAMPLE (small)

Let $\ A\ $ be a 5-element set. Let $\ V:=\binom A2.\ $ Let the set of edges be

$$E\ :=\ \left\{\left\{u\ v\right\}\in \binom V2\ :\ |u\cap v|=1\right\}$$

Then, for $\ G:=(V\ E),\ $ we have:

  • $\ \alpha(G)=2$
  • $\ N(G)=3$
  • $\ M(G)=5$

Thus the answer to all three parts of question 1 is YES--there is a single requested example (it's a regular graph, with $\ \alpha(G)>1$).

General Construction

Now let $\ |A|=3\cdot k-1\ $ for an arbitrary $\ k\ge 2.\ $ Let $\ V:=\binom A k\ $ and $$E\ :=\ \left\{\left\{u\ v\right\}\in \binom V2\ :\ 1\le |u\cap v|<k \right\}$$


  • $\ \alpha(G)=2$
  • $\ N(G)=\binom{2\cdot k-1}k$


The independent sets in my example are pairwise disjont $k$-subsets of the $(3\cdot k-1)$-set A. Thus the maximal independent sets are exactly pairs of two disjoint $k$-sets, hence

$$\alpha(G)\ =\ 2$$

REMARK 1   Every(!) $\ (\alpha(G)-1)$-independent set is contained in the same maximal number $\ N(G)\ $ of the maximal independent sets.

Next, in the case of this (general) example, the independent $(\alpha(G)-1)$-sets are simply $1$-element sets, where the single element is an arbitrary $k$-set $\ X.\ $ You may extend such an independent set $\ \{A\}\ $ by selecting any $\ k$-subset $\ Y\subseteq A\setminus X.\ $ This shows that:

$$N(G)\ := \binom{2\cdot k-1}k$$

  • $\begingroup$ Could you tell me what does oic mean? $\endgroup$ Jan 25, 2015 at 12:15
  • $\begingroup$ I think your count for $M(G)$ is off. $M(G)$ is a collection of subsets with each subset disjoint having cardinality exactly $\alpha(G)$. $\endgroup$
    – Turbo
    Jan 25, 2015 at 12:31
  • $\begingroup$ I fixed $\ M(G)$--now it's perfect! (every k-subset is used). In particulat the small example got improved as the result. $\endgroup$ Jan 25, 2015 at 14:57
  • $\begingroup$ This general (:-) example is done; it's time for a more dramatic one, hey! $\endgroup$ Jan 25, 2015 at 15:37
  • 1
    $\begingroup$ Perhaps. This and variations were on my mind, but I wanted to finish first step to answer properly on your question. Just to establish the $\ \LaTeX\ $ phrases was hard to me (I am slow). Now wider possibilities are open. $\endgroup$ Jan 25, 2015 at 20:43

It occurs to me that the complement is much easier to consider.

Then $M(G)$ is the number of disjoint maximum cliques, $\alpha (G)$ is the clique number and $N(G)$ is whatever.

If we start from a cubic graph, let's say $K_4$, and blow-up every vertex into a triangle at each step, then in the resulting graph the maximum size of a clique is always 3 and the only triangles are blowed-up vertices from the previous graph. So, let $G_n$ be the graph from $K_4$ by blowing up all vertices $n$ times. Then $$ |V(G_n)| = 3^n \cdot 4$$ $$ M(G_n) = |V(G_{n-1})| = 3^{n-1} \cdot 4$$ And $N(G)$ is the maximum number of possible ways of extending a single edge into a triangle, which is 1 since the triangles in $G_n$ are disjoint. So, by taking the complement

$$ M(G_n^c) = |V|/3 > |V|^{(r-1)/f(r)} > |V|^{1/f(r)} > \max \{N(G_n^c), \alpha(G_n^c)\} = \max \{ 1, 3\} = 3$$

I don't think the conditions on $r$ and $f(r)$ actually matters anyway, once you obtain linear number of $M(G)$ and bounded size of $N(G)$ and $\alpha(G)$. I started with dense regular graphs if it helps you. I hope my abuse of notations between complement and the original graph does not bother you.

  • $\begingroup$ something seems incorrect. Let me carefully check. $\endgroup$
    – Turbo
    Jan 31, 2015 at 3:32
  • $\begingroup$ I know for a fact $M(G)$ cannot be arbitrarily big compared to $N(G),\alpha(G)$. $\endgroup$
    – Turbo
    Jan 31, 2015 at 3:34
  • $\begingroup$ If you did not understand the construction then point out where you missed. The graph does not have a single pair of triangles sharing an edge. $\endgroup$
    – Seok
    Jan 31, 2015 at 3:57
  • $\begingroup$ Can you show some pictures? $\endgroup$
    – Turbo
    Jan 31, 2015 at 4:40
  • $\begingroup$ Define blow up please. $\endgroup$
    – Turbo
    Jan 31, 2015 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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