Grafic semi-tranzitiv

Un graf semi-tranzitiv  este un graf care este atât tranzitiv la vârf, cât și tranzitiv la margine , dar nu simetric [1] . Cu alte cuvinte, un graf este semi-tranzitiv dacă grupul său de automorfism acționează tranzitiv atât asupra vârfurilor cât și asupra muchiilor, dar nu asupra perechilor ordonate de vârfuri conectate.

Orice graf simetric conectat trebuie să fie tranzitiv la vârf și tranzitiv la muchie . Reversul este valabil pentru graficele de grad impar [2] , deci nu există grafice semi-tranzitive de grad impar. Cu toate acestea, există grafice tranzitive de grad par [3] . Cel mai mic grafic semi-tranzitiv este graficul Holt de gradul 4 cu 27 de vârfuri [4] [5] .

Note

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

Literatură

• Gross JL Yellen J. Handbook of Graph Theory. - CRC Press, 2004. - ISBN 1-58488-090-2 .
• Babai L. Automorphism groups, izomorfism, reconstruction // Handbook of Combinatorics / Graham R., Grötschel M., Lovász L. — Elsevier, 1996.
• Norman Biggs. Teoria algebrică a graficelor. — al 2-lea. - Cambridge: Cambridge University Press, 1993. - ISBN 0-521-45897-8 .
• Derek F. Holt. Un grafic care este tranzitiv la margine, dar nu este tranzitiv în arc // ​​Journal of Graph Theory. - 1981. - V. 5 , nr. 2 . - doi : 10.1002/jgt.3190050210 .
• Bouwer Z. Grafice tranzitive de vârf și margini, dar nu 1-tranzitive // ​​Canada. Matematică. Bull .. - 1970. - T. 13 .