Niveau Master

b-cliques en théorie des graphes

Posté par
clicli 05-07-09 à 10:28

Bonjour,

Je cherche un contre exemple ou une preuve pour l'assertion: "Dans un graphe G=(V,E), toute b-clique s'écrit comme la somme de b 1-cliques".

Pour rappel, une b-clique d'un graphe G=(V,E) est une application $\omega :V\rightarrow \mathbb{N}$ telle que pour tout stable I on ait la propriété $\displaystyle \omega (I) = \sum_{x\in I}\omega(x)\leq b$ .

La réciproque est vraie: si on dispose de b 1-cliques, il suffit de les sommer pour obtenir une b-clique.

Merci de votre aide!

Ce topic

Imprimer
Réduire / Agrandir
Pour plus d'options, connectez vous !
Fiches de maths

algèbre en post-bac
28 fiches de mathématiques sur "algèbre" en post-bac disponibles.