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

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

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

Властивості ред.

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

Історія ред.

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

Кубічні графи ред.

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

Примітки ред.

Folkman, J. (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. .
Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002). . IMFM Preprints (Ljubljana: Institute of Mathematics, Physics and Mechanics) 40 (845). Архів оригіналу за 2 березня 2012. Процитовано 27 січня 2016. .
Conder, Marston; Malnič, Aleksander; Marušič, Dragan; 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] Folkman, J. (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] Conder, M.; Malnič, A.; Marušič, D.; Pisanski, T.; Potočnik, P. (2002). . IMFM Preprints (Ljubljana: Institute of Mathematics, Physics and Mechanics) 40 (845). Архів оригіналу за 2 березня 2012. Процитовано 27 січня 2016. .

[4] Conder, Marston; Malnič, Aleksander; Marušič, Dragan; 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. .