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

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

в математический поле теория графов, то ромбовидный график это планарный неориентированный граф с 4 вершинами и 5 ребрами.^[1][2] Он состоит из полный график ${ displaystyle K_ {4}}$ минус одно ребро.

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

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

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

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

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

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

Полная группа автоморфизмов ромбовидного графа - это группа порядка 4, изоморфная Кляйн четыре группы, то прямой продукт из циклическая группа Z/2Z с собой.

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

Смотрите также

• Вамос матроид

Рекомендации