|
6
|
|
edited Aug 5 2011 at 12:52 |
Here's an example $G$ for all $i \geq 8$ and $n \geq 2i+1$ that contains only $6$ 8$ induced subgraphs (up to isomorphism).
If we choose $i$ vertices from the top row, we obtain $\overline{K_i}$.
If we choose $i-1$ vertices from the top row, we obtain $K_{1,i-1}$ or $\overline{K_i}$.
If we choose $i-2$ vertices from the top row, we obtain $\overline{K_i}$ or $\overline{K_{i-2}} \cup K_2$ or $K_{1,i-2} \cup K_1$ or $K_{1,i-1}$.
If we choose $i-3$ vertices from the top row, we obtain the subgraphs induced by $i-3 \text{ vertices from a,b,c,d,... } \cup {e,g,h}$ or $i-3 \text{ vertices from a,b,c,d,... } \cup {e,f,g}$ or $K_{1,i-2} \cup K_1$ or $\overline{K_{i-3}} \cup P_3$ (path with three vertices).
If we choose $i-4$ vertices from the top row, we obtain the graph induced by $i-4 \text{ vertices from a,b,c,d,... } \cup {e,f,g,h}$.
Since we must choose at least $i-4$ vertices from the top row, in total, that's 8 isomorphism classes of graphs. We can see that $G$ and its complement both contain a triangle (and are therefore not bipartite) and are connected (each vertex is not adjacent to either h or a).
Generalising this technique, we can replace {e,f,g,h} by any non-bipartite connected subgraph of diameter at least 2. In this case, there would exist some I, N such that for all i>=I and n>=max(N,2i+1) which would satisfy the required conditions.
|
|
|
|
|
5
|
|
edited Aug 5 2011 at 12:44 |
Here's an example $G$ for all $i \geq 8$ and $n \geq 2i+1$ that contains only $6$ induced subgraphs (up to isomorphism).
If we choose $i$ vertices from the top row, we obtain $\overline{K_i}$.
If we choose $i-1$ vertices from the top row, we obtain $K_{1,i-1}$ or $\overline{K_i}$.
If we choose $i-2$ vertices from the top row, we obtain $\overline{K_i}$ or $\overline{K_{i-2}} \cup K_2$ or $K_{1,i-2} \cup K_1$ or $K_{1,i-1}$.
If we choose $i-3$ vertices from the top row, we obtain the subgraphs induced by $i-3 \text{ vertices from a,b,c,d,... } \cup {e,g,h}$ or $i-3 \text{ vertices from a,b,c,d,... } \cup {e,f,g}$ or $K_{1,i-2} \cup K_1$ or $\overline{K_{i-3}} \cup P_3$ (path with three vertices).
If we choose $i-4$ vertices from the top row, we obtain the graph induced by $G \setminus i-4 \text{ vertices from a,b,c,d,... } $.\cup {e,f,g,h}$.
Since we must choose at least $i-4$ vertices from the top row, in total, that's 8 isomorphism classes of graphs. We can see that $G$ and its complement both contain a triangle (and are therefore not bipartite) and are connected (each vertex is not adjacent to either h or a).
Generalising this technique, we can replace {e,f,g,h} by any non-bipartite connected subgraph of diameter at least 2. In this case, there would exist some I, N such that for all i>=I and n>=max(N,2i+1) which would satisfy the required conditions.
|
|
|
|
|
4
|
|
edited Aug 5 2011 at 12:37 |
Here's an example $G$ for all $i \geq 4$ 8$ and $n \geq 2i+1$ that contains only $4$ 6$ induced subgraphs (up to isomorphism).
If we choose $i$ vertices from the top row, we obtain $\overline{K_i}$.
If we choose $i-1$ vertices from the top row, we obtain $K_{1,i-1}$ or $\overline{K_i}$.
If we choose $i-2$ vertices from the top row, we obtain $K_2 \overline{K_i}$ or $\overline{K_{i-2}} \cup K_2$ or $K_{1,i-2} \overbrace{K_1 cup K_1$ or $K_{1,i-1}$.
If we choose $i-3$ vertices from the top row, we obtain the subgraphs induced by $i-3 \text{ vertices from a,b,c,d,... } \cup {e,g,h}$ or $i-3 \cdots text{ vertices from a,b,c,d,... } \cup K_1}^{i-2}$ {e,f,g}$ or $K_{1,i-1}$.K_{1,i-2} \cup K_1$.
If we choose $i-3$ i-4$ vertices from the top row, we obtain $G \setminus {a,b,c}$.i-4 \text{ vertices from a,b,c,d,... }$.
Since we must choose at least $i-3$ i-4$ vertices from the top row, in total, that's four 8 isomorphism classes of graphs. We can easily see that $G$ and its complement both contain a triangle (and are therefore not bipartite) and are connected (each vertex is not adjacent to either h or a).
Generalising this technique, we can replace {e,f,g,h} by any non-bipartite connected subgraph of diameter at least 2. In this case, there would exist some I, N such that for all i>=I and n>=max(N,2i+1) which would satisfy the required conditions.
|
|
|
|
3
|
|
edited Aug 5 2011 at 12:09 |
Here's an example when i=4 $G$ for all $i \geq 4$ and $n \geq 2i+1$ that contains an arbitrarily large number of vertices and only 4 $4$ induced subgraphs (up to isomorphism).
If we choose four $i$ vertices from the top row, we obtain $\overline{K_4}$ (a,b,c,d).\overline{K_i}$.
If we choose three $i-1$ vertices from the top row, we obtain $K_{1,3}$ (a,b,c,e) K_{1,i-1}$ or $\overline{K_4}$ (a,b,c,f).\overline{K_i}$.
If we choose two $i-2$ vertices from the top row, we obtain $K_2 \cup K_1 \overbrace{K_1 \cup K_1$ (a,b,f,g) \cdots \cup K_1}^{i-2}$ or $K_{1,3}$ (a,b,e,f).K_{1,i-1}$.
If we choose one vertex $i-3$ vertices from the top row, we obtain [[what's this graph called?]] (a,e,f,g).
In $G \setminus {a,b,c}$.
Since we must choose at least $i-3$ vertices from the top row, in total, that's four isomorphism classes of graphs. We can easily see that $G$ and its complement both contain a triangle (and are therefore not bipartite) and are connected.
|
|
|
|
|
2
|
|
edited Aug 5 2011 at 11:50 |
Here's an example when i=4 that contains an arbitrarily large number of vertices and only 4 induced subgraphs (up to isomorphism).
If we choose four vertices from the top row, we obtain $\overline{K_4}$ (a,b,c,d).
If we choose three vertices from the top row, we obtain $K_{1,3}$ (a,b,c,e) or $\overline{K_4}$ (a,b,c,f).
If we choose two vertices from the top row, we obtain $K_2 \cup K_1 \cup K_1$ (a,b,f,g) or $K_{1,3}$ (a,b,e,f).
If we choose one vertex from the top row, we obtain [[what's this graph called?]] (a,e,f,g).
In total, that's four isomoprhism isomorphism classes of graphs.
|
|
|
|
|
1
|
|
answered Aug 5 2011 at 11:43 |
Here's an example when i=4 that contains an arbitrarily large number of vertices and only 4 induced subgraphs (up to isomorphism).
If we choose four vertices from the top row, we obtain $\overline{K_4}$ (a,b,c,d).
If we choose three vertices from the top row, we obtain $K_{1,3}$ (a,b,c,e) or $\overline{K_4}$ (a,b,c,f).
If we choose two vertices from the top row, we obtain $K_2 \cup K_1 \cup K_1$ (a,b,f,g) or $K_{1,3}$ (a,b,e,f).
If we choose one vertex from the top row, we obtain [[what's this graph called?]] (a,e,f,g).
In total, that's four isomoprhism classes of graphs.
|
|
|
