Граф Фостера
| Ця стаття містить правописні, лексичні, граматичні, стилістичні або інші мовні помилки, які треба виправити. |
У математичній теорії графів, граф Фостер є двочастковий. Це 3-регулярний граф з 90 135 вершинами и ребрами.[1]
Граф Фостер є гамільтоновим і має хроматичний номер 2, хроматичний індекс 3, радіус 8, діаметр 8 і розпірку 10. Він також 3-вершинно-зв'язний і 3-реберно-зв'язний граф.
Всі кубічні дистанційно-регулярні графи відомі. [2] Граф Фостера є одним з 13 таких графів. Це унікальний дистанційно-транзитивний граф з масивом перетинів {3,2,2,2,2,1,1,1, 1,1,1,1,2,2,2,3}. [3] Це можна побудувати як інцидентність графа часткового лінійного простору, яка є унікальною потрійною кришкою, без 8-кутників узагальненого чотирикутника GQ (2,2). Граф названий на честь Р. М. Фостер. Він виконав перепис кубічних симетричних графів, враховуючи цей графік.
Алгебраїчні властивості ред.
Група автоморфізмів графа Фостера є групою порядку 4320. [4] Він діє транзитивно на вершинах, по краях і на дугах графа. Тому граф Фостера є симетричним. Він має автоморфізм, який бере з однієї будь-якої вершини в будь-яку іншу вершину і будь-який край будь-якого іншого краю. За даними перепису Фостера, граф Фостера, який посилається, як F90A, є єдиним кубічним симетричним графом на 90 вершинах. [5] Характеристичний многочлен графа Фостера дорівнює: [2]
.
Галерея ред.
-
Фостер кольоровий граф, щоб виділити різні цикли -
Хроматичне число графа Фостера 2. -
Хроматичний індекс графа Фостера 3.
Посилання ред.
- ↑ Weisstein, Eric W. Foster Graph(англ.) на сайті Wolfram MathWorld.
- ↑ Conder, M. and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.»