Rodiny grafů definované jejich automorfismy | ||||
---|---|---|---|---|
vzdálenost-tranzitivní | → | pravidelná vzdálenost | ← | velmi pravidelné |
↓ | ||||
symetrický (oblouk-tranzitivní) | ← | t -transitivní, ( t ≥ 2) | symetrický vlevo (v) | |
↓ | ||||
(je-li připojen) vrchol-tranzitivní a hrana-tranzitivní |
→ | pravidelné a hranové tranzitivní | → | hrana tranzitivní |
↓ | ↓ | ↓ | ||
top-tranzitivní | → | pravidelný | → |
(je-li bipartitní) biregular |
↑ | ||||
Cayleyův graf | ← | nulově symetrický | asymetrický |
V teorii grafů je asymetrický graf nebo graf identity graf, jehož skupina automorfismů je triviální . Jde tedy o graf, který nepřipouští žádný jiný autorfismus než identitu.
Nejmenší asymetrický graf je singletonový graf , který je také symetrickým grafem . Vyloučíme-li tento triviální případ, musí mít asymetrický graf alespoň 6 vrcholů. Existuje 8 odlišných asymetrických grafů až po izomorfismus pro objednávku 6, 152 pro objednávku 7, 3696 pro objednávku 8, 135 004 pro objednávku 9, 7 971 848 pro objednávku 10 a 805 364 776 pro objednávku 11.
Mezi kubickými grafy je nejmenším asymetrickým grafem Fruchtův graf . Má 12 vrcholů.
Asymetrické jsou také Kittellův graf , Heawoodův 4-chromatický graf a Waltherův graf .