В області математичної теорії графів, напівсиметричний граф — це неорієнтований граф, який є реберно-транзитивним і регулярним, але не є вершинно-транзитивним. Іншими словами, кожна вершина має однакову кількість інцидентних ребер і є симетрія, яка відображає будь-яке ребро у будь-яке інше, але існує деяка пара вершин таких, що не мають симетрії. Це і є напівсиметричним графом.
Властивості Напівсиметричний граф двочастковий, і його автоморфізм групи повинен діяти транзитивно на кожній з двох поділених вершин. Наприклад, схема графу Фолкмана, яка показана тут. Зелені вершини не можуть бути зівставлені коли червоні будуть автоморфізмами, але кожні дві вершини одного кольору симетричні одна з одною.
Історія Напівсиметричні графи вперше дослідив Е. Даубер, учень Ф. Харарі, у статті, яка більше не доступна, під назвою «Про лінійні, але не точково-симетричні графи» (). Це зміг помітити який і опублікував цю статтю в 1967 році. Вона включає в себе самий маленький напівсиметричний граф, тепер відомий як на 20 вершинах. Термін «напівсиметричний» був вперше використаний і опублікований Кліном у 1978 році..
Кубічні графи Найменший напівсиметричний кубічний граф (тобто той, в якому кожна вершина має рівно три ребра) — це граф Грея на 54 вершинах. Ця напівсиметричність була вперше виявлена Боувером (Bouwer) у 1968 році. А вже довести до розуму найменший кубічний напівсиметричний граф змогли та Aleksander Malnič.. Відомі всі напівсиметричні кубічні графи з числом вершин до 10 000. Згідно з , Malnič, Marušič і Potočnik, чотири найменших можливих кубічних напівсиметричних графи після графу Грея є Iofinova–Ivanov граф на 110 вершинах, граф Любляни на 112 вершинах., граф на 120 вершинах з обхватом 8 та граф 12-клітка Татта..
Примітки
Посилання