Recall that there exist algorithms to decompose any polynomial over Z into a product of polynomials over Z all of which are irreducible over Q (see [Esc01]). If a polynomial is not irreducible, it's not always easy to find its Galois group in terms of the Galois groups of its irreducible factors, so we focus on (monic) irreducible polynomials in what follows. The irreducible parts of the graph's adjacency matrix's characteristic polynomial can be used to compute the Galois group of a corresponding field extension.

As we all know from algebra the following theorem holds:

See [Hul01b] for more information about transitive permutation groups. And by the way remember that the study of an arbitrary group can be reduced to that of transitive groups (as a (sub)direct product), and imprimitive groups are built (embedded in the wreath product) from primitive components (not uniquely determined).

The following example polynomial arises in the 'quasi_1' example:

gap>x:=Indeterminate(Rationals);;
gap>f:=-41 - 100*x + 284*x^2 + 694*x^3 + 40*x^4 - 661*x^5 - 258*x^6 + 
	     218*x^7 + 119*x^8 - 27*x^9 - 19*x^10 + x^11 + x^12;
gap>GaloisType(f);
299
gap>TransitiveGroup(12,299);
  [S(6)^2]2=S(6)wr2  

So we just encountered the wreath product S(6) ≀ C(2). And KASH™ can do it as well:

kash% Galois(f);
  "[S(6)^2]2", extended by:
  ext1 := 12,
  ext2 := 299,
  ext3 := [
    (8*w + 1)*w^2 + (8*w + 12)*w + 15*w,
    (14*w + 12)*w^2 + (15*w + 16)*w + 2*w,
    (11*w + 11)*w^2 + (3*w + 8)*w + 15*w,
    (3*w + 12)*w^2 + (16*w + 14)*w + 2*w,
    (15*w + 5)*w^2 + (6*w + 14)*w + 15*w,
    10*w^2 + (3*w + 4)*w + 2*w,
    (5*w + 15)*w^2 + (5*w + 13)*w + 12*w + 14,
    (4*w + 12)*w^2 + (6*w + 6)*w + 5*w + 14,
    (10*w + 5)*w^2 + (15*w + 15)*w + 12*w + 14,
    (8*w + 4)*w^2 + (9*w + 16)*w + 5*w + 14,
    (2*w + 14)*w^2 + (14*w + 6)*w + 12*w + 14,
    (5*w + 1)*w^2 + (2*w + 12)*w + 5*w + 14
    ],
  ext4 := 17
Time: 0.550028 s 
kash% Discriminant(f);
364686337094564303371953125

It seems that all our polynomials have only real roots, that is to say the signature (the number of real roots) equals the polynomial's degree. Why?

Here are some tabled results (available up to degree 23):

Well, the last two results follow a different notation.

And the following polynomials arise as minimal polynomials from the Cartan matrices for the Lie algebras E6, E7 and E8 (see Chapter 13, Lie Groups and Algebras):

kash% Galois(1 - 16*X + 20*X^2 - 8*X^3 + X^4);
"E(4)"
gap>l:=AllTransitiveGroups(Size, 4);
[ C(4) = 4, E(4) = 2[x]2 ]
kash% Galois(1 - 36*X + 105*X^2 - 112*X^3 + 54*X^4 - 12*X^5 + X^6);
"C(6) = 6 = 3[X]2"
kash% f:=1 - 96*X + 440*X^2 - 784*X^3 + 714*X^4 - 364*X^5 + 105*X^6 - 16*X^7 + X^8;
kash% Galois(f);
"4[X]2", extended by:
  ext1 := 8,
  ext2 := 2,
  ext3 :=
   [ 17*w + 2, 9*w + 2, 7*w + 2, 20*w + 2, 22*w + 2, 18*w + 2, 12*w + 2, 11*w + 2 ],
  ext4 := 29
Time: 0.1576 s
kash% Discriminant(f);
324000000
Time: 0.000357 s

So here come say hello to a world champion. See the hall of fame records in the online database [Mal01] for polynomials up to degree 15 with given Galois group, signature and minimal (absolute) discriminant. Maybe our geometrical realizations could be a starting point for further investigations.