110-vertex Iofinova-Ivanov-graf

110-vertex Iofinova-Ivanov-graf
110-vertex Iofinova-Ivanov-graf
Vertices	110
Kanter	165
Radie	7
Diameter	7
Omkrets	10
Automorfismer	1320 (PGL 2 (11))
Kromatiskt nummer	2
Kromatiskt index	3
Egenskaper	; ; ; halvsymmetrisk tvådelad kubisk Hamiltonian
	Tabell över grafer och parametrar

Iofinova-Ivanov-grafen med 110 hörn är , i grafteorin , en semisymmetrisk kubisk graf med 110 hörn och 165 kanter.

Egenskaper

Iofinova och Ivanov bevisade 1985 existensen av fem och endast fem semisymmetriska kubiska tvådelade grafer vars automorfismgrupper verkar primitivt på varje partition. Den minsta har 110 hörn. De andra har 126, 182, 506 och 990. Iofinova-Ivanov-grafen med 126 vertex är också känd som Tutte 12-buren .

Diametern på Iofinova-Ivanov-grafen med 110 vertex, det största avståndet mellan ett par av hörn, är 7. Dess radie är likaså 7. Dess omkrets är 10.

Det är 3-anslutet och 3-kant-anslutet: för att göra det frånkopplat måste minst tre kanter, eller minst tre hörn, tas bort.

Färg

Det kromatiska numret på 110-vertex Iofina-Ivanov-grafen är 2: dess hörn kan vara 2-färgade så att inga två hörn av samma färg förenas med en kant. Dess kromatiska index är 3: dess kanter kan vara 3-färgade så att inte två kanter av samma färg möts vid en vertex.

Algebraiska egenskaper

Det karakteristiska polynomet för Iofina-Ivanov-grafen med 110 vertex är $(x-3)x^{20}(x+3)(x^{4}-8x^{2}+11)^{12}(x^{4}-6x^{2}+6)^ {10}$ . Symmetrigruppen för Iofina-Ivanov med 110 vertex är den projektiva linjära gruppen PGL ₂ (11), med 1320 element.

Semi-symmetri

Få grafer visar semisymmetri: de flesta kanttransitiva grafer är också vertextransitiva. Den minsta semisymmetriska grafen är Folkman-grafen , med 20 hörn, vilket är 4-regelbundet. De tre minsta kubiska semisymmetriska graferna är den grå grafen , med 54 hörn, denna den minsta av Iofina-Ivanov-graferna med 110 och Ljubljana-grafen med 112. Det är bara för de fem Iofina-Ivanov-graferna som symmetrigruppen verkar primitivt på varje partition av hörnen.

Bibliografi

Iofinova, ME och Ivanov, AA Bi-Primitive Cubic Graphs. I Undersökningar i den algebraiska teorin om kombinatoriska objekt . s. 123–134, 2002. (Vsesoyuz. Nauchno-Issled. Inst. Sistem. Issled., Moskva, s. 137–152, 1985.)
Ivanov, AA Beräkning av längder av banor för en undergrupp i en transitiv permutationsgrupp. I Metoder för komplexa systemstudier . Moskva: VNIISI, s. 3–7, 1983.
Ivanov, AV On Edge Men Inte Vertex Transitive Regular Graphs. I Combinatorial Design Theory (Ed. CJ Colbourn och R. Mathon). Amsterdam, Nederländerna: North-Holland, s. 273–285, 1987.