Komplett bipartit graf

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 $G=(V_{1}\cup V_{2},E)$ ä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, $V_{1}$ eller $V_{2}$ (grafen är bipartit), men om två noder u och v ligger i varsin nodmängd, $V_{1}$ respektive $V_{2}$, så är bågen uv ett element i E.

Om $V_{1}$ har storlek m och $V_{2}$ har storlek n brukar G betecknas $K_{m,n}$

Exempel

För alla k kallas $K_{1,k}$ för stjärngrafer. I bilden syns $K_{1,3},K_{1,4},K_{1,5},K_{1,6}$.

• 
  $K_{1,1}$
• 
  $K_{2,2}$
• 
  $K_{3,2}$
• 
  $K_{3,3}$

Egenskaper

• $K_{m,n}$ har en maximal oberoende mängd med storlek $\max(n,m)$.
• Grannmatrisen till $K_{m,n}$ har egenvärdena ${\sqrt {mn}},-{\sqrt {mn}}$ och 0 med multipliciteterna 1, 1 och $n+m-2$ respektive.
• $K_{m,n}$ har $m^{n-1}n^{m-1}$ uppspännande träd.
• $K_{n,n}$ och $K_{n,n+1}$ är Turángrafer.

Referenser

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