Ця стаття містить правописні лексичні граматичні стилістичні або інші мовні помилки які треба виправити Ви можете допомо

У математичній теорії графів, граф Фостер є двочастковий. Це 3-регулярний граф з 90 135 вершинами и ребрами.

Граф Фостер є гамільтоновим і має хроматичний номер 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] Характеристичний многочлен графа Фостера дорівнює:

$(x-3)(x-2)^{9}(x-1)^{18}x^{10}(x+1)^{18}(x+2)^{9}(x+3)(x^{2}-6)^{12}$ .

Галерея

Фостер кольоровий граф, щоб виділити різні цикли
Хроматичне число графа Фостера 2.
Хроматичний індекс графа Фостера 3.

Посилання

Weisstein, Eric W. Foster Graph(англ.) на сайті Wolfram MathWorld.
Conder, M. and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.»

[1] Weisstein, Eric W. Foster Graph(англ.) на сайті Wolfram MathWorld.

[2] Conder, M. and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.»