Напівсиметричний граф

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

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

Властивості

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

Історія

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

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

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

Примітки

  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.
  3. ↑ Summary of all semi-symmetric cubic graphs on up to 10000 vertices.
  4. ↑ 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.
  5. ↑ 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.