Interested Article - Алмаз (теория графов)

Алмаз планарный неориентированный граф с 4 вершинами и 5 рёбрами . Граф представляет собой полный граф без одного ребра.

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

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

Граф является свободным от алмазов, если он не содержит алмаза в качестве порождённого подграфа . Графы без треугольников являются свободными от алмазов, поскольку любой алмаз содержит треугольник.

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

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

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

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

Характеристический многочлен алмаза равен . Алмаз является единственным графом с характеристическим многочленом, определяющим граф его спектром.

См. также

Примечания

  1. Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
  2. ISGCI: Information System on Graph Classes and their Inclusions " 18 ноября 2012 года. ".
  3. Sin-Min Lee, Y.C. Pan and Ming-Chen Tsai. "On Vertex-graceful (p,p+l)-Graphs". . Дата обращения: 16 сентября 2009. 7 августа 2008 года.
  4. , с. 354–362.

Литература

  • Ehab El-Mallah, Charles J. Colbourn. The complexity of some edge deletion problems // IEEE Transactions on Circuits and Systems. — 1988. — Т. 35 , вып. 3 . — С. 354–362 . — doi : .
Источник —

Same as Алмаз (теория графов)