TOPICS
Search

Bouwer Graph


Bouwer graphs, a term coined here for the first time, are a family of regular graphs which includes members that are symmetric but not arc-transitive. Such graphs are termed 1/2-transitive by Alspach et al. (1994).

Bouwer's general construction of such graphs defines a graph B(N,m,n) with N>=2 and m,n>=2 such that 2^m=1 (mod n). The vertex set of this graph is identified with the Cartesian product

 Z_m×Z_n×...×Z_n_()_(N-1),

where Z_i denotes the ring of integers modulo i, and the edge set consists of pairs of N-tuples

 {(i,a_2,a_3,...,a_N),(i+1,b_2,b_3,...,b_N)}

for i=1, ..., m (with addition mod m) and a_i,b_i=2, ..., N such that either b_r=a_r for all r=2, 3, ..., N, or else there is exactly one s in {2,3,...,N} for which b_s!=a_s, in which case it is taken as b_s=a_s+2^i (mod n).

Such graphs are symmetric by construction, and include the following named graphs which are arc-transitive.

However, this class of graphs also includes members that are symmetric not not edge-transitive. Such graphs were first considered by Tutte (1966), who did not construct any, but showed that if it existed, any such graph must be regular of even degree. The first examples were therefore given by Bouwer (1970), who showed B(N,6,9) is a connected 2N-regular symmetric arc-intransitive graph for all integers N>=2. This class of graphs has 6·9^N vertices, giving graphs with vertex counts 54, 486, 4374, 39366, 354294, ... for N=2, 3, ....

BouwerGraph269

This smallest (N=2) example of such a graph is the quartic symmetric graph on 54 vertices illustrated above in several embeddings. This graph can be concisely described and constructed from the vertex set {(alpha,beta)|alpha in Z_6,beta in Z_9}, where (alpha,beta) is joined to (alpha+/-1,beta), (alpha+1,beta+2^alpha), and (alpha-1,beta-2^(alpha-1)) (Holt 1981).

Dolye (1976) and Holt (1981) subsequently discovered the smaller symmetric arc-intransitive graph now known as the Doyle graph, which can be obtained from Bouwer's 54-vertex graph by contracting pairs of diametrically opposed vertices (Doyle 1998).

A partial tabulation of small symmetric arc-intransitive graphs constructed using Brouwer's method is given in the following table (Weisstein, Nov. 17, 2010), where v is the vertex count. These graphs will are implemented in the Wolfram Language as GraphData[{"Bouwer", {N, m, n}}].

vB(N,m,n)
54B(2,6,9)
60B(2,4,15)
63B(2,9,7)
84B(2,12,7)
100B(3,4,5)

See also

Arc-Transitive Graph, Doyle Graph, Symmetric Graph

Explore with Wolfram|Alpha

References

Alspach, B.; Marušič, Dragan; and Nowitz, L. (1994), "Constructing Graphs which are 1/2-Transitive." J. Austral. Math. Soc. 56, 391-402, 1994.Bouwer, I. Z. "Vertex and Edge Transitive, But Not 1-Transitive Graphs." Canad. Math. Bull. 13, 231-237, 1970.Doyle, P. G. On Transitive Graphs. Senior Thesis. Cambridge, MA, Harvard College, April 1976.Doyle, P. "A 27-Vertex Graph That Is Vertex-Transitive and Edge-Transitive But Not L-Transitive." October 1998. http://arxiv.org/abs/math/0703861.Holt, D. F. "A Graph Which Is Edge Transitive But Not Arc Transitive." J. Graph Th. 5, 201-204, 1981.Tutte, W. T. Connectivity in Graphs. Toronto, CA: University of Toronto Press, 1966.

Referenced on Wolfram|Alpha

Bouwer Graph

Cite this as:

Weisstein, Eric W. "Bouwer Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/BouwerGraph.html

Subject classifications