Gyémánt (gráfelmélet)

A gyémánt egy síkbeli irányítatlan gráf 4 csúcsával és 5 élével [1] [2] . A gráf egy teljes gráf egy él nélkül.

A gyémánt sugara 1, az átmérő 2, a kerülete 3, a kromatikus index és a kromatikus szám 3. A gráf 2 csúcshoz és 2 élhez is kapcsolódik, kecses címkézésű [3] , és Hamiltoni .

Gyémánt nélküli grófok és tiltott kiskorúak

Egy gráf gyémántmentes, ha nem tartalmaz gyémántot generált részgráfként . A háromszög nélküli grafikonok nem tartalmaznak gyémántokat, mivel minden gyémánt tartalmaz háromszöget.

Egy gráfcsaládot, amelyben minden összekapcsolt komponens egy kaktusz , egy gráf-moll generálási művelettel zárjuk le . Ez a gráfcsalád az egyetlen tiltott mellékgyémánttal írható le [4] .

Ha a pillangó és a gyémánt tiltott kiskorúak, az eredményül kapott gráfcsalád az álerdők családja .

Algebrai tulajdonságok

A gyémánt automorfizmuscsoportja a Klein-négyes csoport 4. rendű izomorf csoportja , a Z /2 Z ciklikus csoport és önmagának közvetlen szorzata .

A gyémánt karakterisztikus polinomja . A gyémánt az egyetlen gráf, amelynek jellegzetes polinomja a spektruma alapján határozza meg a gráfot.

Lásd még

• Vamos matroid

Jegyzetek

1. ↑ Weisstein, Eric W. Diamond Graph  a Wolfram MathWorld weboldalán .
2. ↑ ISGCI: Információs rendszer a grafikonosztályokról és azok beillesztéséről " Kis grafikonok listája ".
3. ↑ Sin-Min Lee, YC Pan és Ming-Chen Tsai. "A Vertex-kecses (p,p+l)-grafikonokon". Archivált másolat (nem elérhető link) . Letöltve: 2009. szeptember 16. Az eredetiből archiválva : 2008. augusztus 7.. (határozatlan) 
4. ↑ El-Mallah, Colbourn, 1988 , p. 354–362.

Irodalom

• Ehab El-Mallah, Charles J. Colbourn. Néhány éltörlési probléma összetettsége // IEEE Transactions on Circuits and Systems. - 1988. - T. 35 , sz. 3 . – S. 354–362 . - doi : 10.1109/31.1748 .