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

• Mall:Bokref