✍ Scribed by Alain Quilliot
No coin nor oath required. For personal study only.
Quilliot, A., Une extension du probleme du point fixe pour des graphes simples, Discrete Mathematics 111 (1993) 435-445. Nous disons qu'un graphe possede la propriete du k-point fixe (k est un entier) si pour tout homomorphisme f dun produit Gk dans G, il existe un sommet x de GX dont l'image f(x) est adjacente ou igale a une de ses coordonntes. L'introduction de ce concept se justifie par le hen qui le connecte au probleme du jeu de poursuite a k poursuivants: plus sptcifiquement, il est indispensable qu'un graphe G possede cette propriete du k-point fixe pour que k poursuivants puissent attraper un joueur poursuivi sur G. Nous ttudions ici quelques applications de cette propritte, et prouvons que tout graphe planaire posstde la propriete du 2-point fixe.
📜 SIMILAR VOLUMES