Halvtransitiv graf

Graffamiljer definierade av deras automorfismer
distanstransitiv	→	avstånd-regelbundet	←	starkt regelbunden
↓
symmetrisk (bågtransitiv)	←	t -transitiv, t ≥ 2		snedsymmetrisk
↓
(om ansluten) vertex- och kanttransitiv	→	kanttransitiv och regelbunden	→	kanttransitiv
↓		↓		↓
vertextransitiv	→	regelbunden	→	(om tvådelad) biregelbunden
↑
Cayley graf	←	nollsymmetrisk		asymmetrisk

Inom det matematiska området grafteorin är en halvtransitiv graf en graf som är både vertextransitiv och kanttransitiv , men inte symmetrisk . Med andra ord är en graf halvtransitiv om dess automorfismgrupp verkar transitivt på både dess hörn och dess kanter, men inte på ordnade par av länkade hörn.

Holt -grafen är den minsta halvtransitiva grafen. Bristen på reflektionssymmetri i denna ritning framhäver det faktum att kanterna inte är ekvivalenta med deras invers.

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