Puolitransitiivinen kaavio

Puolitransitiivinen graafi  on graafi , joka on sekä kärkitransitiivinen että reunatransitiivinen , mutta ei symmetrinen [1] . Toisin sanoen graafi on puolitransitiivinen, jos sen automorfismiryhmä toimii transitiivisesti sekä pisteissä että reunoissa, mutta ei järjestetyissä toisiinsa liittyvissä pistepareissa.

Minkä tahansa yhdistetyn symmetrisen graafin on oltava vertex-transitiivinen ja reunatransitiivinen . Päinvastoin pätee parittoman asteen kuvaajiin [2] , joten puolitransitiivisia parittoman asteen kuvaajia ei ole olemassa. On kuitenkin olemassa parillisen asteen transitiivisia kuvaajia [3] . Pienin puolitransitiivinen graafi on 4. asteen Holtin graafi , jossa on 27 kärkeä [4] [5] .

Muistiinpanot

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

Kirjallisuus

• Gross JL Yellen J. Graafiteorian käsikirja. - CRC Press, 2004. - ISBN 1-58488-090-2 .
• Babai L. Automorfismiryhmät, isomorfismi, rekonstruktio // Handbook of Combinatorics / Graham R., Grötschel M., Lovász L. - Elsevier, 1996.
• Norman Biggs. Algebrallinen graafiteoria. – 2. - Cambridge: Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
• Derek F. Holt. Kuvaaja, joka on reunatransitiivinen, mutta ei kaaritransitiivinen // Journal of Graph Theory. - 1981. - V. 5 , no. 2 . - doi : 10.1002/jgt.3190050210 .
• Bouwer Z. Vertex and Edge Transitive, But Not 1-Transitive Graphs // Kanada. Matematiikka. Bull .. - 1970. - T. 13 .