Semi-transitiv graf

En semi-transitiv graf  är en graf som är både vertextransitiv och kanttransitiv , men inte symmetrisk [1] . Med andra ord är en graf semi-transitiv om dess automorfismgrupp verkar transitivt på både hörn och kanter, men inte på ordnade par av sammankopplade hörn.

Varje ansluten symmetrisk graf måste vara vertextransitiv och kanttransitiv . Det omvända är sant för grafer av udda grad [2] , så semi-transitiva grafer av udda grad existerar inte. Det finns dock transitiva grafer av jämn grad [3] . Den minsta semi-transitiva grafen är Holt-grafen av grad 4 med 27 hörn [4] [5] .

Anteckningar

1. ↑ Gross, Yellen, 2004 , sid. 491.
2. ↑ Babai, 1996 .
3. ↑ Bouwer, 1970 , sid. 231-237.
4. ↑ Biggs, 1993 .
5. ↑ Holt, 1981 , sid. 201–204.

Litteratur

• Gross JL Yellen J. Handbook of Graph Theory. - CRC Press, 2004. - ISBN 1-58488-090-2 .
• Babai L. Automorfismgrupper, isomorfism, rekonstruktion // Handbook of Combinatorics / Graham R., Grötschel M., Lovász L. — Elsevier, 1996.
• Norman Biggs. Algebraisk grafteori. — 2:a. - Cambridge: Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
• Derek F. Holt. En graf som är kanttransitiv men inte bågtransitiv //Journal of Graph Theory. - 1981. - V. 5 , nr. 2 . - doi : 10.1002/jgt.3190050210 .
• Bouwer Z. Vertex och Edge Transitive, But Not 1-Transitive Graphs // Kanada. Matematik. Bull .. - 1970. - T. 13 .