Diamant (grafteori)

Diamant
Toppar fyra
revben 5
Radie ett
Diameter 2
Omkrets 3
Automorfismer 4 ( Z /2 Z × Z /2 Z )
Kromatiskt nummer 3
Kromatiskt index 3
Egenskaper
Planar Hamiltonian enhetsdistansgraf
 Mediafiler på Wikimedia Commons

Diamant är en plan oriktad graf med 4 hörn och 5 kanter [1] [2] . En graf är en komplett graf utan en kant.

Diamantradien är 1, diametern är 2, omkretsen är 3, det kromatiska indexet och kromatiska numret är 3. Grafen är också 2-vertex-ansluten och 2-kant-ansluten , har graciös märkning [3] , och är Hamiltonian .

Räknas utan diamanter och förbjudna minderåriga

En graf är diamantfri om den inte innehåller en diamant som en genererad subgraf . Grafer utan trianglar är fria från diamanter, eftersom alla diamanter innehåller en triangel.

En familj av grafer där varje ansluten komponent är en kaktus stängs ned under driften av att generera en graf minor . Denna familj av grafer kan beskrivas med den enda förbjudna mindre diamanten [4] .

Om fjärilen och diamanten är förbjudna minderåriga, är den resulterande familjen av grafer en familj av pseudoskogar .

Algebraiska egenskaper

Automorfismgruppen av en diamant är en grupp av ordning 4 isomorf till Klein-fyrgruppen , den direkta produkten av den cykliska gruppen Z / 2Z och sig själv.

Det karakteristiska polynomet för en diamant är . Diamant är den enda grafen med ett karakteristiskt polynom som definierar grafen med dess spektrum.

Se även

Anteckningar

  1. ↑ Weisstein, Eric W. Diamond Graph  på Wolfram MathWorld- webbplatsen .
  2. ↑ ISGCI: Informationssystem om grafklasser och deras inkludering " Lista över små grafer ".
  3. ↑ Sin-Min Lee, YC Pan och Ming-Chen Tsai. "På Vertex-graciösa (p,p+l)-Graphs". Arkiverad kopia (inte tillgänglig länk) . Hämtad 16 september 2009. Arkiverad från originalet 7 augusti 2008. 
  4. ↑ El-Mallah, Colbourn, 1988 , sid. 354–362.

Litteratur