В області математичної теорії графів напівсиметричний граф це неорієнтований граф який є реберно транзитивним і регулярн

В області математичної теорії графів, напівсиметричний граф — це неорієнтований граф, який є реберно-транзитивним і регулярним, але не є вершинно-транзитивним. Іншими словами, кожна вершина має однакову кількість інцидентних ребер і є симетрія, яка відображає будь-яке ребро у будь-яке інше, але існує деяка пара вершин таких, що не мають симетрії. Це і є напівсиметричним графом.

^[en] — найменший напівсиметричний граф.

Властивості

Напівсиметричний граф двочастковий, і його автоморфізм групи повинен діяти транзитивно на кожній з двох поділених вершин. Наприклад, схема графу Фолкмана, яка показана тут. Зелені вершини не можуть бути зівставлені коли червоні будуть автоморфізмами, але кожні дві вершини одного кольору симетричні одна з одною.

Історія

Напівсиметричний граф був вперше досліджений E. Dauber, який був учнем Ф. Харарі, на папері, який вже давно не існує, під назвою «On line- but not point-symmetric graphs». Це зміг помітити ^[en] який і опублікував цю статтю в 1967 році. Вона включає в себе самий маленький напівсиметричний граф, тепер відомий як ^[en] на 20 вершинах. Термін «напівсиметричний» був вперше використаний і опублікований Кліном у 1978 році.

Кубічні графи

Найменший напівсиметричний кубічний граф (тобто той, в якому кожна вершина має рівно три ребра) — це граф Грея на 54 вершини. Ця напівсиметричність була вперше виявлена Боувером (Bouwer) у 1968 році. А вже довести до розуму найменший кубічний напівсиметричний граф змогли ^[en] та Aleksander Malnič. Напівсиметричні кубічні графи з 768 вершинами відомі всім. Згідно з ^[en], Malnič, Marušič і Potočnik, чотири найменших можливих кубічних напівсиметричних графи після графу Грея є Iofinova–Ivanov граф на 110 вершин, граф Любляни на 112 вершинах, граф на 120 вершин з обхватом 8 та граф 12-клітка Татта.

Примітки

(1967), Regular line-symmetric graphs, Journal of Combinatorial Theory, 3 (3): 215—232, doi:10.1016/S0021-9800(67)80069-3.
Bouwer, I. Z. (1968), An edge but not vertex transitive cubic graph, Bulletin of the Canadian Mathematical Society, 11: 533—535, doi:10.4153/CMB-1968-063-0.
; Malnič, A.; ; ; Potočnik, P. (2002), (PDF), IMFM Preprints, Ljubljana: Institute of Mathematics, Physics and Mechanics, т. 40, № 845, архів оригіналу (PDF) за 2 березня 2012, процитовано 27 січня 2016.
; Malnič, Aleksander; ; Potočnik, Primož (2006), A census of semisymmetric cubic graphs on up to 768 vertices, Journal of Algebraic Combinatorics, 23 (3): 255—294, doi:10.1007/s10801-006-7397-3.

Посилання

Weisstein, Eric W. Semisymmetric Graph(англ.) на сайті Wolfram MathWorld.

[1] (1967), Regular line-symmetric graphs, Journal of Combinatorial Theory, 3 (3): 215—232, doi:10.1016/S0021-9800(67)80069-3.

[2] Bouwer, I. Z. (1968), An edge but not vertex transitive cubic graph, Bulletin of the Canadian Mathematical Society, 11: 533—535, doi:10.4153/CMB-1968-063-0.

[LUB-3] ; Malnič, A.; ; ; Potočnik, P. (2002), (PDF), IMFM Preprints, Ljubljana: Institute of Mathematics, Physics and Mechanics, т. 40, № 845, архів оригіналу (PDF) за 2 березня 2012, процитовано 27 січня 2016.

[4] ; Malnič, Aleksander; ; Potočnik, Primož (2006), A census of semisymmetric cubic graphs on up to 768 vertices, Journal of Algebraic Combinatorics, 23 (3): 255—294, doi:10.1007/s10801-006-7397-3.