Граф Фостера

У математичній теорії графів, граф Фостер є двочастковий. Це 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]

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

Галерея

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

Посилання

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