Une preuve de la conjecture de Sabidussi sur les graphes idempotents pour le produit lexicographique

Carte non disponible

Date/heure
Date(s) - 10/02/2015
11 h 00 min - 12 h 00 min

Catégories


Étant donnés des graphes G et H, le produit lexicographique G[H] de H par G est défini sur V(G)×V(H) de la façon suivante : pour tous (x,u),(y,v) ∈ V(G)×V(H), (x,u)(y,v) ∈ E(G[H]) si ( x≠y et xy ∈ E(G) ) ou ( x=y et uv ∈ E(H).
Un graphe G est idempotent pour le produit lexicographique (ou encore, est un point fixe du produit lexicographique) si G[G] est isomorphe à G. Pour éviter le cas trivial des graphes ayant au plus un sommet, on suppose qu’un graphe idempotent pour le produit lexicographique a au moins deux sommets et donc est infini. Nous construirons des graphes idempotents pour le produit lexicographique en nous inspirant de l’exponentielle ordinale, ce qui permet de ramener l’idempotence pour le produit lexicographique des graphes à l’idempotence pour la somme lexicographique des ordres totaux.
Considérons des ensembles V et V’ et des groupes de permutations Γ de V et Γ’ de V’. Le produit en couronne Γ≀Γ’ de Γ’ par Γ est le groupe de permutations de V×V’ défini de la façon suivante. Étant donnée une permutation φ de V×V’, φ ∈ Γ≀Γ’ s’il existe g ∈ Γ et une fonction ε : V → Γ’ tels que pour tout (x,y) ∈ V×V’, on a :
φ((x,y))=(g(x),ε(x)(y)).

Le groupe d’automorphismes d’un graphe G est noté Aut(G). Étant donnés des graphes G et H, il est facile de voir que
Aut(G)≀Aut(H)≤Aut(G[H]).
En 1960, Sabidussi a conjecturé que si un graphe G est idempotent pour le produit lexicographique, alors
Aut(G)≀Aut(G)Nous apportons une réponse positive à cette conjecture (voir [1]). La preuve est simple et concise ; elle est essentiellement basée sur l’associativité du produit lexicographique.

[1] P. Ille, A proof of a conjecture of Sabidussi on graphs idempotent under the lexicographic product, Proceedings of the 7th French International Colloquium on Graph Theory (ICGT’05), Hyères (France), Discrete Math. 309 (2009), 3518–3522.

Webpage“>Webpage

Olivier CHABROL
Posts created 14

Articles similaires

Commencez à saisir votre recherche ci-dessus et pressez Entrée pour rechercher. ESC pour annuler.

Retour en haut
Secured By miniOrange