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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom