On Some Properties of the Struction of a Graph
D. de Werra · SIAM Journal on Algebraic and Discrete Methods · 1984
The struction is defined as an operation which associates with a graph G with stability number $\alpha (G)$ another graph $G'$ with stability number $\alpha (G') = \alpha (G) - 1$. Properties of the graph $G'$ are related to those of G. Namely, one exhibits some classes of graphs which are closed with respect to the struction; i.e., if G is in class C, then so is $G'$. One shows that for a fixed k, the class of graphs containing no induced $P_k $ (path on k nodes) is closed. So is the class of graphs containing no induced $P_k $ and no induced $C_k $ (cycle on k nodes). One also shows that the class of graphs G with $\alpha (G) = \theta (G)$ is closed. (Here $\theta (G)$ is the minimum number of cliques covering the nodes of G.)