Polotranzitivní graf

Polotranzitivní graf  je graf , který je jak vertex-tranzitivní , tak hranově tranzitivní , ale není symetrický [1] . Jinými slovy, graf je semi-tranzitivní, pokud jeho skupina automorfismu působí tranzitivně jak na vrcholy, tak na hrany, ale ne na uspořádané dvojice spojených vrcholů.

Jakýkoli připojený symetrický graf musí být vertex-transitive a edge-transitive . Pro grafy lichého stupně [2] to platí naopak , semitranzitivní grafy lichého stupně tedy neexistují. Existují však tranzitivní grafy sudého stupně [3] . Nejmenším semitranzitivním grafem je Holtův graf stupně 4 s 27 vrcholy [4] [5] .

Poznámky

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

Literatura

• Gross JL Yellenová J. Příručka teorie grafů. - CRC Press, 2004. - ISBN 1-58488-090-2 .
• Babai L. Skupiny automorfismu, izomorfismus, rekonstrukce // Handbook of Combinatorics / Graham R., Grötschel M., Lovász L. — Elsevier, 1996.
• Norman Biggs. Algebraická teorie grafů. — 2. - Cambridge: Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
• Derek F. Holt. Graf, který je přechodově přechodný, ale není přechodný obloukem // ​​Journal of Graph Theory. - 1981. - V. 5 , čís. 2 . - doi : 10.1002/jgt.3190050210 .
• Bouwer Z. Vertex a Edge Transitive, ale ne 1-tranzitivní grafy // Kanada. Matematika. Bull .. - 1970. - T. 13 .