Граф Фостера

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

Посилання
  1. Weisstein, Eric W. Foster Graph(англ.) на сайті Wolfram MathWorld.
  2. Conder, M. and Dobcsányi, P. «Trivalent Symmetric Graphs Up to 768 Vertices.»
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.