Diamant (teoria graficelor)
| Diamant | |
|---|---|
| Vârfurile | patru |
| coaste | 5 |
| Rază | unu |
| Diametru | 2 |
| Circumferinţă | 3 |
| Automorfisme | 4 ( Z /2 Z × Z /2 Z ) |
| Număr cromatic | 3 |
| Indicele cromatic | 3 |
| Proprietăți |
Graficul de distanță al unității planar Hamiltonian |
| Fișiere media la Wikimedia Commons | |
Diamantul este un graf plan nedirecționat cu 4 vârfuri și 5 muchii [1] [2] . Un grafic este un grafic complet fără o muchie.
Raza diamantului este 1, diametrul este 2, circumferința este 3, indicele cromatic și numărul cromatic sunt 3. Graficul este, de asemenea , conectat cu 2 vârfuri și conectat cu 2 muchii , are o etichetare grațioasă [3] și este Hamiltonian .
Numărări fără diamante și minori interziși
Un grafic nu are diamante dacă nu conține un diamant ca subgraf generat . Graficele fără triunghiuri nu conțin diamante, deoarece orice diamant conține un triunghi.
O familie de grafice în care fiecare componentă conectată este un cactus este închisă sub operația de generare a unui grafic minor . Această familie de grafice poate fi descrisă de singurul diamant minor interzis [4] .
Dacă fluturele și diamantul sunt minore interzise, familia de grafice rezultată este o familie de pseudopăduri .
Proprietăți algebrice
Grupul de automorfism al unui diamant este un grup izomorf de ordinul 4 cu grupul cvadruplu Klein , produsul direct al grupului ciclic Z /2 Z și al lui însuși.
Polinomul caracteristic al unui diamant este . Diamantul este singurul grafic cu un polinom caracteristic care definește graficul prin spectrul său.
Vezi și
- Vamos matroid
Note
- ^ Weisstein , Eric W. Diamond Graph pe site- ul Wolfram MathWorld .
- ↑ ISGCI: Sistemul de informații despre clasele de grafice și includerile lor „ Lista graficelor mici ”.
- ↑ Sin-Min Lee, YC Pan și Ming-Chen Tsai. „Pe Vertex-grațios (p,p+l)-Grafi”. Copie arhivată (link indisponibil) . Consultat la 16 septembrie 2009. Arhivat din original pe 7 august 2008.
- ↑ El-Mallah, Colbourn, 1988 , p. 354–362.
Literatură
- Ehab El-Mallah, Charles J. Colbourn. Complexitatea unor probleme de ștergere a marginilor // Tranzacții IEEE pe circuite și sisteme. - 1988. - T. 35 , nr. 3 . — S. 354–362 . - doi : 10.1109/31.1748 .