Алмаз — планарный неориентированный граф с 4 вершинами и 5 рёбрамиISGCI: Information System on Graph Classes and their Inclusions "List of Small Graphs ".. Граф представляет собой полный граф без одного ребра.
Радиус алмаза равен 1, диаметр равен 2, обхват равен 3, хроматический индекс и хроматическое число равны 3. Граф также вершинно 2-связен и рёберно 2-связен, имеет грациозную разметкуSin-Min Lee, Y.C. Pan and Ming-Chen Tsai. "On Vertex-graceful (p,p+l)-Graphs". и является гамильтоновым.
Графы без алмазов и запрещённые миноры Граф является свободным от алмазов, если он не содержит алмаза в качестве порождённого подграфа. Графы без треугольников являются свободными от алмазов, поскольку любой алмаз содержит треугольник.
Семейство графов, в котором каждая связная компонента является кактусом, замкнуто вниз относительно операции образования минора графа. Это семейство графов может быть описано единственным запрещённым минором — алмазом.
Если бабочка и алмаз являются запрещёнными минорами, полученное семейство графов является семейством псевдолесов.
Алгебраические свойства Группа автоморфизмов алмаза является группой порядка 4, изоморфной четверной группе Клейна, прямому произведению циклической группы Z/2Z на себя.
Характеристический многочлен алмаза равен . Алмаз является единственным графом с характеристическим многочленом, определяющим граф его спектром.
См. также
Примечания
Литература
Категория:Планарные графы