DISMANTLABILITY REVISITED FOR ORDERED SETS AND GRAPHS AND THE FIXED-CLIQUE PROPERTY

We give a unified treatment of several fixed-point type theorems by using the concept of dismantlability, extended from ordered sets to arbitrary graphs. For a graph G and a vertex x of G we let N(G)(x) denote the set of neighbours of x in G. We say that x is a subdominant vertex of G if there is a vertex y of G, distinct from x, such that N(G)(x)U{x} subset-or-equal-to N(G)(y)U{y}. If G has n vertices we say that G is dismantlable if the vertices of G can be listed as x1, x2, ..., x(i),..., x(n) such that, for all i = 1,2,...,n-1, x(i) is a subdominant vertex of the graph G(i) = G - {x(j):j<i}.