11-клетка Балабана

11-клет­ка Бала­ба­на
11-клетка Балабана
11-клет­ка Бала­ба­на
Назван в честь Алек­сан­дру Т. Бала­ба­на
Вер­шин 112
Рёбер 168
Ради­ус 6
Диа­метр 8
Обхват 11
Авто­мор­физ­мы 64
Хро­ма­ти­че­ское чис­ло 3
Хро­ма­ти­че­ский индекс 3
Свой­ства Куби­че­ский
Клет­ка
Гамиль­то­нов
Логотип Викисклада Медиа­фай­лы на Викис­кла­де

11-клет­ка Бала­ба­на или (3–11)-клетка Бала­ба­на — это 3-регу­ляр­ный граф с 112 вер­ши­на­ми и 168 рёб­ра­ми, назван­ные име­нем румын­ско­го хими­ка Алек­сан­дру Т. Бала­ба­на[1].

11-клет­ка Бала­ба­на явля­ет­ся един­ствен­ной (3–11)-клеткой. Граф открыл Бала­бан в 1973 году[2]. Един­ствен­ность её дока­за­ли Брен­дан Мак­кей и Вен­ди Мир­волд в 2003 году[3].

Свойства

11-клет­ка Бала­ба­на явля­ет­ся гамиль­то­но­вым гра­фом и может быть постро­е­на путём уда­ле­ния из 12-клет­ки Тат­та мало­го под­де­ре­ва и полу­ча­ю­щих­ся в резуль­та­те вер­шин сте­пе­ни два[4].

Граф име­ет чис­ло неза­ви­си­мо­сти 52[5], хро­ма­ти­че­ское чис­ло 3, хро­ма­ти­че­ский индекс 3, ради­ус 6, диа­метр 8 и обхват 11. Он так­же явля­ет­ся вер­шин­но 3‑связным и рёбер­но 3‑связным гра­фом.

Алгебраические свойства

Харак­те­ри­сти­че­ский мно­го­член 11-клет­ки Бала­ба­на равен:




(
x
−
3
)

x

12


(

x

2


−
6

)

5


(

x

2


−
2

)

12


(

x

3


−

x

2


−
4
x
+
2

)

2


⋅


{displaystyle (x-3)x^{12}(x^{2}-6)^{5}(x^{2}-2)^{12}(x^{3}-x^{2}-4x+2)^{2}cdot }




⋅
(

x

3


+

x

2


−
6
x
−
2
)
(

x

4


−

x

3


−
6

x

2


+
4
x
+
4

)

4


(

x

5


+

x

4


−
8

x

3


−
6

x

2


+
12
x
+
4

)

8




{displaystyle cdot (x^{3}+x^{2}-6x-2)(x^{4}-x^{3}-6x^{2}+4x+4)^{4}(x^{5}+x^{4}-8x^{3}-6x^{2}+12x+4)^{8}}

.

Груп­па авто­мор­физ­мов гра­фа име­ет поря­док 64[4].

Галерея

Примечания

  1. ↑ Weisstein, Eric W. Balaban 11-Cage (англ.) на сай­те Wolfram MathWorld.
  2. ↑ Balaban, 1973, с. 1033—1043.
  3. ↑ Weisstein, Eric W. Cage Graph (англ.) на сай­те Wolfram MathWorld.
  4. ↑ 1 2 Exoo, Jajcay, 2008.
  5. ↑ Heal, 2016.
  6. ↑ Eades, Marks, Mutzel, North, 1998.

Литература

  • Alexandru T. Balaban. Trivalent graphs of girth nine and eleven, and relationships among cages // Revue Roumaine de Mathématiques Pures et Appliquées. — 1973. — Т. 18.
  • Geoffrey Exoo, Robert Jajcay. Dynamic cage survey // Electr. J. Combin.. — 2008. — Вып. 15.
  • Maher Heal. A Quadratic Programming Formulation to Find the Maximum Independent Set of Any Graph // The 2016 International Conference on Computational Science and Computational Intelligence. — Las Vegas: IEEE Computer Society, 2016.
  • Eades P., Marks J., Mutzel P., North S. Graph-Drawing Contest Report // TR98-16. — Mitsubishi Electric Research Laboratories, 1998.


Источ­ник — https://ru.wikipedia.org/w/index.php?title=11-клетка_Балабана&oldid=100557423
[btn-action]
[wp-post-stars]

Похожее ...

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Учи русский с сайтом "РЯ"
- время проведешь не зря!

Recent Comments

Нет комментариев для просмотра.

Поиск