Kanttransitiv graf
I grafteori er kant - transitiv en graf G , for hvilke som helst to kanter, hvoraf e 1 og e 2 er en automorfi , der kortlægger e 1 til e 2 [1] .
Med andre ord er en graf kanttransitiv, hvis dens automorfigruppe virker transitivt på dens kanter.
Eksempler og egenskaber
Kanttransitive grafer inkluderer alle komplette todelte grafer og alle symmetriske grafer , såsom hjørnerne og kanterne af en terning [1] . Symmetriske grafer er også toppunkttransitive (hvis de er forbundet), men generelt er kanttransitive grafer ikke nødvendigvis toppunkttransitive. Den grå graf er et eksempel på en graf, der er kanttransitiv, men ikke toppunkttransitiv. Alle sådanne grafer er todelte [1] og kan derfor kun farves med to farver.
En kanttransitiv graf, der også er regulær , men ikke vertextransitiv, kaldes semisymmetrisk . Grev Grey tjener igen som eksempel. En kanttransitiv graf skal være todelt og enten semisymmetrisk eller biregulær [2]
Se også
- Edge transitivity (i geometri)
Noter
- ↑ 1 2 3 Biggs, 1993 , s. 118.
- ↑ Lauri, 2003 , s. 20-21.
Litteratur
- Biggs N. Algebraisk grafteori . — 2. udg. - Cambridge, 1993. - ISBN 0-521-45897-8 .
- Lauri J. , Scapellato R. Emner i grafautomorfismer og rekonstruktion . - Cambridge University Press, 2003. - Vol. 54. - (London Mathematical Society. Student Texts). — ISBN 9780521529037 .
Links
- Weisstein, Eric W. Edge-transitive graph (engelsk) på Wolfram MathWorld -webstedet .