Semi-transitiv graf

En semi-transitiv graf  er en graf , der både er toppunkttransitiv og kanttransitiv , men ikke symmetrisk [1] . Med andre ord er en graf semi-transitiv, hvis dens automorfigruppe virker transitivt på både toppunkter og kanter, men ikke på ordnede par af forbundne toppunkter.

Enhver tilsluttet symmetrisk graf skal være toppunkttransitiv og kanttransitiv . Det omvendte gælder for grafer med ulige grader [2] , så semi-transitive grafer med ulige grader eksisterer ikke. Der er dog transitive grafer af lige grad [3] . Den mindste semi-transitive graf er Holt-grafen af ​​grad 4 med 27 hjørner [4] [5] .

Noter

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

Litteratur