On independent sets of graph

Question

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$?

Answer 1

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

Answer 2

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\}$$

Then

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

PROOFS

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$$

Answer 3

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.