Portal de Periódicos da CAPES

On the structure of unbreakable graphs

1991; Wiley; Volume: 15; Issue: 4 Linguagem: Inglês

10.1002/jgt.3190150403

1097-0118

Stephan Olariu,

Limits and Structures in Graph Theory

Abstract A nonempty set C of vertices is a star‐cutset in a graph G if G – C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. Vašek Chvátal proposed to call a graph G unbreakable if neither G nor its complement G has a star‐cutset. A path with four vertices and three edges will be termed a P 4 . An edge uv of a graph G is called a wing, if for some vertices x, y , { u,v,x,y } induces a P 4 in G . We define recursively the coercion class C uv of a wing uv as follows: uv ∈ C uv , and if xy ∈ C uv and xy, x'y' are wings of a same P 4 in G , then x'y' ∈ C uv . The purpose of this work is to present new results concerning unbreakable graphs, using the notion of coercion class. These results include a theorem asserting that every unbreakable graph contains at most two distinct coercion classes and a structure theorem for those unbreakable graphs that contain precisely two coercion classes. These results generalize several previously known results about unbreakable graphs.