Largest Independent Sets in Triangle Free Graphs

303 Views Asked by At

We know that in a triangle free graph, the set of neighbours for a vertex forms an independent set. One can show that the order of the largest independent set in a graph must be larger than (or equal to) the maximum degree.

We can see that if $v_0$ is a vertex with maximum degree and if we have some vertex which has a distance (shortest path) of strictly more than 2 from $v_0$, then one can include such a vertex and extend $N(v_0)$ to form a larger independent set.

Thus, for saturated graphs, the neighbouring set of a vertex with maximum degree is the independent set.

What are some possible characterisations (and examples) of graphs for which the maximum degree vertices have a vertex at distance greater than 2?