Граф Паппа

В Теорії графів графом Паппа називається двочастковий кубічний (або 3-регулярний) неорієнтований граф з 18 вершинами і 27 ребрами, є графом Леві конфігурації Паппа. Він названий на честь Паппа Олександрійського, математика Стародавньої Греції, який вірив, що довів теорему про шестикутник, в якій описував конфігурацію Паппа. Всі кубічні дистанційно-регулярні графи відомі. Граф Паппа — один з тринадцяти таких графів.

Граф Паппа

Число прямолінійних схрещувань графу Паппа дорівнює 5, і цей граф є найменшим кубічним графом з таким числом схрещувань (послідовність A110507 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Граф має обхват 6, діаметр 4, радіус 4, хроматичне число 2, хроматичний індекс 3, а також є і 3-вершинно-зв'язним, і 3-реберно-зв'язним.

Хроматичний поліном графу Паппа дорівнює .

Назва «Граф Паппа» використовується також для близького графу з дев'ятьма вершинами, на вершині для кожної точки конфігурації Паппа з ребрами для кожної пари точок, що перебувають на одній лінії. Цей граф 6-регулярний і є доповненням об'єднання трьох не пов'язаних один з одним трикутних графів. Перший граф Паппа можна вкласти в тор, отримуючи при цьому правильну карту з дев'ятьма шестикутними гранями. Другий граф утворює при такому вкладенні правильну карту з 18 трикутними гранями.

Алгебраїчні властивості

Група автоморфізмів графу Паппа — це група з порядком 216. Вона діє транзитивно на вершини і ребра графу. Таким чином, граф Паппа є симетричним. У нього є автоморфізми, що переводять будь-яку вершину в будь-яку іншу і будь-яке ребро — у будь-яке інше ребро. У списку Фостера граф Паппа позначено як F018A і він є єдиним кубічним симетричним графом з 18 вершинами[1][2]. Характеристичний поліном графу Паппа дорівнює . Це єдиний граф з таким характеристичним поліномом, так що в даному випадку граф визначається своїм спектром.

Галерея

Примітки

  1. Royle, G. «Cubic Symmetric Graphs (The Foster Census).» Архівовано 20 липня 2008 у Wayback Machine.
  2. Conder, M. and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.» J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.