Geodesic
Dismantlability Revisited for Ordered Sets and Graphs and the Fixed-Clique Property
Canadian mathematical bulletin, Tome 37 (1994) no. 4, pp. 473-481

Voir la notice de l'article provenant de la source Cambridge University Press

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}
DOI : 10.4153/CMB-1994-069-6
Mots-clés : 05C99, 06A10, graph, ordered set, subdominant vertex, dismantlable, graph homomorphism, fixedpoint, clique 
Ginsburg, John. Dismantlability Revisited for Ordered Sets and Graphs and the Fixed-Clique Property. Canadian mathematical bulletin, Tome 37 (1994) no. 4, pp. 473-481. doi: 10.4153/CMB-1994-069-6
@article{10_4153_CMB_1994_069_6,
     author = {Ginsburg, John},
     title = {Dismantlability {Revisited} for {Ordered} {Sets} and {Graphs} and the {Fixed-Clique} {Property}},
     journal = {Canadian mathematical bulletin},
     pages = {473--481},
     year = {1994},
     volume = {37},
     number = {4},
     doi = {10.4153/CMB-1994-069-6},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CMB-1994-069-6/}
}
TY  - JOUR
AU  - Ginsburg, John
TI  - Dismantlability Revisited for Ordered Sets and Graphs and the Fixed-Clique Property
JO  - Canadian mathematical bulletin
PY  - 1994
SP  - 473
EP  - 481
VL  - 37
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CMB-1994-069-6/
DO  - 10.4153/CMB-1994-069-6
ID  - 10_4153_CMB_1994_069_6
ER  - 
%0 Journal Article
%A Ginsburg, John
%T Dismantlability Revisited for Ordered Sets and Graphs and the Fixed-Clique Property
%J Canadian mathematical bulletin
%D 1994
%P 473-481
%V 37
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/CMB-1994-069-6/
%R 10.4153/CMB-1994-069-6
%F 10_4153_CMB_1994_069_6

[1] 1. Anstee, R. and Farber, M., On bridged graphs and cop-win graphs, J. Combin. Theory 44(1988), 22–28. Google Scholar

[2] 2. Baclawski, K. and Bjorner, A., Fixed points in partially ordered sets, Adv. Math. 31(1979), 263–287. Google Scholar

[3] 3. Constantin, J. and Fournier, G., Ordonnes escamotables et points fixes, Discrete Math. 53(1985), 21–33. Google Scholar

[4] 4. Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25(1961), 71–76. Google Scholar

[5] 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] 6. Foldes, S. and Hammer, P., The Dilworth number of a graph, Ann. Discrete Math. 2(1978), 211–219. Google Scholar

[7] 7. Golumbic, M. C., Algorithimic graph theory and perfect graphs, Academic Press, New York, 1980. Google Scholar

[8] 8. Lovasz, L., Combinatorial problems and exercises, North-Holland Publishing Co., Amsterdam, New York, Oxford, 1979. Google Scholar

[9] 9. Nowakowski, R. and Winkler, P., Vertex to vertex pursuit in a graph, Discrete Math. 43(1983), 235–239. Google Scholar

[10] 10. Quilliot, A., On the Kelly property working as a compactness criterion on graphs, J. Combin. Theory 40(1985), 186–193. Google Scholar

[11] 11. Rival, I., A fixed point theorem for finite partially ordered sets, J. Combin. Theory (A) 21(1976), 309–318. Google Scholar

[12] 12. Walker, J. W., Isotone relations and the fixed point property for posets, Discrete Math. 48(1984), 275–288. Google Scholar

Cité par Sources :