SAGE code

SAGE is free open-source mathematics software that can be found at: http://www.sagemath.org/.

While doing research for my masters thesis, I used the following simple routines to construct some interesting vertex-transitive conference graphs.

The Paley graphs are a well-studied family of graphs. The Peisert graphs were introduced in a paper by Peisert in 2001, and the semifield graphs were first described in a paper by Weng, Qiu, Wang, and Xiang in 2007.

There is one little subtraction method that I use in the semifield graph constructions. (There is probably a better way to get around this.)

def subt(x,y):
  "Subtracts vectors, component-wise"
  return (x[0] - y[0],x[1]-y[1])

PALEY GRAPHS

This construction is valid when q is the power of an odd prime such that q is equivalent to 1 modulo 4.

def Paley(q):
  K.<a> = FiniteField(q)
  return Graph([K, lambda i,j: (i-j).is_square()])

PEISERT GRAPHS

This construction is valid when p is an odd prime congruent to 3 modulo 4 and r is an positive even integer.

def Peisert(p,r):
  q = p^r
  K.<a> = FiniteField(q)
  pows = [a^(4*i) for i in [1..(q^2-1)/4]] + [a^(4*i+1) for i in [1..(q^2-1)/4]]
  return Graph([K, lambda i,j: i-j in pows])

DICKSON SEMIFIELD GRAPHS

This construction is valid when p is an odd prime and r >=1. The resulting graph will have order p^(2r). (Although if r=1, the resulting graph will be isomorphic to the Paley graph of the same order.)

def DicksonSRG(p,r):
  K.<a> = FiniteField(p^r)
  V = [(x,y) for x in K for y in K]
  D = [(x^2 + a*y^(2*p), 2*x*y) for x in K for y in K]
  return Graph([V, lambda i,j: i != j and subt(i,j) in D])

GANLEY SEMIFIELD GRAPHS

This construction is valid when r>=3 and r is odd. The resulting graph will have order 3^(2r).

def GanleySRG(r):
  K.<a> = FiniteField(3^r)
  V = [(x,y) for x in K for y in K]
  D = [(x^2 + y^10, 2*x*y + y^6) for x in K for y in K]
  return Graph([V, lambda i,j: i != j and subt(i,j) in D])

COHEN-GANLEY SEMIFIELD GRAPHS

This construction is valid when r >=2 and r is odd. The resulting graph will have order 3^(2r).

def CGSRG(r):
  K.<a> = FiniteField(3^r)
  V = [(x,y) for x in K for y in K]
  D = [(x^2 + a*y^2 + a^3*y^18, 2*x*y + a*y^6) for x in K for y in K]
  return Graph([V, lambda i,j: i != j and subt(i,j) in D])

PENTILLA-WILLIAMS SEMIFIELD GRAPH

The graph resulting from this construction will have order 3^(2r).

def PWSRG():
  K.<a> = FiniteField(3^5)
  V = [(x,y) for x in K for y in K]
  D = [(x^2 + y^18, 2*x*y + y^54) for x in K for y in K]
  return Graph([V, lambda i,j: i != j and subt(i,j) in D])