Categorizing the class of graphs consisting of the disjoint union of a star with isolated points

95 Views Asked by At

We define $ \mathcal{Q} $ to be the (obviously hereditary) class of graphs whose vertices can be partitioned into a set inducing a star and a set of isolated vertices. The question is to classify $ \mathcal{Q} $ in terms of minimal forbidden induced subgraphs. I think I've got an answer of $ \mathcal{Q} = \textrm{Free} (2K_2, K_3, P_4, C_4) $ but I'm not fully sure. So my question is, is this correct (if you know that it is, feel free to say so and not go through the details of my proof), and if not, where have I gone wrong? My reasoning is as follows. To clarify the notation, $ K_n $ is the complete graph on $ n $ vertices, so $ 2 K_2 $ is the disjoint union of 2 such graphs, $ P_n $ is the path on $ n $ vertices and $ C_n $ is the cycle on $ n $ vertices.

Firstly, it's very obvious that all the given graphs are not in $ \mathcal{Q} $ and that removing any vertex gives us something in $ \mathcal{Q} $. So $ \mathcal{Q} \subseteq \textrm{Free} (2K_2, K_3, P_4, C_4) $.

The converse is where we do most of the work. Take a graph $ G $ not in $ \mathcal{Q} $; we aim to show that it contains one of our chosen graphs as an induced subgraph. Let $ v $ be a vertex of maximal degree in $ G $ and let $ U $ be the set of its neighbours. First of all, $ v $ cannot have degree $ 0 $ or else $ G $ consists of isolated vertices. If $ v $ has degree $ 1 $ then $ G $ consists of copies of $ K_2 $ and isolated vertices. It must have at least two copies of $ K_2 $, or else it is in $ \mathcal{Q} $. Therefore $ G $ contains $ 2 K_2 $ and we're done in this case.

Assume then that $ v $ has degree at least $ 2 $. If any two vertices in $ U $ are adjacent then these, together with $ v $, induce a $ K_3 $. So assume they are all nonadjacent. Now, if there are no pendant edges from the vertices of $ U $ (i.e. each vertex in $ U $ is adjacent only to $ v $ ) then clearly $ v $ together with $ U $ forms a connected component of $ G $, and this component is a star. Then, since $ G \not\in \mathcal{Q} $, two vertices outside of this component must be connected, and we induce a $ 2K_2 $ again.

So suppose that some vertex $ u \in U $ has a pendant edge, connected to $ w $ say, $ w \neq v $. Note that $ w \not\in U $ (we have assumed that $ U $ is an isolated set). Look at some other $ x \in U, x \neq u $. If $ x $ is not adjacent to $ w $ then we obtain an induced $ P_4 $ from $ xvuw $. On the other hand, if $ x $ is adjacent to $ w $ then we obtain an induced $ C_4 $ from $ xvuw $. This completes the proof.

Would appreciate feedback/possible correction from those good at graph theory (apologies for the lack of pictures!)