Повний дводольний граф

Повний дводольний граф ${\displaystyle G:=(V_{1}+V_{2},E)}$ — це дводольний граф, такий що для будь-яких двох вершин ${\displaystyle v_{1}\in V_{1}}$ і ${\displaystyle v_{2}\in V_{2}}$, ${\displaystyle (v_{1},v_{2})}$ є ребром в ${\displaystyle G}$. Повний дводольний граф з частками розміру ${\displaystyle |V_{1}|=m}$ і ${\displaystyle |V_{2}|=n}$ позначається як. ${\displaystyle K_{m,n}}$.

Графи-зірки ${\displaystyle S_{3}}$, ${\displaystyle S_{4}}$, ${\displaystyle S_{5}}$ і ${\displaystyle S_{6}}$.

Граф ${\displaystyle K_{3,3}}$.

• Графи ${\displaystyle K_{1,k}}$ називаються зірками, всі повні дводольні графи, які є деревами, є зірками.
• Граф ${\displaystyle K_{1,3}}$ називається клешнею та використовується для визначення графів без клешень.
• Граф ${\displaystyle K_{3,3}}$ іноді називається «комунальним графом», назва йде від класичної задачі «вода, газ та електрика», яка в сучасній інтерпретації використовує «комунальне» формулювання (підключити три будинки до водо- електро- та газопостачання без перетинів ліній на площині); задача нерозв'язна незважаючи на непланарність графа ${\displaystyle K_{3,3}}$.

• Задача пошука для даного дводольного графа повного дводольного підграфа ${\displaystyle K_{m,n}}$ NP-повна.
• Планарний граф не може містити ${\displaystyle K_{3,3}}$ як мінор графа. Зовніпланарний граф не може містити ${\displaystyle K_{3,2}}$ як мінор (Це недостатня умова планарності та зовнішньої планарності, а необхідна). І навпаки, будь-який непланарний граф містить або ${\displaystyle K_{3,3}}$, або повний граф ${\displaystyle K_{5}}$ як мінор (теорема Куратовського).
• Повні дводольні графи ${\displaystyle K_{n,n}}$ є графами Мура і ${\displaystyle (n,4)}$-клітками.
• Повні дводольні графи ${\displaystyle K_{n,n}}$ і ${\displaystyle K_{n,n+1}}$ є графами Турана.
• Повний дводольний граф ${\displaystyle K_{m,n}}$ має розмір вершинного покриття, рівний ${\displaystyle \min(m,n)}$ і розмір реберного покриття, що дорівнює ${\displaystyle \max(m,n)}$.
• Повний дводольний граф ${\displaystyle K_{m,n}}$ має максимальну незалежну множину розміром ${\displaystyle \max(m,n)}$.
• Матриця суміжності повного дводольного графа ${\displaystyle K_{m,n}}$ має власні значення ${\displaystyle {\sqrt {nm}}}$, ${\displaystyle -{\sqrt {nm}}}$ і ${\displaystyle 0}$ із кратностями ${\displaystyle 1}$, ${\displaystyle 1}$ і ${\displaystyle n+m-2}$ відповідно.
• Матриця Лапласа повного дводольного графа ${\displaystyle K_{m,n}}$ має власні значення ${\displaystyle n+m}$, ${\displaystyle n}$, ${\displaystyle m}$, ${\displaystyle 0}$ із кратностями ${\displaystyle 1}$, ${\displaystyle m-1}$, ${\displaystyle n-1}$ і ${\displaystyle 1}$ відповідно.
• Повний дводольний граф ${\displaystyle K_{m,n}}$ має ${\displaystyle m^{n-1}\cdot n^{m-1}}$ кістякових дерев.
• Повний дводольний граф ${\displaystyle K_{m,n}}$ має максимальне парування розміру ${\displaystyle \min(m,n)}$.
• Повний дводольний граф ${\displaystyle K_{n,n}}$ має підхоже ${\displaystyle n}$-реберне розфарбування, яке відповідає латинському квадрату.

Останні два результати є наслідком теореми Холла, застосованої до ${\displaystyle k}$-регулярного дводольного графа.

• Цикл
• Шлях
• Корона
• Двогранний граф
• Двочасткова розмірність