A note on superbrittle graphs
type: Item
instance of: scholarly article
title: A note on superbrittle graphs
zbMATH Open document ID: 0602.05035
DOI: 10.1016/0012-365X(86)90097-X
author: Dominique De Werra
author: N. V. R. Mahadev
author: Myriam Preissmann
published in: Discrete Mathematics
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 3970784
zbMATH Keywords: superbrittle graphs
zbMATH Keywords: vertex elimination
zbMATH Keywords: superfragile graphs
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
cites work: Q5615282
cites work: Q3222875
cites work: Which line-graphs are perfectly orderable?
cites work: Trivially perfect graphs
cites work: Q3328583
full work available at URL: 0012-365x(86)90097-x
OpenAlex ID: W1988149074
Recommended article: Q4544103
Recommended article: Q3501517
Recommended article: A note on the total domination supercritical graphs
Recommended article: The superregular graphs
Recommended article: On the super domination number of graphs
Recommended article: Supereulerian graphs: A survey
Recommended article: Supersaturated graphs and hypergraphs
Recommended article: Some results on super mean graphs
Recommended article: On superperfect noncomparability graphs
Recommended article: On super i‐connected graphs
description: scientific article; zbMATH DE number 3970784