Various families of graphs¶
The methods defined here appear in sage.graphs.graph_generators
.

sage.graphs.generators.families.
AztecDiamondGraph
(n)¶ Return the Aztec Diamond graph of order
n
.See the Wikipedia article Aztec_diamond for more information.
EXAMPLES:
sage: graphs.AztecDiamondGraph(2) Aztec Diamond graph of order 2 sage: [graphs.AztecDiamondGraph(i).num_verts() for i in range(8)] [0, 4, 12, 24, 40, 60, 84, 112] sage: [graphs.AztecDiamondGraph(i).num_edges() for i in range(8)] [0, 4, 16, 36, 64, 100, 144, 196] sage: G = graphs.AztecDiamondGraph(3) sage: sum(1 for p in G.perfect_matchings()) 64

sage.graphs.generators.families.
BalancedTree
(r, h)¶ Returns the perfectly balanced tree of height \(h \geq 1\), whose root has degree \(r \geq 2\).
The number of vertices of this graph is \(1 + r + r^2 + \cdots + r^h\), that is, \(\frac{r^{h+1}  1}{r  1}\). The number of edges is one less than the number of vertices.
INPUT:
r
– positive integer \(\geq 2\). The degree of the root node.h
– positive integer \(\geq 1\). The height of the balanced tree.
OUTPUT:
The perfectly balanced tree of height \(h \geq 1\) and whose root has degree \(r \geq 2\). A
NetworkXError
is returned if \(r < 2\) or \(h < 1\).ALGORITHM:
Uses NetworkX.
EXAMPLES:
A balanced tree whose root node has degree \(r = 2\), and of height \(h = 1\), has order 3 and size 2:
sage: G = graphs.BalancedTree(2, 1); G Balanced tree: Graph on 3 vertices sage: G.order(); G.size() 3 2 sage: r = 2; h = 1 sage: v = 1 + r sage: v; v  1 3 2
Plot a balanced tree of height 5, whose root node has degree \(r = 3\):
sage: G = graphs.BalancedTree(3, 5) sage: G.show() # long time
A tree is bipartite. If its vertex set is finite, then it is planar.
sage: r = randint(2, 5); h = randint(1, 7) sage: T = graphs.BalancedTree(r, h) sage: T.is_bipartite() True sage: T.is_planar() True sage: v = (r^(h + 1)  1) / (r  1) sage: T.order() == v True sage: T.size() == v  1 True

sage.graphs.generators.families.
BarbellGraph
(n1, n2)¶ Returns a barbell graph with
2*n1 + n2
nodes. The argumentn1
must be greater than or equal to 2.A barbell graph is a basic structure that consists of a path graph of order
n2
connecting two complete graphs of ordern1
each.INPUT:
n1
– integer \(\geq 2\). The order of each of the two complete graphs.n2
– nonnegative integer. The order of the path graph connecting the two complete graphs.
OUTPUT:
A barbell graph of order
2*n1 + n2
. AValueError
is returned ifn1 < 2
orn2 < 0
.PLOTTING:
Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, each barbell graph will be displayed with the two complete graphs in the lowerleft and upperright corners, with the path graph connecting diagonally between the two. Thus the
n1
th node will be drawn at a 45 degree angle from the horizontal right center of the first complete graph, and then1 + n2 + 1
th node will be drawn 45 degrees below the left horizontal center of the second complete graph.EXAMPLES:
Construct and show a barbell graph
Bar = 4
,Bells = 9
:sage: g = graphs.BarbellGraph(9, 4); g Barbell graph: Graph on 22 vertices sage: g.show() # long time
An
n1 >= 2
,n2 >= 0
barbell graph has order2*n1 + n2
. It has the complete graph onn1
vertices as a subgraph. It also has the path graph onn2
vertices as a subgraph.sage: n1 = randint(2, 2*10^2) sage: n2 = randint(0, 2*10^2) sage: g = graphs.BarbellGraph(n1, n2) sage: v = 2*n1 + n2 sage: g.order() == v True sage: K_n1 = graphs.CompleteGraph(n1) sage: P_n2 = graphs.PathGraph(n2) sage: s_K = g.subgraph_search(K_n1, induced=True) sage: s_P = g.subgraph_search(P_n2, induced=True) sage: K_n1.is_isomorphic(s_K) True sage: P_n2.is_isomorphic(s_P) True

sage.graphs.generators.families.
BubbleSortGraph
(n)¶ Returns the bubble sort graph \(B(n)\).
The vertices of the bubble sort graph are the set of permutations on \(n\) symbols. Two vertices are adjacent if one can be obtained from the other by swapping the labels in the \(i\)th and \((i+1)\)th positions for \(1 \leq i \leq n1\). In total, \(B(n)\) has order \(n!\). Swapping two labels as described previously corresponds to multiplying on the right the permutation corresponding to the node by an elementary transposition in the
SymmetricGroup
.The bubble sort graph is the underlying graph of the
permutahedron()
.INPUT:
n
– positive integer. The number of symbols to permute.
OUTPUT:
The bubble sort graph \(B(n)\) on \(n\) symbols. If \(n < 1\), a
ValueError
is returned.EXAMPLES:
sage: g = graphs.BubbleSortGraph(4); g Bubble sort: Graph on 24 vertices sage: g.plot() # long time Graphics object consisting of 61 graphics primitives
The bubble sort graph on \(n = 1\) symbol is the trivial graph \(K_1\):
sage: graphs.BubbleSortGraph(1) Bubble sort: Graph on 1 vertex
If \(n \geq 1\), then the order of \(B(n)\) is \(n!\):
sage: n = randint(1, 8) sage: g = graphs.BubbleSortGraph(n) sage: g.order() == factorial(n) True
See also
AUTHORS:
Michael Yurko (20090901)

sage.graphs.generators.families.
CaiFurerImmermanGraph
(G, twisted=False)¶ Return the a CaiFurerImmerman graph from \(G\), possibly a twisted one, and a partition of its nodes.
A CaiFurerImmerman graph from/on \(G\) is a graph created by applying the transformation described in [CFI1992] on a graph \(G\), that is substituting every vertex v in \(G\) with a Furer gadget \(F(v)\) of order d equal to the degree of the vertex, and then substituting every edge \((v,u)\) in \(G\) with a pair of edges, one connecting the two “a” nodes of \(F(v)\) and \(F(u)\) and the other their two “b” nodes. The returned coloring of the vertices is made by the union of the colorings of each single Furer gadget, individualised for each vertex of \(G\). To understand better what these “a” and “b” nodes are, see the documentation on Furer gadgets.
Furthermore, this method can apply what is described in the paper mentioned above as a “twist” on an edge, that is taking only one of the pairs of edges introduced in the new graph and swap two of their extremes, making each edge go from an “a” node to a “b” node. This is only doable if the original graph G is connected.
A CaiFurerImmerman graph on a graph with no balanced vertex separators smaller than s and its twisted version cannot be distinguished by kWL for any k < s.
INPUT:
G
– An undirected graph on which to construct theCaiFurerImmerman graph
twisted
– A boolean indicating if the version to constructis a twisted one or not
OUTPUT:
H
– The CaiFurerImmerman graph onG
coloring
– A list of list of vertices, representing thepartition induced by the coloring on
H
EXAMPLES:
CaiFurerImmerman graph with no balanced vertex separator smaller than 2
sage: G = graphs.CycleGraph(4) sage: CFI, p = graphs.CaiFurerImmermanGraph(G) sage: sorted(CFI, key=str) [(0, ()), (0, (0, 'a')), (0, (0, 'b')), (0, (0, 1)), (0, (1, 'a')), (0, (1, 'b')), (1, ()), (1, (0, 'a')), (1, (0, 'b')), (1, (0, 1)), (1, (1, 'a')), (1, (1, 'b')), (2, ()), (2, (0, 'a')), (2, (0, 'b')), (2, (0, 1)), (2, (1, 'a')), (2, (1, 'b')), (3, ()), (3, (0, 'a')), (3, (0, 'b')), (3, (0, 1)), (3, (1, 'a')), (3, (1, 'b'))] sage: sorted(CFI.edge_iterator(), key=str) [((0, ()), (0, (0, 'b')), None), ((0, ()), (0, (1, 'b')), None), ((0, (0, 'a')), (1, (0, 'a')), None), ((0, (0, 'b')), (1, (0, 'b')), None), ((0, (0, 1)), (0, (0, 'a')), None), ((0, (0, 1)), (0, (1, 'a')), None), ((0, (1, 'a')), (3, (0, 'a')), None), ((0, (1, 'b')), (3, (0, 'b')), None), ((1, ()), (1, (0, 'b')), None), ((1, ()), (1, (1, 'b')), None), ((1, (0, 1)), (1, (0, 'a')), None), ((1, (0, 1)), (1, (1, 'a')), None), ((1, (1, 'a')), (2, (0, 'a')), None), ((1, (1, 'b')), (2, (0, 'b')), None), ((2, ()), (2, (0, 'b')), None), ((2, ()), (2, (1, 'b')), None), ((2, (0, 1)), (2, (0, 'a')), None), ((2, (0, 1)), (2, (1, 'a')), None), ((2, (1, 'a')), (3, (1, 'a')), None), ((2, (1, 'b')), (3, (1, 'b')), None), ((3, ()), (3, (0, 'b')), None), ((3, ()), (3, (1, 'b')), None), ((3, (0, 1)), (3, (0, 'a')), None), ((3, (0, 1)), (3, (1, 'a')), None)]

