𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Permutations representatives d'un graphe a seuil

✍ Scribed by P. Arbouz

Publisher
Elsevier Science
Year
1984
Tongue
English
Weight
184 KB
Volume
50
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Threshold graphs are known to be permutation graphs. We give, from the describing word of a threshold graph G, a way of getting all representative permutations of G and an explicit counting formula of all these permutations.

Rappeb et notations

Parmi les nombreuses caract6risations des graphes h seuiI, nous retiendrons la suivante [1]:

Un graphe est h seuil si et seulement si il peut 6tre construit, h partir du graphe vide, par applications successives d'op6rations 616mentaires:

-ajouter au graphe un nouveau sommet isol6, -ajouter au graphe un nouveau sommet dominant (i.e. adjacent h tous les autres).

De cette caract6risation, nous pouvons associer h tout graphe h seuil, un 'mot' ou 'liste' form6e des lettres I (isol6) et D (dominant) correspondant au statut de chaque sommet ajout6 dans la construction pr6c6dente.

📜 SIMILAR VOLUMES

La reduction minimale d'un graphe a une
La reduction minimale d'un graphe a une reunion de cliques
✍ Ioan Tomescu 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 770 KB

Rkwn& On obtient la virleu: mw4mnle de l'indice dc r6ductiol minimate d'un graphe 3 une rCunion de k cliques. Dam ce qui suit mm uf ilisms la, tern~inalogie de [ 2 1. Un graphe est un graphe compose de deu~ classes de ssmmets qui contiennent re&zctivement p et y sommets, un sbmmet etant reli6 par d

Coloured knots and coloured graphs repre
Coloured knots and coloured graphs representing 3-fold simple coverings of %plane1D;54A;3
✍ Mari Rita Casali 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 525 KB

It is well-known that every closed orientable 3-manifold M 3 is the 3-fold simple covering M3(K,o)) of S 3 branched over a knot K: hence, M 3 may be visualized by the associated coloured knot (K, co). On the other hand, PL-manifolds of arbitrary dimension may be represented by coloured graphs, via p