Двогранний граф

У теорії графів двогранний граф або напіврегулярний двочастковий граф ${\displaystyle G=(U,V,E)}$ є двочастковим графом для якого кожні дві вершини на одній і тій же стороні даного двонаправленого розділу мають однаковий степінь. Якщо вершин в ${\displaystyle U}$ мають степінь ${\displaystyle x}$, а вершини в ${\displaystyle V}$ степеня ${\displaystyle y}$, тоді граф називається ${\displaystyle (x,y)}$-двогранним.

Види графів за їхніми автоморфізмами
відстанево-транзитивний	${\displaystyle \leftarrow }$	сильно регулярний
${\displaystyle \downarrow }$
симетричний (дуго-транзитивний)	${\displaystyle \leftarrow }$	t-транзитивний, t ≥ 2
${\displaystyle \downarrow }$(якщо зв'язний)
^[en]	${\displaystyle \rightarrow }$	реберно-транзитивний і регулярний	${\displaystyle \rightarrow }$	реберно-транзитивний
${\displaystyle \downarrow }$		${\displaystyle \downarrow }$
вершинно-транзитивний	${\displaystyle \rightarrow }$	регулярний
${\displaystyle \uparrow }$
граф Келі		^[en]		асиметричний

Граф ромбододекаедру є двогранним (бірегулярним).

Приклад

Кожен повний двочастковий граф ${\displaystyle K_{a,b}}$ є ${\displaystyle (b,a)}$-двогранним. Ромбододекаедр є ще одним прикладом; він є (3,4)-двогранним графом .

Кількість вершин

${\displaystyle (x,y)}$-двогранний граф ${\displaystyle G=(U,V,E)}$ має задовольняти рівняння ${\displaystyle x|U|=y|V|}$. Це випливає з простого аргументу ^[en]: кількість кінців ребер з ${\displaystyle U}$ дорівнює ${\displaystyle x|U|}$, кількість кінців ребер в ${\displaystyle V}$ дорівнює ${\displaystyle y|V|}$, і кожне ребро додає однакову кількість в обидва числа.

Симетрія

Кожен регулярний двочастковий граф також є двогранним. Кожен реберно-транзитивний граф (забороняються графи з ізольованими вершинами), який не є також вершинно-транзитивним, повинен бути двогранним. Зокрема, кожен реберно-транзитивний граф є або регулярним, або бірегулярним (двогранним).

Конфігурації

Графи Леві геометричних конфігурацій є двогранними; двогранний граф — це граф Леві (абстрактної) конфігурації тоді й тільки тоді, коли його обхват становить не менше шести.

Посилання

1. ; Ullman, Daniel H. (1997), Fractional graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons Inc., с. 137, ISBN , MR 1481157.
2. Dehmer, Matthias; Emmert-Streib, Frank (2009), , John Wiley & Sons, с. 149, ISBN , архів оригіналу за 19 березня 2017, процитовано 11 січня 2020.
3. Lauri, Josef; Scapellato, Raffaele (2003), , London Mathematical Society Student Texts, Cambridge University Press, с. 20—21, ISBN , архів оригіналу за 2 серпня 2020, процитовано 11 січня 2020.
4. Réti, Tamás (2012), (PDF), MATCH Commun. Math. Comput. Chem., 68: 169—188, архів оригіналу (PDF) за 29 серпня 2017, процитовано 2 вересня 2012.
5. Gropp, Harald (2007), VI.7 Configurations, у Colbourn, Charles J.; Dinitz, Jeffrey H. (ред.), Handbook of combinatorial designs, Discrete Mathematics and its Applications (Boca Raton) (вид. Second), Chapman & Hall/CRC, Boca Raton, Florida, с. 353—355.