Двогранний граф
У теорії графів двогранний граф[1] або напіврегулярний двочастковий граф[2] є двочастковим графом для якого кожні дві вершини на одній і тій же стороні даного двонаправленого розділу мають однаковий степінь. Якщо вершин в мають степінь , а вершини в степеня , тоді граф називається -двогранним.
Кожен повний двочастковий граф є -двогранним[3]. Ромбододекаедр є ще одним прикладом; він є (3,4)-двогранним графом[4] .
-двогранний граф має задовольняти рівняння . Це випливає з простого аргументу подвійного підрахунку[en]: кількість кінців ребер з дорівнює , кількість кінців ребер в дорівнює , і кожне ребро додає однакову кількість в обидва числа.
Кожен регулярний двочастковий граф також є двогранним. Кожен реберно-транзитивний граф (забороняються графи з ізольованими вершинами), який не є також вершинно-транзитивним, повинен бути двогранним[3]. Зокрема, кожен реберно-транзитивний граф є або регулярним, або бірегулярним (двогранним).
Графи Леві геометричних конфігурацій є двогранними; двогранний граф — це граф Леві (абстрактної) конфігурації тоді й тільки тоді, коли його обхват становить не менше шести[5].
- ↑ Scheinerman, Edward R.; Ullman, Daniel H. (1997), Fractional graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, New York: John Wiley & Sons Inc., с. 137, ISBN 0-471-17864-0, MR 1481157.
- ↑ Dehmer, Matthias; Emmert-Streib, Frank (2009), Analysis of Complex Networks: From Biology to Linguistics, John Wiley & Sons, с. 149, ISBN 9783527627998, архів оригіналу за 19 березня 2017, процитовано 11 січня 2020.
- ↑ а б Lauri, Josef; Scapellato, Raffaele (2003), Topics in Graph Automorphisms and Reconstruction, London Mathematical Society Student Texts, Cambridge University Press, с. 20—21, ISBN 9780521529037, архів оригіналу за 2 серпня 2020, процитовано 11 січня 2020.
- ↑ Réti, Tamás (2012), On the relationships between the first and second Zagreb indices (PDF), MATCH Commun. Math. Comput. Chem., 68: 169—188, архів оригіналу (PDF) за 29 серпня 2017, процитовано 2 вересня 2012.
- ↑ 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.