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.
Definition 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
Exempel center|miniatyr|450px|För alla k kallas för stjärngrafer. I bilden syns .
Egenskaper 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.
Referenser
Kategori:Grafteori