Graphe biparti de Kneser
En théorie des graphes, une branche des mathématiques, les graphes bipartis de Kneser forment une famille de graphes non orientés définie comme suit :
Graphe biparti de Kneser | |
Le graphe de Desargues est le graphe biparti de Kneser . | |
Notation | |
---|---|
Nombre de sommets | |
Distribution des degrés | régulier de degré |
Nombre chromatique | 2 |
Propriétés | Régulier Biparti Sommet-transitif |
Soient E un ensemble à n éléments et k un entier inférieur à n. Les sommets du graphe représentent les sous-ensembles de E à k éléments ou à n − k éléments. Deux sommets sont reliés par une arête lorsque l'un des sous-ensembles qu'ils représentent est inclus dans l'autre[1].
Exemples
Le graphe biparti de Kneser H5,2 est le graphe de Desargues (figure).
Les graphes bipartis de Kneser Hn,1 sont les graphes couronnes.
Propriétés
Le graphe biparti de Kneser a sommets. Il est régulier de degré .
Comme le Graphe de Kneser, il est sommet-transitif.
Le graphe biparti de Kneser peut être formé comme une double couverture bipartie (en) du graphe de Kneser en dupliquant chaque sommet et en remplaçant chaque arête par une paire d'arêtes reliant les paires correspondantes de sommets[2].
Voir aussi
Références
- (en) Ya-Chen Chen, « Kneser graphs are Hamiltonian for n ≥ 3 », Journal of Combinatorial Theory, series B, vol. 80, no 1,‎ , p. 2 (DOI 10.1006/jctb.2000.1969, lire en ligne).
- (en) J. E. Simpson, Proceedings of the Twenty-second Southeastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA, 1991), vol. 85, , p. 97-110.
Lien externe
(en) Eric W. Weisstein, « Bipartite Kneser Graph », sur MathWorld