Алмазный график

Алмазный график
Вершины	4
Края	5
Радиус	1
Диаметр	2
Обхват	3
Автоморфизмы	4 ( четыре группы Клейна : ⁠ $\mathbb {Z} /2\mathbb {Z} \times \mathbb {Z} /2\mathbb {Z} )$⁠
Хроматическое число	3
Хроматический индекс	3
Характеристики	гамильтониан Планарный Расстояние единицы
Таблица графиков и параметров

В математической области теории графов ромбовидный граф представляет собой плоский неориентированный граф с 4 вершинами и 5 ребрами. Он состоит из полного графа ⁠ $K_{4}$⁠ минус одно ребро.

Алмазный граф имеет радиус 1, диаметр 2, обхват 3, хроматическое число 3 и хроматический индекс 3. Он также является 2- вершинно-связным и 2- реберно-связным , изящным , Гамильтонов график .

Графики без бриллиантов и запрещенный минор

Граф является безромбическим, если в нем нет ромба в качестве индуцированного подграфа . Графы без треугольников — это графы без ромбов, поскольку каждый ромб содержит треугольник. Графы без ромба локально кластеризованы: то есть это графы, в которых каждая окрестность является кластерным графом . Альтернативно, граф не содержит алмазов тогда и только тогда, когда каждая пара максимальных клик в графе имеет не более одной общей вершины.

Семейство графов, в котором каждый компонент связности является графом-кактусом, замкнуто вниз относительно второстепенных операций над графом. Это семейство графов может характеризоваться одним запрещенным минором . Этот минор — ромбовидный граф.

Если и граф-бабочка , и граф-ромб являются запрещенными минорами, полученное семейство графов является семейством псевдолесов .

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

Полная группа автоморфизмов алмазного графа — это группа порядка 4, изоморфная четырёхгруппе Клейна , прямому произведению циклической группы ⁠ $\mathbb {Z} /2\mathbb {Z}$⁠ с самим собой.

Характеристический многочлен ромбовидного графа равен ⁠ $x(x+1)(x^{2}-x-4)$⁠ . Это единственный граф с этим характеристическим полиномом, что делает его графом, определяемым его спектром.

См. также

• Таможенный матроид