Diamant (grafteori)

Diamant
Toppe fire
ribben 5
Radius en
Diameter 2
Omkreds 3
Automorfismer 4 ( Z /2 Z × Z /2 Z )
Kromatisk tal 3
Kromatisk indeks 3
Ejendomme
Plan Hamiltonian enhedsafstandsgraf
 Mediefiler på Wikimedia Commons

Diamant er en plan urettet graf med 4 spidser og 5 kanter [1] [2] . En graf er en komplet graf uden én kant.

Diamantens radius er 1, diameteren er 2, omkredsen er 3, det kromatiske indeks og det kromatiske tal er 3. Grafen er også 2-vertex-forbundet og 2-kant-forbundet , har en yndefuld mærkning [3] , og er Hamiltonian .

Tæller uden diamanter og forbudte mindreårige

En graf er diamantfri, hvis den ikke indeholder en diamant som en genereret undergraf . Grafer uden trekanter er fri for diamanter, da enhver diamant indeholder en trekant.

En familie af grafer, hvor hver tilsluttet komponent er en kaktus , lukkes ned under driften af ​​at generere en graf minor . Denne familie af grafer kan beskrives med den eneste forbudte lille diamant [4] .

Hvis sommerfuglen og diamanten er forbudte mindreårige, er den resulterende familie af grafer en familie af pseudoskove .

Algebraiske egenskaber

Automorfigruppen af ​​en diamant er en gruppe af orden 4 isomorf til Klein-firegruppegruppen , det direkte produkt af den cykliske gruppe Z / 2Z og sig selv.

Det karakteristiske polynomium for en diamant er . Diamant er den eneste graf med et karakteristisk polynomium, der definerer grafen ved dens spektrum.

Se også

Noter

  1. Weisstein, Eric W. Diamond Graph  på Wolfram MathWorld- webstedet .
  2. ISGCI: Informationssystem om grafklasser og deres inklusion " Liste over små grafer ".
  3. Sin-Min Lee, YC Pan og Ming-Chen Tsai. "På vertex-yndefulde (p,p+l)-grafer". Arkiveret kopi (ikke tilgængeligt link) . Hentet 16. september 2009. Arkiveret fra originalen 7. august 2008. 
  4. El-Mallah, Colbourn, 1988 , s. 354-362.

Litteratur