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 :

Ne doit pas être confondu avec Graphe de Kneser.

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 à nk é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

  1. (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).
  2. (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

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.