A note on superbrittle graphs (Q1081614): Difference between revisions

Let \(P_ 4\) denote a chordless path on vertices a, b, c, d; a and d are called endpoints of \(P_ 4\), while b and c are midpoints. We shall eliminate vertices of a graph one after the other as long as possible by applying two following rules: R1 If there is no induced \(P_ 4\) having vertex x as an endpoint, then x and all adjacent edges are removed, R2 If there is not induced \(P_ 4\) having vertex x as a midpoint, then x and all adjacent edges are removed. We shall call a graph superbrittle if at any stage of the elimination procedure one may eliminate any remaining vertex by rule R1 or R2. In a similar way we consider a class of graphs where \(P_ 4's\) are replaced by \(P_ 3's\) in the rules R1 and R2. Let us call a graph superfragile if at any stage of the elimination process any vertex can be eliminated. There are characterized superbrittle and superfragile graphs via forbidden (induced) subgraphs.