Напівсиметричний граф
В області математичної теорії графів, напівсиметричний граф — це неорієнтований граф, який є реберно-транзитивним і регулярним, але не є вершинно-транзитивним. Іншими словами, кожна вершина має однакову кількість інцидентних ребер і є симетрія, яка відображає будь-яке ребро у будь-яке інше, але існує деяка пара вершин таких, що не мають симетрії. Це і є напівсиметричним графом.
Властивості ред.
Напівсиметричний граф двочастковий, і його автоморфізм групи повинен діяти транзитивно на кожній з двох поділених вершин. Наприклад, схема графу Фолкмана, яка показана тут. Зелені вершини не можуть бути зівставлені коли червоні будуть автоморфізмами, але кожні дві вершини одного кольору симетричні одна з одною.
Історія ред.
Напівсиметричний граф був вперше досліджений E. Dauber, який був учнем Ф. Харарі, на папері, який вже давно не існує, під назвою «On line- but not point-symmetric graphs». Це зміг помітити Джон Фолкман[en] який і опублікував цю статтю в 1967 році. Вона включає в себе самий маленький напівсиметричний граф, тепер відомий як граф Фолкмана[en] на 20 вершинах. Термін «напівсиметричний» був вперше використаний і опублікований Кліном у 1978 році.[1]
Кубічні графи ред.
Найменший напівсиметричний кубічний граф (тобто той, в якому кожна вершина має рівно три ребра) — це граф Грея на 54 вершини. Ця напівсиметричність була вперше виявлена Боувером (Bouwer) у 1968 році. А вже довести до розуму найменший кубічний напівсиметричний граф змогли Dragan Marušič[en] та Aleksander Malnič.[2] Напівсиметричні кубічні графи з 768 вершинами відомі всім. Згідно з Марстоном Кондером[en], Malnič, Marušič і Potočnik, чотири найменших можливих кубічних напівсиметричних графи після графу Грея є Iofinova–Ivanov граф на 110 вершин, граф Любляни на 112 вершинах[3], граф на 120 вершин з обхватом 8 та граф 12-клітка Татта.[4]
Примітки ред.
- ↑ 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), The Ljubljana Graph (PDF), IMFM Preprints, Ljubljana: Institute of Mathematics, Physics and Mechanics, т. 40, № 845, архів оригіналу (PDF) за 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.