Diamant (teorie grafů)
| diamant | |
|---|---|
| Vrcholy | čtyři |
| žebra | 5 |
| Poloměr | jeden |
| Průměr | 2 |
| obvod | 3 |
| Automorfismy | 4 ( Z /2 Z × Z /2 Z ) |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti |
Graf vzdálenosti planárních hamiltonovských jednotek |
| Mediální soubory na Wikimedia Commons | |
Diamant je rovinný neorientovaný graf se 4 vrcholy a 5 hranami [1] [2] . Graf je úplný graf bez jedné hrany.
Poloměr diamantu je 1, průměr je 2, obvod je 3, chromatický index a chromatické číslo jsou 3. Graf je také spojen se 2 vrcholy a se 2 okraji , má elegantní označení [3] a je Hamiltonian .
Počty bez diamantů a zakázané nezletilé
Graf je bez diamantu, pokud neobsahuje diamant jako vygenerovaný podgraf . Grafy bez trojúhelníků neobsahují diamanty, protože každý diamant obsahuje trojúhelník.
Rodina grafů, ve kterých je každá připojená komponenta kaktus , je uzavřena operací generování menšího grafu . Tuto rodinu grafů lze popsat jediným zakázaným mollovým diamantem [4] .
Pokud jsou motýl a diamant zakázaní nezletilí, výsledná rodina grafů je rodina pseudolesů .
Algebraické vlastnosti
Skupina automorfismu diamantu je grupa řádu 4 izomorfní ke Kleinově čtyřskupině , přímý produkt cyklické grupy Z /2 Z a sebe sama.
Charakteristickým polynomem diamantu je . Diamant je jediný graf s charakteristickým polynomem definujícím graf svým spektrem.
Viz také
- Vamos matroid
Poznámky
- ↑ Weisstein, Eric W. Diamond Graph na webu Wolfram MathWorld .
- ↑ ISGCI: Informační systém o třídách grafů a jejich zahrnutí " Seznam malých grafů ".
- ↑ Sin-Min Lee, YC Pan a Ming-Chen Tsai. "Na Vertex-graceful (p, p + l)-Graphs". Archivovaná kopie (nedostupný odkaz) . Získáno 16. září 2009. Archivováno z originálu 7. srpna 2008.
- ↑ El-Mallah, Colbourn, 1988 , s. 354–362.
Literatura
- Ehab El-Mallah, Charles J. Colbourn. Složitost některých problémů s odstraněním okrajů // IEEE Transactions on Circuits and Systems. - 1988. - T. 35 , no. 3 . — S. 354–362 . - doi : 10.1109/31.1748 .