Graphe biparti de Kneser

En théorie des graphes, une branche des mathématiques, les graphes bipartis de Kneser $H_{n,k}$ 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 $H_{5,2}$ .

Notation	$H_{n,k}$
Nombre de sommets	$2C_{k}^{n}$
Distribution des degrés	régulier de degré $C_{n-k}^{k}$
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 $H_{n,k}$ 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 $H 5,2$ est le graphe de Desargues (figure).

Les graphes bipartis de Kneser $H n,1$ sont les graphes couronnes.

Propriétés

Le graphe biparti de Kneser a $2C_{k}^{n}$ sommets. Il est régulier de degré $C_{k}^{n-k}$ .

Comme le Graphe de Kneser, il est sommet-transitif.

Le graphe biparti de Kneser $H_{n,k}$ peut être formé comme une double couverture bipartie (en) du graphe de Kneser $KG_{n,k}$ 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, n^o 1,‎ 2000, 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, 1991, 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.

[1] (en) Ya-Chen Chen, « Kneser graphs are Hamiltonian for n ≥ 3 », Journal of Combinatorial Theory, series B, vol. 80, n^o 1,‎ 2000, 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, 1991, p. 97-110.