Grafic tranzitiv de margine
În teoria grafurilor, muchia -tranzitivă este un graf G , pentru oricare două muchii dintre care e 1 și e 2 există un automorfism care mapează e 1 la e 2 [1] .
Cu alte cuvinte, un graf este tranzitiv de margine dacă grupul său de automorfism acționează tranzitiv asupra marginilor sale.
Exemple și proprietăți
Graficele tranzitive de muchie includ toate graficele bipartite complete și toate graficele simetrice , cum ar fi vârfurile și muchiile unui cub [1] . Graficele simetrice sunt, de asemenea, varf-tranzitive (dacă sunt conectate), dar, în general, graficele cu muchii-tranzitive nu sunt neapărat varf-tranzitive. Graficul Gray este un exemplu de graf care este tranzitiv la margine, dar nu tranzitiv la vârf. Toate astfel de grafice sunt bipartite [1] și, prin urmare, pot fi colorate doar cu două culori.
Un graf tranzitiv de muchie care este, de asemenea , regulat , dar nu tranzitiv la vârf, se numește semi-simetric . Contele Gray servește din nou drept exemplu. Un graf tranzitiv de muchie trebuie să fie bipartit și fie semi-simetric, fie biregular [2]
Vezi și
- Tranzitivitatea marginilor (în geometrie)
Note
- ↑ 1 2 3 Biggs, 1993 , p. 118.
- ↑ Lauri, 2003 , p. 20-21.
Literatură
- Biggs N. Teoria graficelor algebrice . — Ed. a II-a. - Cambridge, 1993. - ISBN 0-521-45897-8 .
- Lauri J. , Scapellato R. Topics in Graph Automorphisms and Reconstruction . - Cambridge University Press, 2003. - Vol. 54. - (London Mathematical Society. Texte studenților). — ISBN 9780521529037 .
Link -uri
- Weisstein, Eric W. Grafic tranzitiv Edge (engleză) pe site-ul web Wolfram MathWorld .