En teoria de grafs un graf bipartit complet és aquell graf bipartit en el qual tots els vèrtexs de la partició estan connectats a tots els vèrtexs de la partició i viceversa.
Definició Un graf bipartit complet és un graf bipartit tal que És a dir, un graf bipartit complet està format per dos conjunts disjunts de vèrtexs i totes les possibles arestes que uneixen aquests vèrtexs.
El graf complet bipartit amb particions de mida i és denotat com .
Exemples
Propietats Sigui un graf bipartit amb i , es verifica que i posseeix arbres d'expansió. Donat un graf bipartit, comprovar si conté un subgraf bipartit complet per un paràmetre és un problema NP-complet. Un graf planar no pot contenir K3,3 com a subconjunt, i un graf planar exterior (sense vèrtexs interns) no pot contenir K3,2 com a subconjunt. (No són condicions suficients per a la planaritat i la planaritat exterior, però són necessàries). D'altra banda, segons el teorema de Wagner, tot graf no planar conté K3,3 o bé el graf complet K₅ com a subconjunts. Tot graf bipartit complet de la forma és un graf de Moore. Tot graf bipartit complet és un graf modular, és a dir, cada triplet de vèrtexs té una mediana que pertany als camins més curts entre cada parell possible d'aquests vèrtexs.
Referències
Bibliografia (Electronic edition).
Vegeu també Graf bipartit Graf complet
Categoria:Famílies de grafs