sage.graphs.generators.families.
CirculantGraph
(n, adjacency)¶ Returns a circulant graph with n nodes.
A circulant graph has the property that the vertex \(i\) is connected with the vertices \(i+j\) and \(ij\) for each j in
adjacency
.INPUT:
n
 number of vertices in the graphadjacency
 the list of j values
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, each circulant graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.
Filling the position dictionary in advance adds O(n) to the constructor.
See also
sage.graphs.generic_graph.GenericGraph.is_circulant()
– checks whether a (di)graph is circulant, and/or returns all possible sets of parameters.
EXAMPLES: Compare plotting using the predefined layout and networkx:
sage: import networkx sage: n = networkx.cycle_graph(23) sage: spring23 = Graph(n) sage: posdict23 = graphs.CirculantGraph(23,2) sage: spring23.show() # long time sage: posdict23.show() # long time
We next view many cycle graphs as a Sage graphics array. First we use the
CirculantGraph
constructor, which fills in the position dictionary:sage: g = [] sage: j = [] sage: for i in range(9): ....: k = graphs.CirculantGraph(i+4, i+1) ....: g.append(k) sage: for i in range(3): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) sage: G = graphics_array(j) sage: G.show() # long time
Compare to plotting with the springlayout algorithm:
sage: g = [] sage: j = [] sage: for i in range(9): ....: spr = networkx.cycle_graph(i+3) ....: k = Graph(spr) ....: g.append(k) sage: for i in range(3): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) sage: G = graphics_array(j) sage: G.show() # long time
Passing a 1 into adjacency should give the cycle.
sage: graphs.CirculantGraph(6,1)==graphs.CycleGraph(6) True sage: graphs.CirculantGraph(7,[1,3]).edges(labels=false) [(0, 1), (0, 3), (0, 4), (0, 6), (1, 2), (1, 4), (1, 5), (2, 3), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5), (5, 6)]

sage.graphs.generators.families.
CubeConnectedCycle
(d)¶ Return the cubeconnected cycle of dimension \(d\).
The cubeconnected cycle of order \(d\) is the \(d\)dimensional hypercube with each of its vertices replaced by a cycle of length \(d\). This graph has order \(d \times 2^d\). The construction is as follows: Construct vertex \((x,y)\) for \(0 \leq x < 2^d\), \(0 \leq y < d\). For each vertex, \((x,y)\), add an edge between it and \((x, (y1) \mod d))\), \((x,(y+1) \mod d)\), and \((x \oplus 2^y, y)\), where \(\oplus\) is the bitwise xor operator.
For \(d=1\) and \(2\), the cubeconnected cycle graph contains selfloops or multiple edges between a pair of vertices, but for all other \(d\), it is simple.
INPUT:
d
– The dimension of the desired hypercube as well as the length of the cycle to be placed at each vertex of the \(d\)dimensional hypercube. \(d\) must be a positive integer.
EXAMPLES:
The order of the graph is \(d \times 2^d\)
sage: d = 3 sage: g = graphs.CubeConnectedCycle(d) sage: len(g) == d*2**d True
The diameter of cubeconnected cycles for \(d > 3\) is \(2d + \lfloor \frac{d}{2} \rfloor  2\)
sage: d = 4 sage: g = graphs.CubeConnectedCycle(d) sage: g.diameter() == 2*d+d//22 True
All vertices have degree \(3\) when \(d > 1\)
sage: g = graphs.CubeConnectedCycle(5) sage: all(g.degree(v) == 3 for v in g) True

sage.graphs.generators.families.
CubeGraph
(n)¶ Returns the hypercube in \(n\) dimensions.
The hypercube in \(n\) dimension is build upon the binary strings on \(n\) bits, two of them being adjacent if they differ in exactly one bit. Hence, the distance between two vertices in the hypercube is the Hamming distance.
EXAMPLES:
The distance between \(0100110\) and \(1011010\) is \(5\), as expected
sage: g = graphs.CubeGraph(7) sage: g.distance('0100110','1011010') 5
Plot several \(n\)cubes in a Sage Graphics Array
sage: g = [] sage: j = [] sage: for i in range(6): ....: k = graphs.CubeGraph(i+1) ....: g.append(k) ... sage: for i in range(2): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) ... sage: G = graphics_array(j) sage: G.show(figsize=[6,4]) # long time
Use the plot options to display larger \(n\)cubes
sage: g = graphs.CubeGraph(9) sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20) # long time
AUTHORS:
Robert Miller

sage.graphs.generators.families.
DipoleGraph
(n)¶ Returns a dipole graph with n edges.
A dipole graph is a multigraph consisting of 2 vertices connected with n parallel edges.
EXAMPLES:
Construct and show a dipole graph with 13 edges:
sage: g = graphs.DipoleGraph(13); g Dipole graph: Multigraph on 2 vertices sage: g.show() # long time

sage.graphs.generators.families.
DorogovtsevGoltsevMendesGraph
(n)¶ Construct the nth generation of the DorogovtsevGoltsevMendes graph.
EXAMPLES:
sage: G = graphs.DorogovtsevGoltsevMendesGraph(8) sage: G.size() 6561
REFERENCE:
[1] Dorogovtsev, S. N., Goltsev, A. V., and Mendes, J. F. F., Pseudofractal scalefree web, Phys. Rev. E 066122 (2002).

