| Алмазный график | |
|---|---|
 | |
| Вершины | 4 |
| Края | 5 |
| Радиус | 1 |
| Диаметр | 2 |
| Обхват | 3 |
| Автоморфизмы | 4 ( Z / 2 Z × Z / 2 Z ) |
| Хроматическое число | 3 |
| Хроматический индекс | 3 |
| Характеристики | Гамильтоново плоское единичное расстояние |
| Таблица графиков и параметров | |
В математической области теории графов , то алмаз граф является планарной неориентированный граф с 4 вершинами и 5 ребер. [1] [2] Он состоит из полного графа минус одно ребро.
Алмазов граф имеет радиус 1, диаметр 2, обхват 3, хроматические номер 3 и хроматические индекс 3. Это также 2- вершина соединенных и 2- ребра соединены изящным [3] гамильтонов граф .
Графы без алмаза и запрещенный минор [ править ]
Граф не имеет ромба, если в нем нет ромба в качестве индуцированного подграфа . В треугольнике свободных графиков являются алмазной свободной графикой, так как каждый алмаз содержит треугольник. Графы без ромбов локально кластеризованы: то есть это графы, в которых каждая окрестность является кластерным графом . С другой стороны, граф не содержит ромбов тогда и только тогда, когда каждая пара максимальных клик в графе имеет не более одной вершины.
Семейство графов , в которых каждая компонента связности является кактус граф является вниз закрытым под графиком незначительных операций. Это семейство графов можно охарактеризовать одним запрещенным минором . Этот минор - ромбовидный граф. [4]
Если и граф-бабочка, и граф ромбов являются запрещенными минорами, полученное семейство графов является семейством псевдолесов .
Алгебраические свойства [ править ]
Полная группа автоморфизмов алмаза графа является группа порядка 4 изоморфна четверной группе Клейна , то прямое произведение из циклической группы Z / 2 Z с самим собой.
Характеристический полином алмазного графа . Это единственный граф с таким характеристическим многочленом, что делает его графом, определяемым его спектром.
См. Также [ править ]
- Матроид вамос
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. «Алмазный график» . MathWorld .
- ^ ISGCI: Информационная система по классам графов и их включениям « Список малых графов ».
- ↑ Sin-Min Lee, YC Pan и Ming-Chen Tsai. «На вершинно-изящных (p, p + l) -графах». [1] Архивировано 7 августа 2008 г. в Wayback Machine.
- ↑ Эль-Маллах, Эхаб; Colbourn, Чарльз Дж (1988), "Сложность некоторых проблем края делеционных", IEEE Transactions на схем и систем , 35 (3): 354-362, DOI : 10,1109 / 31,1748.
