Premium
A New Class of Brittle Graphs
Author(s) -
Jamison B.,
Olariu S.
Publication year - 1989
Publication title -
studies in applied mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 46
eISSN - 1467-9590
pISSN - 0022-2526
DOI - 10.1002/sapm198981189
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , path (computing) , induced path , discrete mathematics , chordal graph , longest path problem , computer science , programming language
A graph G is perfectly orderable in the sense of Chvátal if there exists a linear order on the set of vertices of G such that no induced path with vertices a, b, c, d and edges ab, bc, cd has a < b and d < c . A perfectly orderable graph G is brittle if every induced subgraph of G contains a vertex which is either endpoint or midpoint of no induced path with three edges in G . We present a new class of brittle graphs by forbidden configurations.