У теорії графів двогранний граф[1] або напіврегулярний дводольний граф[2] є дводольним графом для якого кожні дві вершини на одній і тій же стороні даного двонаправленого розділу мають однаковий степінь. Якщо вершин в мають степінь , а вершини в степеня , тоді граф називається -двогранним.

Види графів за їхніми автоморфізмами
відстанево-транзитивний[en]відстанево-регулярний[en]сильно регулярний[en]
симетричний (дуго-транзитивний)t-транзитивний, t ≥ 2
(якщо зв'язний)
вершинно- та реберно-транзитивний[en]реберно-транзитивний і регулярнийреберно-транзитивний
вершинно-транзитивнийрегулярний
граф Келікососиметричний[en]асиметричний
Граф ромбододекаедру є двогранним (бірегулярним).

ПрикладРедагувати

Кожен повний дводольний граф   є  -двогранним[3]. Ромбододекаедр є ще одним прикладом; він є (3,4)-двогранним графом[4] .

Кількість вершинРедагувати

 -двогранний граф   має задовольняти рівняння  . Це випливає з простого аргументу подвійного підрахунку[en]: кількість кінців ребер з   дорівнює  , кількість кінців ребер в   дорівнює  , і кожне ребро додає однакову кількість в обидва числа.

СиметріяРедагувати

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

КонфігураціїРедагувати

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

ПосиланняРедагувати

  1. 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. .
  2. Dehmer, Matthias; Emmert-Streib, Frank (2009). Analysis of Complex Networks: From Biology to Linguistics. John Wiley & Sons. с. 149. ISBN 9783527627998. .
  3. а б Lauri, Josef; Scapellato, Raffaele (2003). Topics in Graph Automorphisms and Reconstruction. London Mathematical Society Student Texts. Cambridge University Press. с. 20–21. ISBN 9780521529037. .
  4. Réti, Tamás (2012). On the relationships between the first and second Zagreb indices. MATCH Commun. Math. Comput. Chem. 68: 169–188. Архів оригіналу за 2017-08-29. Процитовано 2012-09-02. .
  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. .