Snark kwiat
| Snark kwiatowy | |
|---|---|
 Snark kwiatowy J 3 , J 5 i J 7 .
| |
| Wierzchołki | 4 przyp |
| Krawędzie | 6 przyp |
| Obwód |
3 dla n=3 5 dla n=5 6 dla n≥7 |
| Liczba chromatyczna | 3 |
| Indeks chromatyczny | 4 |
| Grubość książki |
3 dla n=5 3 dla n=7 |
| Numer kolejki |
2 dla n=5 2 dla n=7 |
| Nieruchomości | Snark dla n≥5 |
| Notacja | J n z n nieparzystym |
| Tabela wykresów i parametrów | |
| Snark kwiatowy J 5 | |
|---|---|
 Snark kwiatowy J 5 .
| |
| Wierzchołki | 20 |
| Krawędzie | 30 |
| Obwód | 5 |
| Liczba chromatyczna | 3 |
| Indeks chromatyczny | 4 |
| Nieruchomości |
Snark Hypohamiltonian |
| Tabela wykresów i parametrów | |
W matematycznej dziedzinie teorii grafów snarks kwiatowe tworzą nieskończoną rodzinę snarksów wprowadzonych przez Rufusa Isaacsa w 1975 roku.
Jako snarki, snarki kwiatowe są spójnymi, bezmostkowymi grafami sześciennymi o indeksie chromatycznym równym 4. Snarki kwiatowe są niepłaskie i niehamiltonowskie . Snarki kwiatowe J 5 i J 7 mają grubość księgi 3 i numer kolejki 2.
Budowa
Snark kwiatu J n można skonstruować w następujący sposób:
- Zbuduj n kopii grafu gwiazdy na 4 wierzchołkach. Oznaczmy środkowy wierzchołek każdej gwiazdy A i oraz zewnętrzne wierzchołki B i , C i oraz D i . Daje to rozłączony graf na 4 n wierzchołkach z 3 n krawędziami (A i – B i , A i – C i oraz A i – Di dla 1 ≤ i ≤ n ).
- Skonstruuj n -cykl (B 1 ... B n ). To dodaje n krawędzi.
- Na koniec skonstruuj cykl 2n (C 1 ... C n D 1 ... D n ). To dodaje 2n krawędzi.
Z założenia Flower snark J n jest grafem sześciennym o 4 n wierzchołkach i 6 n krawędziach. Aby miał wymagane właściwości, n powinno być nieparzyste.
Przypadki specjalne
Nazwa kwiat snark jest czasami używana dla J 5 , snark kwiatu z 20 wierzchołkami i 30 krawędziami. Jest to jeden z 6 snarków na 20 wierzchołkach (sekwencja A130315 w OEIS ). Snark kwiatowy J 5 jest hipohamiltonowy .
J 3 jest trywialną odmianą grafu Petersena utworzoną przez zastąpienie jednego z jego wierzchołków trójkątem. Graf ten jest również znany jako wykres Tietze'a . Aby uniknąć trywialnych przypadków, snarks są generalnie ograniczone do obwodu co najmniej 5. Z tym ograniczeniem J 3 nie jest snark.
Galeria
Liczba chromatyczna snarka kwiatowego J 5 wynosi 3.
Indeks chromatyczny snarka kwiatowego J 5 wynosi 4.
Oryginalne przedstawienie snarka kwiatowego J 5 .
Graf Petersena jako graf moll snarka kwiatowego J 5
