Diamentowy wykres
| Diamentowy wykres | |
|---|---|
 | |
| Wierzchołki | 4 |
| Krawędzie | 5 |
| Promień | 1 |
| Średnica | 2 |
| Obwód | 3 |
| Automorfizmy | 4 ( Klein cztery grupy : |
| Liczba chromatyczna | 3 |
| Indeks chromatyczny | 3 |
| Nieruchomości |
Hamiltonowska jednostka planarna odległość |
| Tabela wykresów i parametrów | |
W matematycznej dziedzinie teorii grafów graf diamentowy jest planarnym , nieskierowanym grafem z 4 wierzchołkami i 5 krawędziami. Składa się z wykresu minus jedna
Graf rombowy ma promień 1, średnicę 2, obwód 3, liczbę chromatyczną 3 i indeks chromatyczny 3. Jest to również graf hamiltonowski z dwoma wierzchołkami i dwoma krawędziami , pełen wdzięku .
Grafy bez diamentów i zabronione drobne
Graf jest pozbawiony diamentów, jeśli nie ma diamentu jako podgrafu indukowanego . Grafy bez trójkątów są grafami bez diamentów, ponieważ każdy romb zawiera trójkąt. Grafy bez diamentów są lokalnie skupione: to znaczy są to grafy, w których każde sąsiedztwo jest grafem skupień . Alternatywnie, graf jest wolny od diamentów wtedy i tylko wtedy, gdy każda para maksymalnych klik w grafie ma co najwyżej jeden wierzchołek.
Rodzina grafów, w której każdy połączony element jest grafem kaktusowym, jest zamknięta w dół w ramach mniejszych operacji grafowych. Ta rodzina grafów może być scharakteryzowana przez jedną zabronioną nieletnią . Ten drugorzędny to wykres rombu.
Jeśli zarówno graf motyla, jak i graf rombu są zabronionymi drugorzędnymi, otrzymaną rodziną grafów jest rodzina pseudolasów .
Właściwości algebraiczne
Pełna grupa automorfizmów wykresu diamentu jest grupą rzędu 4 izomorficzną z czterogrupą Kleina , bezpośrednim iloczynem grupy cyklicznej z samo.
Charakterystyczny wielomian wykresu rombowego to . Jest to jedyny wykres z tym charakterystycznym wielomianem, co czyni go wykresem określonym przez jego widmo.