sage.graphs.generators.families.
DoubleGeneralizedPetersenGraph
(n, k)¶ Return a double generalized Petersen graph with \(4n\) nodes.
The double generalized Petersen graphs is a family of graphs proposed in [ZF2012] as a variant of generalized Petersen graphs. The variables \(n\), \(k\) are integers such that \(n > 2\) and \(0 < k \leq \lfloor (n1) / 2 \rfloor\).
INPUT:
n
– the number of nodes is \(4 * n\)k
– integer such that \(0 < k \leq \lfloor (n1) / 2 \rfloor\) determining how vertices on second and third inner rims are connected
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, the double generalized Petersen graphs are displayed as 4 cocentric cycles, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outercircle, moving counterclockwise after that. The second circle is drawn with the (n)th node at the top, then counterclockwise as well. The tird cycle is drawn with the (2n)th node at the top, then counterclockwise. And the fourth cycle is drawn with the (3n)th node at the top, then again counterclockwise.
EXAMPLES:
When \(n\) is even the resulting graph will be isomorphic to a double generalized Petersen graph with \(k' = n / 2  k\):
sage: g = graphs.DoubleGeneralizedPetersenGraph(10, 2) sage: g2 = graphs.DoubleGeneralizedPetersenGraph(10, 3) sage: g.is_isomorphic(g2) True

sage.graphs.generators.families.
EgawaGraph
(p, s)¶ Return the Egawa graph with parameters \(p\), \(s\).
Egawa graphs are a peculiar family of graphs devised by Yoshimi Egawa in [Ega1981] . The Shrikhande graph is a special case of this family of graphs, with parameters \((1,0)\). All the graphs in this family are not recognizable by 1WL (Weisfeiler Lehamn algorithm of the first order) and 2WL, that is their orbits are not correctly returned by kWL for k lower than 3.
Furthermore, all the graphs in this family are distanceregular, but they are not distancetransitive if \(p \neq 0\).
The Egawa graph with parameters \((0, s)\) is isomorphic to the Hamming graph with parameters \((s, 4)\), when the underlying set of the Hamming graph is \([0,1,2,3]\)
INPUT:
p
– power to which the graph named \(Y\) in the referenceprovided above will be raised
s
– power to which the graph named \(X\) in the referenceprovided above will be raised
OUTPUT:
G
– The Egawa graph with parameters (p,s)
EXAMPLES:
Every Egawa graph is distance regular.
sage: g = graphs.EgawaGraph(1, 2) sage: g.is_distance_regular() True
An Egawa graph with parameters (0,s) is isomorphic to the Hamming graph with parameters (s, 4).
sage: g = graphs.EgawaGraph(0, 4) sage: g.is_isomorphic(graphs.HammingGraph(4,4)) True

sage.graphs.generators.families.
FibonacciTree
(n)¶ Return the graph of the Fibonacci Tree \(F_{i}\) of order \(n\).
The Fibonacci tree \(F_{i}\) is recursively defined as the tree with a root vertex and two attached child trees \(F_{i1}\) and \(F_{i2}\), where \(F_{1}\) is just one vertex and \(F_{0}\) is empty.
INPUT:
n
 the recursion depth of the Fibonacci Tree
EXAMPLES:
sage: g = graphs.FibonacciTree(3) sage: g.is_tree() True
sage: l1 = [ len(graphs.FibonacciTree(_)) + 1 for _ in range(6) ] sage: l2 = list(fibonacci_sequence(2,8)) sage: l1 == l2 True
AUTHORS:
Harald Schilly and Yann LaigleChapuy (20100325)

sage.graphs.generators.families.
FoldedCubeGraph
(n)¶ Returns the folded cube graph of order \(2^{n1}\).
The folded cube graph on \(2^{n1}\) vertices can be obtained from a cube graph on \(2^n\) vertices by merging together opposed vertices. Alternatively, it can be obtained from a cube graph on \(2^{n1}\) vertices by adding an edge between opposed vertices. This second construction is the one produced by this method.
See the Wikipedia article Folded_cube_graph for more information.
EXAMPLES:
The folded cube graph of order five is the Clebsch graph:
sage: fc = graphs.FoldedCubeGraph(5) sage: clebsch = graphs.ClebschGraph() sage: fc.is_isomorphic(clebsch) True

sage.graphs.generators.families.
FriendshipGraph
(n)¶ Return the friendship graph \(F_n\).
The friendship graph is also known as the Dutch windmill graph. Let \(C_3\) be the cycle graph on 3 vertices. Then \(F_n\) is constructed by joining \(n \geq 1\) copies of \(C_3\) at a common vertex. If \(n = 1\), then \(F_1\) is isomorphic to \(C_3\) (the triangle graph). If \(n = 2\), then \(F_2\) is the butterfly graph, otherwise known as the bowtie graph. For more information, see the Wikipedia article Friendship_graph.
INPUT:
n
– positive integer; the number of copies of \(C_3\) to use in constructing \(F_n\).
OUTPUT:
The friendship graph \(F_n\) obtained from \(n\) copies of the cycle graph \(C_3\).
See also
GraphGenerators.ButterflyGraph()
EXAMPLES:
The first few friendship graphs.
sage: A = []; B = [] sage: for i in range(9): ....: g = graphs.FriendshipGraph(i + 1) ....: A.append(g) sage: for i in range(3): ....: n = [] ....: for j in range(3): ....: n.append(A[3*i + j].plot(vertex_size=20, vertex_labels=False)) ....: B.append(n) sage: G = graphics_array(B) sage: G.show() # long time
For \(n = 1\), the friendship graph \(F_1\) is isomorphic to the cycle graph \(C_3\), whose visual representation is a triangle.
sage: G = graphs.FriendshipGraph(1); G Friendship graph: Graph on 3 vertices sage: G.show() # long time sage: G.is_isomorphic(graphs.CycleGraph(3)) True
For \(n = 2\), the friendship graph \(F_2\) is isomorphic to the butterfly graph, otherwise known as the bowtie graph.
sage: G = graphs.FriendshipGraph(2); G Friendship graph: Graph on 5 vertices sage: G.is_isomorphic(graphs.ButterflyGraph()) True
If \(n \geq 1\), then the friendship graph \(F_n\) has \(2n + 1\) vertices and \(3n\) edges. It has radius 1, diameter 2, girth 3, and chromatic number 3. Furthermore, \(F_n\) is planar and Eulerian.
sage: n = randint(1, 10^3) sage: G = graphs.FriendshipGraph(n) sage: G.order() == 2*n + 1 True sage: G.size() == 3*n True sage: G.radius() 1 sage: G.diameter() 2 sage: G.girth() 3 sage: G.chromatic_number() 3 sage: G.is_planar() True sage: G.is_eulerian() True

sage.graphs.generators.families.
FurerGadget
(k, prefix=None)¶ Return a Furer gadget of order
k
and their coloring.Construct the Furer gadget described in [CFI1992], a graph composed by a middle layer of \(2^(k1)\) nodes and two sets of nodes \((a_0, ... , a_{k1})\) and \((b_0, ... , b_{k1})\). Each node in the middle is connected to either \(a_i\) or \(b_i\), for each i in [0,k[. To read about the complete construction, see [CFI1992]. The returned coloring colors the middle section with one color, and then each pair \((a_i, b_i)\) with another color. Since this method is mainly used to create Furer gadgets for the CaiFurerImmerman construction, returning gadgets that don’t always have the same vertex labels is important, that’s why there is a parameter to manually set a prefix to be appended to each vertex label.
INPUT:
k
– The order of the returned Furer gadget, greater than 0.prefix
– Prefix of to be appended to each vertex label,so as to individualise the returned Furer gadget. Must be comparable for equality and hashable.
OUTPUT:
G
– The Furer gadget of orderk
coloring
– A list of list of vertices, representing thepartition induced by the coloring of
G
’s vertices
EXAMPLES:
Furer gadget of order 3, without any prefix.
sage: G, p = graphs.FurerGadget(3) sage: sorted(G, key=str) [(), (0, 'a'), (0, 'b'), (0, 1), (0, 2), (1, 'a'), (1, 'b'), (1, 2), (2, 'a'), (2, 'b')] sage: sorted(G.edge_iterator(), key=str) [((), (0, 'b'), None), ((), (1, 'b'), None), ((), (2, 'b'), None), ((0, 'b'), (1, 2), None), ((0, 1), (0, 'a'), None), ((0, 1), (1, 'a'), None), ((0, 1), (2, 'b'), None), ((0, 2), (0, 'a'), None), ((0, 2), (1, 'b'), None), ((0, 2), (2, 'a'), None), ((1, 2), (1, 'a'), None), ((1, 2), (2, 'a'), None)]
Furer gadget of order 3, with a prefix.
sage: G, p = graphs.FurerGadget(3, 'Prefix') sage: sorted(G, key=str) [('Prefix', ()), ('Prefix', (0, 'a')), ('Prefix', (0, 'b')), ('Prefix', (0, 1)), ('Prefix', (0, 2)), ('Prefix', (1, 'a')), ('Prefix', (1, 'b')), ('Prefix', (1, 2)), ('Prefix', (2, 'a')), ('Prefix', (2, 'b'))] sage: sorted(G.edge_iterator(), key=str) [(('Prefix', ()), ('Prefix', (0, 'b')), None), (('Prefix', ()), ('Prefix', (1, 'b')), None), (('Prefix', ()), ('Prefix', (2, 'b')), None), (('Prefix', (0, 'b')), ('Prefix', (1, 2)), None), (('Prefix', (0, 1)), ('Prefix', (0, 'a')), None), (('Prefix', (0, 1)), ('Prefix', (1, 'a')), None), (('Prefix', (0, 1)), ('Prefix', (2, 'b')), None), (('Prefix', (0, 2)), ('Prefix', (0, 'a')), None), (('Prefix', (0, 2)), ('Prefix', (1, 'b')), None), (('Prefix', (0, 2)), ('Prefix', (2, 'a')), None), (('Prefix', (1, 2)), ('Prefix', (1, 'a')), None), (('Prefix', (1, 2)), ('Prefix', (2, 'a')), None)]

sage.graphs.generators.families.
FuzzyBallGraph
(partition, q)¶ Construct a Fuzzy Ball graph with the integer partition
partition
andq
extra vertices.Let \(q\) be an integer and let \(m_1,m_2,...,m_k\) be a set of positive integers. Let \(n=q+m_1+...+m_k\). The Fuzzy Ball graph with partition \(m_1,m_2,...,m_k\) and \(q\) extra vertices is the graph constructed from the graph \(G=K_n\) by attaching, for each \(i=1,2,...,k\), a new vertex \(a_i\) to \(m_i\) distinct vertices of \(G\).
For given positive integers \(k\) and \(m\) and nonnegative integer \(q\), the set of graphs
FuzzyBallGraph(p, q)
for all partitions \(p\) of \(m\) with \(k\) parts are cospectral with respect to the normalized Laplacian.EXAMPLES:
sage: F = graphs.FuzzyBallGraph([3,1],2) sage: F.adjacency_matrix(vertices=list(F)) [0 0 1 1 1 0 0 0] [0 0 0 0 0 1 0 0] [1 0 0 1 1 1 1 1] [1 0 1 0 1 1 1 1] [1 0 1 1 0 1 1 1] [0 1 1 1 1 0 1 1] [0 0 1 1 1 1 0 1] [0 0 1 1 1 1 1 0]
Pick positive integers \(m\) and \(k\) and a nonnegative integer \(q\). All the FuzzyBallGraphs constructed from partitions of \(m\) with \(k\) parts should be cospectral with respect to the normalized Laplacian:
sage: m=4; q=2; k=2 sage: g_list=[graphs.FuzzyBallGraph(p,q) for p in Partitions(m, length=k)] sage: set([g.laplacian_matrix(normalized=True, vertices=list(g)).charpoly() for g in g_list]) # long time (7s on sage.math, 2011) {x^8  8*x^7 + 4079/150*x^6  68689/1350*x^5 + 610783/10800*x^4  120877/3240*x^3 + 1351/100*x^2  931/450*x}

sage.graphs.generators.families.
GeneralizedPetersenGraph
(n, k)¶ Returns a generalized Petersen graph with \(2n\) nodes. The variables \(n\), \(k\) are integers such that \(n>2\) and \(0<k\leq\lfloor(n1)\)/\(2\rfloor\)
For \(k=1\) the result is a graph isomorphic to the circular ladder graph with the same \(n\). The regular Petersen Graph has \(n=5\) and \(k=2\). Other named graphs that can be described using this notation include the Desargues graph and the MöbiusKantor graph.
INPUT:
n
 the number of nodes is \(2*n\).k
 integer \(0<k\leq\lfloor(n1)\)/\(2\rfloor\). Decides how inner vertices are connected.
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, the generalized Petersen graphs are displayed as an inner and outer cycle pair, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outercircle, moving counterclockwise after that. The inner circle is drawn with the (n)th node at the top, then counterclockwise as well.
EXAMPLES: For \(k=1\) the resulting graph will be isomorphic to a circular ladder graph.
sage: g = graphs.GeneralizedPetersenGraph(13,1) sage: g2 = graphs.CircularLadderGraph(13) sage: g.is_isomorphic(g2) True
The Desargues graph:
sage: g = graphs.GeneralizedPetersenGraph(10,3) sage: g.girth() 6 sage: g.is_bipartite() True
AUTHORS:
Anders Jonsson (20091015)

sage.graphs.generators.families.
GoethalsSeidelGraph
(k, r)¶ Returns the graph \(\text{GoethalsSeidel}(k,r)\).
The graph \(\text{GoethalsSeidel}(k,r)\) comes from a construction presented in Theorem 2.4 of [GS1970]. It relies on a
(v,k)BIBD
with \(r\) blocks and ahadamard_matrix()
of order \(r+1\). The result is asage.graphs.strongly_regular_db.strongly_regular_graph()
on \(v(r+1)\) vertices with degree \(k=(n+r1)/2\).It appears under this name in Andries Brouwer’s database of strongly regular graphs.
INPUT:
k,r
– integers
See also
EXAMPLES:
sage: graphs.GoethalsSeidelGraph(3,3) Graph on 28 vertices sage: graphs.GoethalsSeidelGraph(3,3).is_strongly_regular(parameters=True) (28, 15, 6, 10)

sage.graphs.generators.families.
HammingGraph
(n, q, X=None)¶ Returns the Hamming graph with parameters
n
,q
overX
.Hamming graphs are graphs over the cartesian product of n copies of
X
, where \(q = X\), where the vertices, labelled with the corresponding tuple in \(X^n\), are connected if the Hamming distance between their labels is 1. All Hamming graphs are regular, vertextransitive and distanceregular.Hamming graphs with parameters \((1,q)\) represent the complete graph with q vertices over the set
X
.INPUT:
n
– power to whichX
will be raised to provide verticesfor the Hamming graph
q
– cardinality ofX
X
– list of labels representing the vertices of theunderlying graph the Hamming graph will be based on; if
None
(or left unused), the list \([0, ... , q1]\) will be used
OUTPUT:
G
– The Hamming graph with parameters \((n,q,X)\)
EXAMPLES:
Every Hamming graph is distanceregular, regular and vertextransitive.
sage: g = graphs.HammingGraph(3, 7) sage: g.is_distance_regular() True sage: g.is_regular() True sage: g.is_vertex_transitive() True
A Hamming graph with parameters (1,q) is isomorphic to the Complete graph with parameter q.
sage: g = graphs.HammingGraph(1, 23) sage: g.is_isomorphic(graphs.CompleteGraph(23)) True
If a parameter
q
is provided which is not equal toX
’s cardinality, an exception is raised.sage: X = ['a','b','c','d','e'] sage: g = graphs.HammingGraph(2, 3, X) Traceback (most recent call last): ... ValueError: q must be the cardinality of X
REFERENCES:
For a more accurate description, see the following wikipedia page: Wikipedia article Hamming_graph

sage.graphs.generators.families.
HanoiTowerGraph
(pegs, disks, labels=True, positions=True)¶ Returns the graph whose vertices are the states of the Tower of Hanoi puzzle, with edges representing legal moves between states.
INPUT:
pegs
 the number of pegs in the puzzle, 2 or greaterdisks
 the number of disks in the puzzle, 1 or greaterlabels
 default:True
, ifTrue
the graph contains more meaningful labels, see explanation below. For large instances, turn off labels for much faster creation of the graph.positions
 default:True
, ifTrue
the graph contains layout information. This creates a planar layout for the case of three pegs. For large instances, turn off layout information for much faster creation of the graph.
OUTPUT:
The Tower of Hanoi puzzle has a certain number of identical pegs and a certain number of disks, each of a different radius. Initially the disks are all on a single peg, arranged in order of their radii, with the largest on the bottom.
The goal of the puzzle is to move the disks to any other peg, arranged in the same order. The one constraint is that the disks resident on any one peg must always be arranged with larger radii lower down.
The vertices of this graph represent all the possible states of this puzzle. Each state of the puzzle is a tuple with length equal to the number of disks, ordered by largest disk first. The entry of the tuple is the peg where that disk resides. Since disks on a given peg must go down in size as we go up the peg, this totally describes the state of the puzzle.
For example
(2,0,0)
means the large disk is on peg 2, the medium disk is on peg 0, and the small disk is on peg 0 (and we know the small disk must be above the medium disk). We encode these tuples as integers with a base equal to the number of pegs, and loworder digits to the right.Two vertices are adjacent if we can change the puzzle from one state to the other by moving a single disk. For example,
(2,0,0)
is adjacent to(2,0,1)
since we can move the small disk off peg 0 and onto (the empty) peg 1. So the solution to a 3disk puzzle (with at least two pegs) can be expressed by the shortest path between(0,0,0)
and(1,1,1)
. For more on this representation of the graph, or its properties, see [AD2010].For greatest speed we create graphs with integer vertices, where we encode the tuples as integers with a base equal to the number of pegs, and loworder digits to the right. So for example, in a 3peg puzzle with 5 disks, the state
(1,2,0,1,1)
is encoded as \(1\ast 3^4 + 2\ast 3^3 + 0\ast 3^2 + 1\ast 3^1 + 1\ast 3^0 = 139\).For smaller graphs, the labels that are the tuples are informative, but slow down creation of the graph. Likewise computing layout information also incurs a significant speed penalty. For maximum speed, turn off labels and layout and decode the vertices explicitly as needed. The
sage.rings.integer.Integer.digits()
with thepadsto
option is a quick way to do this, though you may want to reverse the list that is output.PLOTTING:
The layout computed when
positions = True
will look especially good for the threepeg case, when the graph is known to be planar. Except for two small cases on 4 pegs, the graph is otherwise not planar, and likely there is a better way to layout the vertices.EXAMPLES:
A classic puzzle uses 3 pegs. We solve the 5 disk puzzle using integer labels and report the minimum number of moves required. Note that \(3^51\) is the state where all 5 disks are on peg 2.
sage: H = graphs.HanoiTowerGraph(3, 5, labels=False, positions=False) sage: H.distance(0, 3^51) 31
A slightly larger instance.
sage: H = graphs.HanoiTowerGraph(4, 6, labels=False, positions=False) sage: H.num_verts() 4096 sage: H.distance(0, 4^61) 17
For a small graph, labels and layout information can be useful. Here we explicitly list a solution as a list of states.
sage: H = graphs.HanoiTowerGraph(3, 3, labels=True, positions=True) sage: H.shortest_path((0,0,0), (1,1,1)) [(0, 0, 0), (0, 0, 1), (0, 2, 1), (0, 2, 2), (1, 2, 2), (1, 2, 0), (1, 1, 0), (1, 1, 1)]
Some facts about this graph with \(p\) pegs and \(d\) disks:
only automorphisms are the “obvious” ones  renumber the pegs.
chromatic number is less than or equal to \(p\)
independence number is \(p^{d1}\)
sage: H = graphs.HanoiTowerGraph(3,4,labels=False,positions=False) sage: H.automorphism_group().is_isomorphic(SymmetricGroup(3)) True sage: H.chromatic_number() 3 sage: len(H.independent_set()) == 3^(41) True
AUTHOR:
Rob Beezer, (20091226), with assistance from Su Doree

sage.graphs.generators.families.
HararyGraph
(k, n)¶ Returns the Harary graph on \(n\) vertices and connectivity \(k\), where \(2 \leq k < n\).
A \(k\)connected graph \(G\) on \(n\) vertices requires the minimum degree \(\delta(G)\geq k\), so the minimum number of edges \(G\) should have is \(\lceil kn/2\rceil\). Harary graphs achieve this lower bound, that is, Harary graphs are minimal \(k\)connected graphs on \(n\) vertices.
The construction provided uses the method CirculantGraph. For more details, see the book D. B. West, Introduction to Graph Theory, 2nd Edition, Prentice Hall, 2001, p. 150–151; or the MathWorld article on Harary graphs.
EXAMPLES:
Harary graphs \(H_{k,n}\):
sage: h = graphs.HararyGraph(5,9); h Harary graph 5, 9: Graph on 9 vertices sage: h.order() 9 sage: h.size() 23 sage: h.vertex_connectivity() 5

sage.graphs.generators.families.
HyperStarGraph
(n, k)¶ Returns the hyperstar graph HS(n,k).
The vertices of the hyperstar graph are the set of binary strings of length n which contain k 1s. Two vertices, u and v, are adjacent only if u can be obtained from v by swapping the first bit with a different symbol in another position.
INPUT:
n
k
EXAMPLES:
sage: g = graphs.HyperStarGraph(6,3) sage: g.plot() # long time Graphics object consisting of 51 graphics primitives
REFERENCES:
Lee, HyeongOk, JongSeok Kim, Eunseuk Oh, and HyeongSeok Lim. “HyperStar Graph: A New Interconnection Network Improving the Network Cost of the Hypercube.” In Proceedings of the First EurAsian Conference on Information and Communication Technology, 858865. SpringerVerlag, 2002.
AUTHORS:
Michael Yurko (20090901)

sage.graphs.generators.families.
IGraph
(n, j, k)¶ Return an Igraph with \(2n\) nodes.
The IGraph family as been proposed in [BCMS1988] as a generalization of the generalized Petersen graphs. The variables \(n\), \(j\), \(k\) are integers such that \(n > 2\) and \(0 < j, k \leq \lfloor (n  1) / 2 \rfloor\). When \(j = 1\) the resulting graph is isomorphic to the generalized Petersen graph with the same \(n\) and \(k\).
INPUT:
n
– the number of nodes is \(2 * n\)j
– integer such that \(0 < j \leq \lfloor (n1) / 2 \rfloor\) determining how outer vertices are connectedk
– integer such that \(0 < k \leq \lfloor (n1) / 2 \rfloor\) determining how inner vertices are connected
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, the Igraphs are displayed as an inner and outer cycle pair, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outercircle, moving counterclockwise after that. The inner circle is drawn with the (n)th node at the top, then counterclockwise as well.
EXAMPLES:
When \(j = 1\) the resulting graph will be isomorphic to a generalized Petersen graph:
sage: g = graphs.IGraph(7,1,2) sage: g2 = graphs.GeneralizedPetersenGraph(7,2) sage: g.is_isomorphic(g2) True
The IGraph with parameters \((n, j, k)\) is isomorphic to the IGraph with parameters \((n, k, j)\):
sage: g = graphs.IGraph(7, 2, 3) sage: h = graphs.IGraph(7, 3, 2) sage: g.is_isomorphic(h) True

sage.graphs.generators.families.
JohnsonGraph
(n, k)¶ Returns the Johnson graph with parameters \(n, k\).
Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph \(J(n,k)\) are the \(k\)element subsets of an \(n\)element set; two vertices are adjacent when they meet in a \((k1)\)element set. See the Wikipedia article Johnson_graph for more information.
EXAMPLES:
The Johnson graph is a Hamiltonian graph.
sage: g = graphs.JohnsonGraph(7, 3) sage: g.is_hamiltonian() True
Every Johnson graph is vertex transitive.
sage: g = graphs.JohnsonGraph(6, 4) sage: g.is_vertex_transitive() True
The complement of the Johnson graph \(J(n,2)\) is isomorphic to the Kneser Graph \(K(n,2)\). In particular the complement of \(J(5,2)\) is isomorphic to the Petersen graph.
sage: g = graphs.JohnsonGraph(5,2) sage: g.complement().is_isomorphic(graphs.PetersenGraph()) True

sage.graphs.generators.families.
KneserGraph
(n, k)¶ Returns the Kneser Graph with parameters \(n, k\).
The Kneser Graph with parameters \(n,k\) is the graph whose vertices are the \(k\)subsets of \([0,1,\dots,n1]\), and such that two vertices are adjacent if their corresponding sets are disjoint.
For example, the Petersen Graph can be defined as the Kneser Graph with parameters \(5,2\).
EXAMPLES:
sage: KG = graphs.KneserGraph(5,2) sage: sorted(KG.vertex_iterator(), key=str) [{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}] sage: P = graphs.PetersenGraph() sage: P.is_isomorphic(KG) True

sage.graphs.generators.families.
LCFGraph
(n, shift_list, repeats)¶ Return the cubic graph specified in LCF notation.
LCF (LederbergCoxeterFruchte) notation is a concise way of describing cubic Hamiltonian graphs. The way a graph is constructed is as follows. Since there is a Hamiltonian cycle, we first create a cycle on n nodes. The variable shift_list = [s_0, s_1, …, s_k1] describes edges to be created by the following scheme: for each i, connect vertex i to vertex (i + s_i). Then, repeats specifies the number of times to repeat this process, where on the jth repeat we connect vertex (i + j*len(shift_list)) to vertex ( i + j*len(shift_list) + s_i).
INPUT:
n
 the number of nodes.shift_list
 a list of integer shifts mod n.repeats
 the number of times to repeat the process.
EXAMPLES:
sage: G = graphs.LCFGraph(4, [2,2], 2) sage: G.is_isomorphic(graphs.TetrahedralGraph()) True
sage: G = graphs.LCFGraph(20, [10,7,4,4,7,10,4,7,7,4], 2) sage: G.is_isomorphic(graphs.DodecahedralGraph()) True
sage: G = graphs.LCFGraph(14, [5,5], 7) sage: G.is_isomorphic(graphs.HeawoodGraph()) True
The largest cubic nonplanar graph of diameter three:
sage: G = graphs.LCFGraph(20, [10,7,5,4,7,10,7,4,5,7,10,7,6,5,7,10,7,5,6,7], 1) sage: G.degree() [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] sage: G.diameter() 3 sage: G.show() # long time
PLOTTING: LCF Graphs are plotted as an ncycle with edges in the middle, as described above.
REFERENCES:
[1] Frucht, R. “A Canonical Representation of Trivalent Hamiltonian Graphs.” J. Graph Th. 1, 4560, 1976.
[2] Grunbaum, B. Convex Polytope es. New York: Wiley, pp. 362364, 1967.
[3] Lederberg, J. ‘DENDRAL64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs.’ Interim Report to the National Aeronautics and Space Administration. Grant NsG 8160. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.

sage.graphs.generators.families.
LollipopGraph
(n1, n2)¶ Returns a lollipop graph with n1+n2 nodes.
A lollipop graph is a path graph (order n2) connected to a complete graph (order n1). (A barbell graph minus one of the bells).
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, the complete graph will be drawn in the lowerleft corner with the (n1)th node at a 45 degree angle above the right horizontal center of the complete graph, leading directly into the path graph.
EXAMPLES:
Construct and show a lollipop graph Candy = 13, Stick = 4:
sage: g = graphs.LollipopGraph(13,4); g Lollipop graph: Graph on 17 vertices sage: g.show() # long time

sage.graphs.generators.families.
MathonPseudocyclicMergingGraph
(M, t)¶ Mathon’s merging of classes in a pseudocyclic 3class association scheme
Construct strongly regular graphs from p.97 of [BL1984].
INPUT:
M
– the list of matrices in a pseudocyclic 3class association scheme. The identity matrix must be the first entry.t
(integer) – the number of the graph, from 0 to 2.
See also

sage.graphs.generators.families.
MathonPseudocyclicStronglyRegularGraph
(t, G=None, L=None)¶ Return a strongly regular graph on \((4t+1)(4t1)^2\) vertices from [Mat1978].
Let \(4t1\) be a prime power, and \(4t+1\) be such that there exists a strongly regular graph \(G\) with parameters \((4t+1,2t,t1,t)\). In particular, \(4t+1\) must be a sum of two squares [Mat1978]. With this input, Mathon [Mat1978] gives a construction of a strongly regular graph with parameters \((4 \mu + 1, 2 \mu, \mu1, \mu)\), where \(\mu = t(4t(4t1)1)\). The construction is optionally parametrised by an a skewsymmetric Latin square of order \(4t+1\), with entries in \(2t,...,1,0,1,...,2t\).
Our implementation follows a description given in [ST1981].
INPUT:
t
– a positive integerG
– ifNone
(default), try to construct the necessary graph with parameters \((4t+1,2t,t1,t)\), otherwise use the usersupplied one, with vertices labelled from \(0\) to \(4t\).L
– ifNone
(default), construct a necessary skew Latin square, otherwise use the usersupplied one. Here nonisomorphic Latin squares – one constructed from \(Z/9Z\), and the other from \((Z/3Z)^2\) – lead to nonisomorphic graphs.
See also
EXAMPLES:
Using default
G
andL
.sage: from sage.graphs.generators.families import MathonPseudocyclicStronglyRegularGraph sage: G=MathonPseudocyclicStronglyRegularGraph(1); G Mathon's PC SRG on 45 vertices: Graph on 45 vertices sage: G.is_strongly_regular(parameters=True) (45, 22, 10, 11)
Supplying
G
andL
(constructed from the automorphism group ofG
).sage: G = graphs.PaleyGraph(9) sage: a = G.automorphism_group(partition=[sorted(G)]) sage: it = (x for x in a.normal_subgroups() if x.order() == 9) sage: subg = next(iter(it)) sage: r = [matrix(libgap.PermutationMat(libgap(z), 9).sage()) ....: for z in subg] sage: ff = list(map(lambda y: (y[0]1,y[1]1), ....: Permutation(map(lambda x: 1+r.index(x^1), r)).cycle_tuples()[1:])) sage: L = sum(i*(r[a]r[b]) for i,(a,b) in zip(range(1,len(ff)+1), ff)); L [ 0 1 1 3 2 4 3 4 2] [1 0 1 4 3 2 2 3 4] [ 1 1 0 2 4 3 4 2 3] [ 3 4 2 0 1 1 3 2 4] [ 2 3 4 1 0 1 4 3 2] [ 4 2 3 1 1 0 2 4 3] [3 2 4 3 4 2 0 1 1] [4 3 2 2 3 4 1 0 1] [2 4 3 4 2 3 1 1 0] sage: G.relabel(range(9)) sage: G3x3=graphs.MathonPseudocyclicStronglyRegularGraph(2,G=G,L=L) sage: G3x3.is_strongly_regular(parameters=True) (441, 220, 109, 110) sage: G3x3.automorphism_group(algorithm="bliss").order() # optional  bliss 27 sage: G9=graphs.MathonPseudocyclicStronglyRegularGraph(2) sage: G9.is_strongly_regular(parameters=True) (441, 220, 109, 110) sage: G9.automorphism_group(algorithm="bliss").order() # optional  bliss 9

sage.graphs.generators.families.
MuzychukS6Graph
(n, d, Phi='fixed', Sigma='fixed', verbose=False)¶ Return a strongly regular graph of S6 type from [Muz2007] on \(n^d((n^d1)/(n1)+1)\) vertices.
The construction depends upon a number of parameters, two of them, \(n\) and \(d\), mandatory, and \(\Phi\) and \(\Sigma\) mappings defined in [Muz2007]. These graphs have parameters \((mn^d, n^{d1}(m1)  1,\mu  2,\mu)\), where \(\mu=\frac{n^{d1}1}{n1}n^{d1}\) and \(m:=\frac{n^d1}{n1}+1\).
Some details on \(\Phi\) and \(\Sigma\) are as follows. Let \(L\) be the complete graph on \(M:=\{0,..., m1\}\) with the matching \(\{(2i,2i+1)  i=0,...,m/2\}\) removed. Then one arbitrarily chooses injections \(\Phi_i\) from the edges of \(L\) on \(i \in M\) into sets of parallel classes of affine \(d\)dimensional designs; our implementation uses the designs of hyperplanes in \(d\)dimensional affine geometries over \(GF(n)\). Finally, for each edge \(ij\) of \(L\) one arbitrarily chooses bijections \(\Sigma_{ij}\) between \(\Phi_i\) and \(\Phi_j\). More details, in particular how these choices lead to nonisomorphic graphs, are in [Muz2007].
INPUT:
n
(integer)– a prime powerd
(integer)– must be odd if \(n\) is oddPhi
is an optional parameter of the construction; it must be either‘fixed’– this will generate fixed default \(\Phi_i\), for \(i \in M\), or
‘random’– \(\Phi_i\) are generated at random, or
A dictionary describing the functions \(\Phi_i\); for \(i \in M\), Phi[(i, T)] in \(M\), for each edge T of \(L\) on \(i\). Also, each \(\Phi_i\) must be injective.
Sigma
is an optional parameter of the construction; it must be either‘fixed’– this will generate a fixed default \(\Sigma\), or
‘random’– \(\Sigma\) is generated at random.
verbose
(Boolean)– default is False. If True, print progress information
See also
Todo
Implement the possibility to explicitly supply the parameter \(\Sigma\) of the construction.
EXAMPLES:
sage: graphs.MuzychukS6Graph(3, 3).is_strongly_regular(parameters=True) (378, 116, 34, 36) sage: phi={(2,(0,2)):0,(1,(1,3)):1,(0,(0,3)):1,(2,(1,2)):1,(1,(1, ....: 2)):0,(0,(0,2)):0,(3,(0,3)):0,(3,(1,3)):1} sage: graphs.MuzychukS6Graph(2,2,Phi=phi).is_strongly_regular(parameters=True) (16, 5, 0, 2)

sage.graphs.generators.families.
MycielskiGraph
(k=1, relabel=True)¶ Returns the \(k\)th Mycielski Graph.
The graph \(M_k\) is trianglefree and has chromatic number equal to \(k\). These graphs show, constructively, that there are trianglefree graphs with arbitrarily high chromatic number.
The Mycielski graphs are built recursively starting with \(M_0\), an empty graph; \(M_1\), a single vertex graph; and \(M_2\) is the graph \(K_2\). \(M_{k+1}\) is then built from \(M_k\) as follows:
If the vertices of \(M_k\) are \(v_1,\ldots,v_n\), then the vertices of \(M_{k+1}\) are \(v_1,\ldots,v_n,w_1,\ldots,w_n,z\). Vertices \(v_1,\ldots,v_n\) induce a copy of \(M_k\). Vertices \(w_1,\ldots,w_n\) are an independent set. Vertex \(z\) is adjacent to all the \(w_i\)vertices. Finally, vertex \(w_i\) is adjacent to vertex \(v_j\) iff \(v_i\) is adjacent to \(v_j\).
INPUT:
k
Number of steps in the construction process.relabel
Relabel the vertices so their names are the integersrange(n)
wheren
is the number of vertices in the graph.
EXAMPLES:
The Mycielski graph \(M_k\) is trianglefree and has chromatic number equal to \(k\).
sage: g = graphs.MycielskiGraph(5) sage: g.is_triangle_free() True sage: g.chromatic_number() 5
The graphs \(M_4\) is (isomorphic to) the Grotzsch graph.
sage: g = graphs.MycielskiGraph(4) sage: g.is_isomorphic(graphs.GrotzschGraph()) True
REFERENCES:
[1] Weisstein, Eric W. “Mycielski Graph.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/MycielskiGraph.html

sage.graphs.generators.families.
MycielskiStep
(g)¶ Perform one iteration of the Mycielski construction.
See the documentation for
MycielskiGraph
which uses this method. We expose it to all users in case they may find it useful.EXAMPLE. One iteration of the Mycielski step applied to the 5cycle yields a graph isomorphic to the Grotzsch graph
sage: g = graphs.CycleGraph(5) sage: h = graphs.MycielskiStep(g) sage: h.is_isomorphic(graphs.GrotzschGraph()) True

sage.graphs.generators.families.
NKStarGraph
(n, k)¶ Returns the (n,k)star graph.
The vertices of the (n,k)star graph are the set of all arrangements of n symbols into labels of length k. There are two adjacency rules for the (n,k)star graph. First, two vertices are adjacent if one can be obtained from the other by swapping the first symbol with another symbol. Second, two vertices are adjacent if one can be obtained from the other by swapping the first symbol with an external symbol (a symbol not used in the original label).
INPUT:
n
k
EXAMPLES:
sage: g = graphs.NKStarGraph(4,2) sage: g.plot() # long time Graphics object consisting of 31 graphics primitives
REFERENCES:
WeiKuo, Chiang, and Chen RongJaye. “The (n, k)star graph: A generalized star graph.” Information Processing Letters 56, no. 5 (December 8, 1995): 259264.
AUTHORS:
Michael Yurko (20090901)

sage.graphs.generators.families.
NStarGraph
(n)¶ Returns the nstar graph.
The vertices of the nstar graph are the set of permutations on n symbols. There is an edge between two vertices if their labels differ only in the first and one other position.
INPUT:
n
EXAMPLES:
sage: g = graphs.NStarGraph(4) sage: g.plot() # long time Graphics object consisting of 61 graphics primitives
REFERENCES:
S.B. Akers, D. Horel and B. Krishnamurthy, The star graph: An attractive alternative to the previous ncube. In: Proc. Internat. Conf. on Parallel Processing (1987), pp. 393–400.
AUTHORS:
Michael Yurko (20090901)

sage.graphs.generators.families.
OddGraph
(n)¶ Returns the Odd Graph with parameter \(n\).
The Odd Graph with parameter \(n\) is defined as the Kneser Graph with parameters \(2n1,n1\). Equivalently, the Odd Graph is the graph whose vertices are the \(n1\)subsets of \([0,1,\dots,2(n1)]\), and such that two vertices are adjacent if their corresponding sets are disjoint.
For example, the Petersen Graph can be defined as the Odd Graph with parameter \(3\).
EXAMPLES:
sage: OG = graphs.OddGraph(3) sage: sorted(OG.vertex_iterator(), key=str) [{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}] sage: P = graphs.PetersenGraph() sage: P.is_isomorphic(OG) True

sage.graphs.generators.families.
PaleyGraph
(q)¶ Paley graph with \(q\) vertices
Parameter \(q\) must be the power of a prime number and congruent to 1 mod 4.
EXAMPLES:
sage: G = graphs.PaleyGraph(9); G Paley graph with parameter 9: Graph on 9 vertices sage: G.is_regular() True
A Paley graph is always selfcomplementary:
sage: G.is_self_complementary() True

sage.graphs.generators.families.
PasechnikGraph
(n)¶ Pasechnik strongly regular graph on \((4n1)^2\) vertices
A strongly regular graph with parameters of the orthogonal array graph
OrthogonalArrayBlockGraph()
, also known as pseudo Latin squares graph \(L_{2n1}(4n1)\), constructed from a skew Hadamard matrix of order \(4n\) following [Pas1992].See also
EXAMPLES:
sage: graphs.PasechnikGraph(4).is_strongly_regular(parameters=True) (225, 98, 43, 42) sage: graphs.PasechnikGraph(5).is_strongly_regular(parameters=True) # long time (361, 162, 73, 72) sage: graphs.PasechnikGraph(9).is_strongly_regular(parameters=True) # not tested (1225, 578, 273, 272)

sage.graphs.generators.families.
RingedTree
(k, vertex_labels=True)¶ Return the ringed tree on klevels.
A ringed tree of level \(k\) is a binary tree with \(k\) levels (counting the root as a level), in which all vertices at the same level are connected by a ring.
More precisely, in each layer of the binary tree (i.e. a layer is the set of vertices \([2^i...2^{i+1}1]\)) two vertices \(u,v\) are adjacent if \(u=v+1\) or if \(u=2^i\) and \(v=\).
Ringed trees are defined in [CFHM2013].
INPUT:
k
– the number of levels of the ringed tree.vertex_labels
(boolean) – whether to label vertices as binary words (default) or as integers.
EXAMPLES:
sage: G = graphs.RingedTree(5) sage: P = G.plot(vertex_labels=False, vertex_size=10) sage: P.show() # long time sage: G.vertices() ['', '0', '00', '000', '0000', '0001', '001', '0010', '0011', '01', '010', '0100', '0101', '011', '0110', '0111', '1', '10', '100', '1000', '1001', '101', '1010', '1011', '11', '110', '1100', '1101', '111', '1110', '1111']

sage.graphs.generators.families.
RoseWindowGraph
(n, a, r)¶ Return a rose window graph with \(2n\) nodes.
The rose window graphs is a family of tetravalant graphs introduced in [Wilson2008]. The parameters \(n\), \(a\) and \(r\) are integers such that \(n > 2\), \(1 \leq a, r < n\), and \(r \neq n / 2\).
INPUT:
n
– the number of nodes is \(2 * n\)a
– integer such that \(1 \leq a < n\) determing aspoke edgesr
– integer such that \(1 \leq r < n\) and \(r \neq n / 2\) determing how inner vertices are connected
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, the rose window graphs are displayed as an inner and outer cycle pair, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outercircle, moving counterclockwise after that. The inner circle is drawn with the (n)th node at the top, then counterclockwise as well. Vertices in the outer circle are connected in the circular manner, vertices in the inner circle are connected when their label have difference \(r\) (mod n). Vertices on the outer rim are connected with the vertices on the inner rim when they are at the same position and when they are \(a\) apart.
EXAMPLES:
The vertices of a rose window graph have all degree 4:
sage: G = graphs.RoseWindowGraph(5, 1, 2) sage: all(G.degree(u) == 4 for u in G) True
The smallest rose window graph as parameters \((3, 2, 1)\):
sage: G = graphs.RoseWindowGraph(3, 2, 1) sage: all(G.degree(u) == 4 for u in G) True

sage.graphs.generators.families.
SierpinskiGasketGraph
(n)¶ Return the Sierpinski Gasket graph of generation \(n\).
All vertices but 3 have valence 4.
INPUT:
\(n\) – an integer
OUTPUT:
a graph \(S_n\) with \(3 (3^{n1}+1)/2\) vertices and \(3^n\) edges, closely related to the famous Sierpinski triangle fractal.
All these graphs have a triangular shape, and three special vertices at top, bottom left and bottom right. These are the only vertices of valence 2, all the other ones having valence 4.
The graph \(S_1\) (generation \(1\)) is a triangle.
The graph \(S_{n+1}\) is obtained from the disjoint union of three copies A,B,C of \(S_n\) by identifying pairs of vertices: the top vertex of A with the bottom left vertex of B, the bottom right vertex of B with the top vertex of C, and the bottom left vertex of C with the bottom right vertex of A.
See also
There is another family of graphs called Sierpinski graphs, where all vertices but 3 have valence 3. They are available using
graphs.HanoiTowerGraph(3, n)
.EXAMPLES:
sage: s4 = graphs.SierpinskiGasketGraph(4); s4 Graph on 42 vertices sage: s4.size() 81 sage: s4.degree_histogram() [0, 0, 3, 0, 39] sage: s4.is_hamiltonian() True
REFERENCES:

sage.graphs.generators.families.
SquaredSkewHadamardMatrixGraph
(n)¶ Pseudo\(OA(2n,4n1)\)graph from a skew Hadamard matrix of order \(4n\)
A strongly regular graph with parameters of the orthogonal array graph
OrthogonalArrayBlockGraph()
, also known as pseudo Latin squares graph \(L_{2n}(4n1)\), constructed from a skew Hadamard matrix of order \(4n\), due to Goethals and Seidel, see [BL1984].See also
EXAMPLES:
sage: graphs.SquaredSkewHadamardMatrixGraph(4).is_strongly_regular(parameters=True) (225, 112, 55, 56) sage: graphs.SquaredSkewHadamardMatrixGraph(5).is_strongly_regular(parameters=True) # long time (361, 180, 89, 90) sage: graphs.SquaredSkewHadamardMatrixGraph(9).is_strongly_regular(parameters=True) # not tested (1225, 612, 305, 306)

sage.graphs.generators.families.
SwitchedSquaredSkewHadamardMatrixGraph
(n)¶ A strongly regular graph in Seidel switching class of \(SquaredSkewHadamardMatrixGraph\)
A strongly regular graph in the
Seidel switching
class of the disjoint union of a 1vertex graph and the one produced byPseudoL_{2n}(4n1)
In this case, the other possible parameter set of a strongly regular graph in the Seidel switching class of the latter graph (see [BH2012]) coincides with the set of parameters of the complement of the graph returned by this function.
See also
EXAMPLES:
sage: g=graphs.SwitchedSquaredSkewHadamardMatrixGraph(4) sage: g.is_strongly_regular(parameters=True) (226, 105, 48, 49) sage: from sage.combinat.designs.twographs import twograph_descendant sage: twograph_descendant(g,0).is_strongly_regular(parameters=True) (225, 112, 55, 56) sage: twograph_descendant(g.complement(),0).is_strongly_regular(parameters=True) (225, 112, 55, 56)

sage.graphs.generators.families.
TabacjnGraph
(n, a, b, r)¶ Return a Tabačjn graph with \(2n\) nodes.
The Tabačjn graphs is a family of pentavalent bicirculants graphs proposed in [AHKOS2014] as a generalization of generalized Petersen graphs. The parameters \(n\), \(a\), \(b\), \(r\) are integers such that \(n \geq 3\), \(1 \leq a, b, r \leq n  1\), with \(a \neq b\) and \(r \neq n / 2\).
INPUT:
n
– the number of nodes is \(2 * n\)a
– integer such that \(0 < a < n\) and \(a \neq b\), that determines aspoke edgesb
– integer such that \(0 < b < n\) and \(b \neq a\), that determines bspoke edgesr
– integer such that \(0 < r < n\) and \(r \neq n/2\) determining how inner vertices are connected
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, the rose window graphs are displayed as an inner and outer cycle pair, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outercircle, moving counterclockwise after that. The inner circle is drawn with the (n)th node at the top, then counterclockwise as well. Vertices in the outer circle are connected in the circular manner, vertices in the inner circle are connected when their label have difference \(r\) (mod n). Vertices on the outer rim are connected with the vertices on the inner rim when they are at the same position and when they are \(a\) and \(b\) apart.
EXAMPLES:
sage: G = graphs.TabacjnGraph(3, 1, 2, 1) sage: G.degree() [5, 5, 5, 5, 5, 5] sage: G.is_isomorphic(graphs.CompleteGraph(6)) True sage: G = graphs.TabacjnGraph(6, 1, 5, 2) sage: I = graphs.IcosahedralGraph() sage: G.is_isomorphic(I) True

sage.graphs.generators.families.
TadpoleGraph
(n1, n2)¶ Return a tadpole graph with n1+n2 nodes.
A tadpole graph is a path graph (order n2) connected to a cycle graph (order n1).
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, the cycle graph will be drawn in the lowerleft corner with the (n1)th node at a 45 degree angle above the right horizontal center of the cycle graph, leading directly into the path graph.
EXAMPLES:
Construct and show a tadpole graph Cycle = 13, Stick = 4:
sage: g = graphs.TadpoleGraph(13, 4); g Tadpole graph: Graph on 17 vertices sage: g.show() # long time

sage.graphs.generators.families.
TuranGraph
(n, r)¶ Returns the Turan graph with parameters \(n, r\).
Turan graphs are complete multipartite graphs with \(n\) vertices and \(r\) subsets, denoted \(T(n,r)\), with the property that the sizes of the subsets are as close to equal as possible. The graph \(T(n,r)\) will have \(n \pmod r\) subsets of size \(\lfloor n/r \rfloor\) and \(r  (n \pmod r)\) subsets of size \(\lceil n/r \rceil\). See the Wikipedia article Turan_graph for more information.
INPUT:
n
(integer)– the number of vertices in the graph.r
(integer) – the number of partitions of the graph.
EXAMPLES:
The Turan graph is a complete multipartite graph.
sage: g = graphs.TuranGraph(13, 4) sage: k = graphs.CompleteMultipartiteGraph([3,3,3,4]) sage: g.is_isomorphic(k) True
The Turan graph \(T(n,r)\) has \(\lfloor \frac{(r1)(n^2)}{2r} \rfloor\) edges.
sage: n = 13 sage: r = 4 sage: g = graphs.TuranGraph(n,r) sage: g.size() == floor((r1)*(n**2)/(2*r)) True

sage.graphs.generators.families.
WheelGraph
(n)¶ Returns a Wheel graph with n nodes.
A Wheel graph is a basic structure where one node is connected to all other nodes and those (outer) nodes are connected cyclically.
PLOTTING: Upon construction, the position dictionary is filled to override the springlayout algorithm. By convention, each wheel graph will be displayed with the first (0) node in the center, the second node at the top, and the rest following in a counterclockwise manner.
With the wheel graph, we see that it doesn’t take a very large n at all for the springlayout to give a counterintuitive display. (See Graphics Array examples below).
EXAMPLES:
We view many wheel graphs with a Sage Graphics Array, first with this constructor (i.e., the position dictionary filled):
sage: g = [] sage: j = [] sage: for i in range(9): ....: k = graphs.WheelGraph(i+3) ....: g.append(k) ... sage: for i in range(3): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) ... sage: G = graphics_array(j) sage: G.show() # long time
Next, using the springlayout algorithm:
sage: import networkx sage: g = [] sage: j = [] sage: for i in range(9): ....: spr = networkx.wheel_graph(i+3) ....: k = Graph(spr) ....: g.append(k) ... sage: for i in range(3): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) ... sage: G = graphics_array(j) sage: G.show() # long time
Compare the plotting:
sage: n = networkx.wheel_graph(23) sage: spring23 = Graph(n) sage: posdict23 = graphs.WheelGraph(23) sage: spring23.show() # long time sage: posdict23.show() # long time

sage.graphs.generators.families.
WindmillGraph
(k, n)¶ Return the Windmill graph \(Wd(k, n)\).
The windmill graph \(Wd(k, n)\) is an undirected graph constructed for \(k \geq 2\) and \(n \geq 2\) by joining \(n\) copies of the complete graph \(K_k\) at a shared vertex. It has \((k1)n+1\) vertices and \(nk(k1)/2\) edges, girth 3 (if \(k > 2\)), radius 1 and diameter 2. It has vertex connectivity 1 because its central vertex is an articulation point; however, like the complete graphs from which it is formed, it is \((k1)\)edgeconnected. It is trivially perfect and a block graph.
See also
GraphGenerators.StarGraph()
GraphGenerators.FriendshipGraph()
EXAMPLES:
The Windmill graph \(Wd(2, n)\) is a star graph:
sage: n = 5 sage: W = graphs.WindmillGraph(2, n) sage: W.is_isomorphic( graphs.StarGraph(n) ) True
The Windmill graph \(Wd(3, n)\) is the Friendship graph \(F_n\):
sage: n = 5 sage: W = graphs.WindmillGraph(3, n) sage: W.is_isomorphic( graphs.FriendshipGraph(n) ) True
The Windmill graph \(Wd(3, 2)\) is the Butterfly graph:
sage: W = graphs.WindmillGraph(3, 2) sage: W.is_isomorphic( graphs.ButterflyGraph() ) True
The Windmill graph \(Wd(k, n)\) has chromatic number \(k\):
sage: n,k = 5,6 sage: W = graphs.WindmillGraph(k, n) sage: W.chromatic_number() == k True

sage.graphs.generators.families.
chang_graphs
()¶ Return the three Chang graphs.
Three of the four strongly regular graphs of parameters \((28,12,6,4)\) are called the Chang graphs. The fourth is the line graph of \(K_8\). For more information about the Chang graphs, see the Wikipedia article Chang_graphs or https://www.win.tue.nl/~aeb/graphs/Chang.html.
EXAMPLES: check that we get 4 nonisomorphic s.r.g.’s with the same parameters:
sage: chang_graphs = graphs.chang_graphs() sage: K8 = graphs.CompleteGraph(8) sage: T8 = K8.line_graph() sage: four_srg = chang_graphs + [T8] sage: for g in four_srg: ....: print(g.is_strongly_regular(parameters=True)) (28, 12, 6, 4) (28, 12, 6, 4) (28, 12, 6, 4) (28, 12, 6, 4) sage: from itertools import combinations sage: for g1,g2 in combinations(four_srg,2): ....: assert not g1.is_isomorphic(g2)
Construct the Chang graphs by Seidel switching:
sage: c3c5=graphs.CycleGraph(3).disjoint_union(graphs.CycleGraph(5)) sage: c8=graphs.CycleGraph(8) sage: s=[K8.subgraph_search(c8).edges(), ....: [(0,1,None),(2,3,None),(4,5,None),(6,7,None)], ....: K8.subgraph_search(c3c5).edges()] sage: list(map(lambda x,G: T8.seidel_switching(x, inplace=False).is_isomorphic(G), ....: s, chang_graphs)) [True, True, True]

sage.graphs.generators.families.
line_graph_forbidden_subgraphs
()¶ Returns the 9 forbidden subgraphs of a line graph.
See the Wikipedia article Line_graph for more information.
The graphs are returned in the ordering given by the Wikipedia drawing, read from left to right and from top to bottom.
EXAMPLES:
sage: graphs.line_graph_forbidden_subgraphs() [Claw graph: Graph on 4 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 5 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 6 vertices, Graph on 5 vertices]

sage.graphs.generators.families.
petersen_family
(generate=False)¶ Returns the Petersen family
The Petersen family is a collection of 7 graphs which are the forbidden minors of the linklessly embeddable graphs. For more information see the Wikipedia article Petersen_family.
INPUT:
generate
(boolean) – whether to generate the family from the \(\DeltaY\) transformations. When set toFalse
(default) a hardcoded version of the graphs (with a prettier layout) is returned.
EXAMPLES:
sage: graphs.petersen_family() [Petersen graph: Graph on 10 vertices, Complete graph: Graph on 6 vertices, Multipartite Graph with set sizes [3, 3, 1]: Graph on 7 vertices, Graph on 8 vertices, Graph on 9 vertices, Graph on 7 vertices, Graph on 8 vertices]
The two different inputs generate the same graphs:
sage: F1 = graphs.petersen_family(generate=False) sage: F2 = graphs.petersen_family(generate=True) sage: F1 = [g.canonical_label().graph6_string() for g in F1] sage: F2 = [g.canonical_label().graph6_string() for g in F2] sage: set(F1) == set(F2) True

sage.graphs.generators.families.
trees
(vertices)¶ Returns a generator of the distinct trees on a fixed number of vertices.
INPUT:
vertices
 the size of the trees created.
OUTPUT:
A generator which creates an exhaustive, duplicatefree listing of the connected free (unlabeled) trees with
vertices
number of vertices. A tree is a graph with no cycles.ALGORITHM:
Uses an algorithm that generates each new tree in constant time. See the documentation for, and implementation of, the
sage.graphs.trees
module, including a citation.EXAMPLES:
We create an iterator, then loop over its elements.
sage: tree_iterator = graphs.trees(7) sage: for T in tree_iterator: ....: print(T.degree_sequence()) [2, 2, 2, 2, 2, 1, 1] [3, 2, 2, 2, 1, 1, 1] [3, 2, 2, 2, 1, 1, 1] [4, 2, 2, 1, 1, 1, 1] [3, 3, 2, 1, 1, 1, 1] [3, 3, 2, 1, 1, 1, 1] [4, 3, 1, 1, 1, 1, 1] [3, 2, 2, 2, 1, 1, 1] [4, 2, 2, 1, 1, 1, 1] [5, 2, 1, 1, 1, 1, 1] [6, 1, 1, 1, 1, 1, 1]
The number of trees on the first few vertex counts. This is sequence A000055 in Sloane’s OEIS.
sage: [len(list(graphs.trees(i))) for i in range(0, 15)] [1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159]