Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-24T20:58:13.349Z Has data issue: false hasContentIssue false
  • English
  • Français

Dismantlability Revisited for Ordered Sets and Graphs and the Fixed-Clique Property

Published online by Cambridge University Press:  20 November 2018

John Ginsburg
John Ginsburg*
Affiliation:
Department of Mathematics, University of Winnipeg Winnipeg, Manitoba R3B 2E9
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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 NG(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 NG(x)∪{x} ⊆ NG(y)∪{y}. If G has n vertices we say that G is dismantlable if the vertices of G can be listed as x1, x2, ..., xi,..., xn such that, for all i = 1,2,..., n— 1, xi is a subdominant vertex of the graph Gi = G — {xj : j < i}

Keywords

05C9906A10graphordered setsubdominant vertexdismantlablegraph homomorphismfixedpointclique
Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 37 , Issue 4 , 01 December 1994 , pp. 473 - 481
Copyright
Copyright © Canadian Mathematical Society 1994

References

1. Anstee, R. and Farber, M., On bridged graphs and cop-win graphs, J. Combin. Theory 44(1988), 22–28.Google Scholar
2. Baclawski, K. and Bjorner, A., Fixed points in partially ordered sets, Adv. Math. 31(1979), 263–287.Google Scholar
3. Constantin, J. and Fournier, G., Ordonnes escamotables et points fixes, Discrete Math. 53(1985), 21–33.Google Scholar
4. Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25(1961), 71–76.Google Scholar
5. Duffus, D., Poguntke, W. and Rival, I., Retracts and the fixed point problem for finite partially ordered sets, Canad. Math. Bull. (2) 23(1980), 231–236.Google Scholar
6. Foldes, S. and Hammer, P., The Dilworth number of a graph, Ann. Discrete Math. 2(1978), 211–219.Google Scholar
7. Golumbic, M. C., Algorithimic graph theory and perfect graphs, Academic Press, New York, 1980.Google Scholar
8. Lovasz, L., Combinatorial problems and exercises, North-Holland Publishing Co., Amsterdam, New York, Oxford, 1979.Google Scholar
9. Nowakowski, R. and Winkler, P., Vertex to vertex pursuit in a graph, Discrete Math. 43(1983), 235–239.Google Scholar
10. Quilliot, A., On the Kelly property working as a compactness criterion on graphs, J. Combin. Theory 40(1985), 186–193.Google Scholar
11. Rival, I., A fixed point theorem for finite partially ordered sets, J. Combin. Theory (A) 21(1976), 309–318.Google Scholar
12. Walker, J. W., Isotone relations and the fixed point property for posets, Discrete Math. 48(1984), 275–288.Google Scholar