En komplett bipartit graf är inom grafteori en särskild bipartit graf där varje nod i ena nodmängden är ansluten till alla noder i den andra nodmängden.

DefinitionRedigera

En komplett bipartit graf   är en graf sådan att det inte finns några bågar mellan två noder om båda noderna ligger i samma nodmängd,   eller   (grafen är bipartit), men om två noder u och v ligger i varsin nodmängd,   respektive  , så är bågen uv ett element i E.

Om   har storlek m och   har storlek n brukar G betecknas  

ExempelRedigera

 
För alla k kallas   för stjärngrafer. I bilden syns  .

EgenskaperRedigera

  •   har en maximal oberoende mängd med storlek  .
  • Grannmatrisen till   har egenvärdena   och 0 med multipliciteterna 1, 1 och   respektive.
  •   har   uppspännande träd.
  •   och   är Turángrafer.

ReferenserRedigera

  • Diestel, Reinhard (2005). Graph Theory. Springer Verlag