Diamentowy wykres - Diamond graph
Diamentowy wykres | |
---|---|
Wierzchołki | 4 |
Krawędzie | 5 |
Promień | 1 |
Średnica | 2 |
Obwód | 3 |
Automorfizmy | 4 ( Z / 2 Z × Z / 2 Z ) |
Liczba chromatyczna | 3 |
Indeks chromatyczny | 3 |
Nieruchomości |
Hamiltonian Planar Unit odległość |
Tabela wykresów i parametrów |
W matematycznej dziedzinie teorii wykres The wykres diament jest płaska nieukierunkowane wykres z 4 i 5 krawędzie wierzchołków. Składa się z pełnego wykresu minus jedna krawędź.
Wykres 1 Diament ma promień, średnica 2, obwód 3, numer chromatycznej 3 i wskaźnik chromatycznej 3. Jest także 2- wierzchołek połączone i 2- krawędź połączone wdzięku Hamiltona wykres .
Wykresy bez diamentów i zabronione drobne
Wykres jest wolny od diamentu, jeśli nie ma diamentu jako indukowanego podgrafu . Te wykresy trójkąt wolne są diamentową darmowe wykresy, ponieważ każdy diament zawiera trójkąt. Grafy bez diamentów są lokalnie skupione: to znaczy są to wykresy, na 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 wykresów, w których każdy połączony komponent jest wykresem kaktusa, jest zamknięta w dół w ramach mniejszych operacji na wykresie . Ta rodzina grafów może być scharakteryzowana przez jednego zabronionego małoletniego . Ta drugorzędna to diamentowy wykres.
Jeżeli zarówno wykres motyla, jak i wykres rombowy są zabronione jako nieletnie, rodzina uzyskanych wykresów jest rodziną pseudoleśni .
Właściwości algebraiczne
Pełna grupa automorfizmem wykresu diamentu jest grupą o uporządkowaniu 4 izomorficzne z Klein czterech grup The bezpośrednim produktem z grupy cyklicznej Z / 2, Z, sama ze sobą.
Wielomian charakterystyczny wykresu diamentu jest . Jest to jedyny wykres z tym charakterystycznym wielomianem, co czyni go wykresem określonym przez jego widmo.