# On independent sets of graph

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

• 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. Jan 25 '15 at 21:27
• 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). Jan 27 '15 at 5:41
• Thank you. But at least what I called my small EXAMPLE was fine, I was not confused at that stage. Jan 27 '15 at 6:11
• 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)$). Jan 27 '15 at 9:42
• Yes, as an upper bound. These are trivially equivalent (sorry to inertially waste time on my talking). Jan 27 '15 at 9:50

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

• 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. Jan 25 '15 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\}$$

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

• Could you tell me what does oic mean? Jan 25 '15 at 12:15
• 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)$.
– Mr.
Jan 25 '15 at 12:31
• I fixed $\ M(G)$--now it's perfect! (every k-subset is used). In particulat the small example got improved as the result. Jan 25 '15 at 14:57
• This general (:-) example is done; it's time for a more dramatic one, hey! Jan 25 '15 at 15:37
• 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. Jan 25 '15 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.

• something seems incorrect. Let me carefully check.
– Mr.
Jan 31 '15 at 3:32
• I know for a fact $M(G)$ cannot be arbitrarily big compared to $N(G),\alpha(G)$.
– Mr.
Jan 31 '15 at 3:34
• 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.
– Seok
Jan 31 '15 at 3:57
• Can you show some pictures?
– Mr.
Jan 31 '15 at 4:40