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                                          # needs networkx
Balanced tree: Graph on 3 vertices
sage: G.order(); G.size()                                                       # needs networkx
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)                                             # needs networkx
sage: G.show()                          # long time                             # needs networkx sage.plot

A tree is bipartite. If its vertex set is finite, then it is planar.

sage: # needs networkx
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 argument n1 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 order n1 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. A ValueError is returned if n1 < 2 or n2 < 0.

PLOTTING:

Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each barbell graph will be displayed with the two complete graphs in the lower-left and upper-right 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 the n1 + 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                             # needs sage.plot

An n1 >= 2, n2 >= 0 barbell graph has order 2*n1 + n2. It has the complete graph on n1 vertices as a subgraph. It also has the path graph on n2 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: # needs sage.modules
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 n-1\). 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                             # needs sage.plot
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 (2009-09-01)

sage.graphs.generators.families.CaiFurerImmermanGraph(G, twisted=False)#

Return the a Cai-Furer-Immerman graph from \(G\), possibly a twisted one, and a partition of its nodes.

A Cai-Furer-Immerman 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 k-WL for any k < s.

INPUT:

  • G – An undirected graph on which to construct the

    Cai-Furer-Immerman graph

  • twisted – A boolean indicating if the version to construct

    is a twisted one or not

OUTPUT:

  • H – The Cai-Furer-Immerman graph on G

  • coloring – A list of list of vertices, representing the

    partition 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 \(i-j\) for each j in adjacency.

INPUT:

  • n - number of vertices in the graph

  • adjacency - the list of j values

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout 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

EXAMPLES: Compare plotting using the predefined layout and networkx:

sage: # needs 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: # needs sage.plot
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 spring-layout algorithm:

sage: # needs networkx sage.plot
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(sort=True, 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 cube-connected cycle of dimension \(d\).

The cube-connected 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, (y-1) \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 cube-connected cycle graph contains self-loops 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 cube-connected 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//2-2
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, embedding=1)#

Return the \(n\)-cube graph, also called 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.

INPUT:

  • n – integer; the dimension of the cube graph

  • embedding – integer (default: 1); two embeddings of the \(n\)-cube are available:

    • 1: the \(n\)-cube is projected inside a regular \(2n\)-gonal polygon by a skew orthogonal projection. See the Wikipedia article Hypercube for more details.

    • 2: orthogonal projection of the \(n\)-cube. This orientation shows columns of independent vertices such that the neighbors of a vertex are located in the columns on the left and on the right. The number of vertices in each column represents rows in Pascal’s triangle. See for instance the Wikipedia article 10-cube for more details.

    • 3: oblique projection of the \(n\)-cube. Oblique projection involves aligning one face parallel to the viewer and projecting at a specified angle, maintaining equal size for edges parallel to one axis while applying fixed foreshortening to others. This method simplifies the representation of a four-dimensional hypercube onto a two-dimensional plane, offering a geometrically consistent visualization.

    • None or O: no embedding is provided

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: # needs sage.plot
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, embedding=1)
sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20)       # long time, needs sage.plot
sage: g = graphs.CubeGraph(9, embedding=2)
sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20)       # long time, needs sage.plot
sage: g = graphs.CubeGraph(9, embedding=3)
sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20)       # long time, needs sage.plot

AUTHORS:

  • Robert Miller

  • David Coudert

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: Multi-graph on 2 vertices
sage: g.show()                          # long time                             # needs sage.plot
sage.graphs.generators.families.DorogovtsevGoltsevMendesGraph(n)#

Construct the n-th generation of the Dorogovtsev-Goltsev-Mendes graph.

EXAMPLES:

sage: G = graphs.DorogovtsevGoltsevMendesGraph(8)                               # needs networkx
sage: G.size()                                                                  # needs networkx
6561

REFERENCE:

  • [1] Dorogovtsev, S. N., Goltsev, A. V., and Mendes, J. F. F., Pseudofractal scale-free 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 (n-1) / 2 \rfloor\).

INPUT:

  • n – the number of nodes is \(4 * n\)

  • k – integer such that \(0 < k \leq \lfloor (n-1) / 2 \rfloor\) determining how vertices on second and third inner rims are connected

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout 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 outer-circle, 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 1-WL (Weisfeiler Lehamn algorithm of the first order) and 2-WL, that is their orbits are not correctly returned by k-WL for k lower than 3.

Furthermore, all the graphs in this family are distance-regular, but they are not distance-transitive 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 reference

    provided above will be raised

  • s – power to which the graph named \(X\) in the reference

    provided 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_{i-1}\) and \(F_{i-2}\), 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)                                               # needs sage.libs.pari
sage: g.is_tree()                                                               # needs sage.libs.pari
True

sage: l1 = [ len(graphs.FibonacciTree(_)) + 1 for _ in range(6) ]               # needs sage.libs.pari
sage: l2 = list(fibonacci_sequence(2,8))                                        # needs sage.libs.pari
sage: l1 == l2                                                                  # needs sage.libs.pari
True

AUTHORS:

  • Harald Schilly and Yann Laigle-Chapuy (2010-03-25)

sage.graphs.generators.families.FoldedCubeGraph(n)#

Returns the folded cube graph of order \(2^{n-1}\).

The folded cube graph on \(2^{n-1}\) 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^{n-1}\) 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: # needs sage.plot
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                             # needs sage.plot
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 2\), 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(2, 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^(k-1)\) nodes and two sets of nodes \((a_0, ... , a_{k-1})\) and \((b_0, ... , b_{k-1})\). 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 Cai-Furer-Immerman 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 order k

  • coloring – A list of list of vertices, representing the

    partition 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 and q 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))                                      # needs sage.modules
[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)                                      # needs sage.combinat sage.modules
....:           for p in Partitions(m, length=k)]
sage: set(g.laplacian_matrix(normalized=True,   # long time (7s on sage.math, 2011), needs sage.combinat sage.modules
....:                        vertices=list(g)).charpoly()
....:     for g in g_list)
{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(n-1)\)/\(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öbius-Kantor graph.

INPUT:

  • n - the number of nodes is \(2*n\).

  • k - integer \(0<k\leq\lfloor(n-1)\)/\(2\rfloor\). Decides how inner vertices are connected.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout 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 outer-circle, 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 (2009-10-15)

sage.graphs.generators.families.GeneralizedSierpinskiGraph(G, k, stretch=None)#

Return the generalized Sierpinski graph of \(G\) of dimension \(k\).

Generalized Sierpinski graphs have been introduced in [GKP2011] to generalize the notion of Sierpinski graphs [KM1997].

Given a graph \(G = (V, E)\) of order \(n\) and a parameter \(k\), the generalized Sierpinski graph of \(G\) of dimension \(k\), denoted by \(S(G, k)\), can be constructed recursively from \(G\) as follows. \(S(G, 1)\) is isomorphic to \(G\). To construct \(S(G, k)\) for \(k > 1\), copy \(n\) times \(S(G, k - 1)\), once per vertex \(u \in V\), and add \(u\) at the beginning of the labels of each vertex in the copy of \(S(G, k - 1)\) corresponding to vertex \(u\). Then for any edge \(\{u, v\} \in E\), add an edge between vertex \((u, v, \ldots, v)\) and vertex \((v, u, \ldots, u)\).

INPUT:

  • G – a sage Graph

  • k – integer; the dimension

  • stretch – integer (default: None); stretching factor used to determine the positions of the vertices of the output graph. By default (None), this value is set to twice the maximum Euclidean distance between the vertices of \(G\). This parameter is used only when the vertices of \(G\) have positions.

See also

EXAMPLES:

The generalized Sierpinski graph of dimension 1 of any graph \(G\) is isomorphic to \(G\):

sage: G = graphs.RandomGNP(10, .5)
sage: S = graphs.GeneralizedSierpinskiGraph(G, 1)
sage: S.is_isomorphic(G)
True

When \(G\) is a clique of order 3, the generalized Sierpinski graphs of \(G\) are isomorphic to Hanoi Tower graphs:

sage: k = randint(1, 5)
sage: S = graphs.GeneralizedSierpinskiGraph(graphs.CompleteGraph(3), k)         # needs sage.modules
sage: H = graphs.HanoiTowerGraph(3, k)
sage: S.is_isomorphic(H)                                                        # needs sage.modules
True

The generalized Sierpinski graph of dimension \(k\) of any graph \(G\) with \(n\) vertices and \(m\) edges has \(n^k\) vertices and \(m\sum_{i=0}^{k-1}n^i\) edges:

sage: # needs sage.modules
sage: n = randint(2, 6)
sage: k = randint(1, 5)
sage: G = graphs.RandomGNP(n, .5)
sage: m = G.size()
sage: S = graphs.GeneralizedSierpinskiGraph(G, k)
sage: S.order() == n**k
True
sage: S.size() == m*sum([n**i for i in range(k)])
True
sage: G = graphs.CompleteGraph(n)
sage: S = graphs.GeneralizedSierpinskiGraph(G, k)
sage: S.order() == n**k
True
sage: S.size() == (n*(n - 1)/2)*sum([n**i for i in range(k)])
True

The positions of the vertices of the output graph are determined from the positions of the vertices of \(G\), if any:

sage: G = graphs.HouseGraph()
sage: G.get_pos() is not None
True
sage: H = graphs.GeneralizedSierpinskiGraph(G, 2)                               # needs sage.symbolic
sage: H.get_pos() is not None                                                   # needs sage.symbolic
True
sage: G = Graph([(0, 1)])
sage: G.get_pos() is not None
False
sage: H = graphs.GeneralizedSierpinskiGraph(G, 2)                               # needs sage.symbolic
sage: H.get_pos() is not None                                                   # needs sage.symbolic
False
../../../_images/families-1.svg
sage.graphs.generators.families.GoethalsSeidelGraph(k, r)#

Returns the graph \(\text{Goethals-Seidel}(k,r)\).

The graph \(\text{Goethals-Seidel}(k,r)\) comes from a construction presented in Theorem 2.4 of [GS1970]. It relies on a (v,k)-BIBD with \(r\) blocks and a hadamard_matrix() of order \(r+1\). The result is a sage.graphs.strongly_regular_db.strongly_regular_graph() on \(v(r+1)\) vertices with degree \(k=(n+r-1)/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)                                           # needs sage.combinat sage.modules
Graph on 28 vertices
sage: graphs.GoethalsSeidelGraph(3,3).is_strongly_regular(parameters=True)      # needs sage.combinat sage.modules
(28, 15, 6, 10)
sage.graphs.generators.families.HammingGraph(n, q, X=None)#

Returns the Hamming graph with parameters n, q over X.

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, vertex-transitive and distance-regular.

Hamming graphs with parameters \((1,q)\) represent the complete graph with q vertices over the set X.

INPUT:

  • n – power to which X will be raised to provide vertices

    for the Hamming graph

  • q – cardinality of X

  • X – list of labels representing the vertices of the

    underlying graph the Hamming graph will be based on; if None (or left unused), the list \([0, ... , q-1]\) will be used

OUTPUT:

  • G – The Hamming graph with parameters \((n,q,X)\)

EXAMPLES:

Every Hamming graph is distance-regular, regular and vertex-transitive.

sage: g = graphs.HammingGraph(3, 7)
sage: g.is_distance_regular()
True
sage: g.is_regular()
True
sage: g.is_vertex_transitive()                                                  # needs sage.groups
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 to X’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 greater

  • disks - the number of disks in the puzzle, 1 or greater

  • labels - default: True, if True 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, if True 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 low-order 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 3-disk 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 low-order digits to the right. So for example, in a 3-peg 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 the padsto option is a quick way to do this, though you may want to reverse the list that is output.

See also

PLOTTING:

The layout computed when positions = True will look especially good for the three-peg 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^5-1\) 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^5-1)
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^6-1)
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^{d-1}\)

sage: H = graphs.HanoiTowerGraph(3, 4, labels=False, positions=False)
sage: H.automorphism_group().is_isomorphic(SymmetricGroup(3))                   # needs sage.groups
True
sage: H.chromatic_number()
3
sage: len(H.independent_set()) == 3^(4-1)
True

AUTHOR:

  • Rob Beezer, (2009-12-26), 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()                                                   # needs sage.numerical.mip
5
sage.graphs.generators.families.HyperStarGraph(n, k)#

Return the hyper-star graph \(HS(n, k)\).

The vertices of the hyper-star 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. For instance, vertex '011100' of \(HS(6, 3)\) is adjacent to vertices '101100', '110100' and '111000'. See [LKOL2002] for more details.

INPUT:

  • n – non-negative integer; length of the binary strings

  • k – non-negative integer; number of 1s per binary string

EXAMPLES:

sage: g = graphs.HyperStarGraph(6,3)
sage: sorted(g.neighbors('011100'))
['101100', '110100', '111000']
sage: g.plot()                          # long time                             # needs sage.plot
Graphics object consisting of 51 graphics primitives

AUTHORS:

  • Michael Yurko (2009-09-01)

sage.graphs.generators.families.IGraph(n, j, k)#

Return an I-graph with \(2n\) nodes.

The I-Graph 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 (n-1) / 2 \rfloor\) determining how outer vertices are connected

  • k – integer such that \(0 < k \leq \lfloor (n-1) / 2 \rfloor\) determining how inner vertices are connected

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the I-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 outer-circle, 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 \((k-1)\)-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()                                                        # needs sage.numerical.mip
True

Every Johnson graph is vertex transitive:

sage: g = graphs.JohnsonGraph(6, 4)
sage: g.is_vertex_transitive()                                                  # needs sage.groups
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,n-1]\), 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 (Lederberg-Coxeter-Fruchte) 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_k-1] 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)                                         # needs networkx
sage: G.is_isomorphic(graphs.TetrahedralGraph())                                # needs networkx
True

sage: G = graphs.LCFGraph(20, [10,7,4,-4,-7,10,-4,7,-7,4], 2)                   # needs networkx
sage: G.is_isomorphic(graphs.DodecahedralGraph())                               # needs networkx
True

sage: G = graphs.LCFGraph(14, [5,-5], 7)                                        # needs networkx
sage: G.is_isomorphic(graphs.HeawoodGraph())                                    # needs networkx
True

The largest cubic nonplanar graph of diameter three:

sage: # needs networkx
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                             # needs sage.plot

PLOTTING: LCF Graphs are plotted as an n-cycle with edges in the middle, as described above.

REFERENCES:

  • [1] Frucht, R. “A Canonical Representation of Trivalent Hamiltonian Graphs.” J. Graph Th. 1, 45-60, 1976.

  • [2] Grunbaum, B. Convex Polytope es. New York: Wiley, pp. 362-364, 1967.

  • [3] Lederberg, J. ‘DENDRAL-64: 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 81-60. 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 spring-layout algorithm. By convention, the complete graph will be drawn in the lower-left 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                             # needs sage.plot
sage.graphs.generators.families.MathonPseudocyclicMergingGraph(M, t)#

Mathon’s merging of classes in a pseudo-cyclic 3-class association scheme

Construct strongly regular graphs from p.97 of [BL1984].

INPUT:

  • M – the list of matrices in a pseudo-cyclic 3-class 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)(4t-1)^2\) vertices from [Mat1978].

Let \(4t-1\) be a prime power, and \(4t+1\) be such that there exists a strongly regular graph \(G\) with parameters \((4t+1,2t,t-1,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, \mu-1, \mu)\), where \(\mu = t(4t(4t-1)-1)\). The construction is optionally parametrised by an a skew-symmetric 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 integer

  • G – if None (default), try to construct the necessary graph with parameters \((4t+1,2t,t-1,t)\), otherwise use the user-supplied one, with vertices labelled from \(0\) to \(4t\).

  • L – if None (default), construct a necessary skew Latin square, otherwise use the user-supplied one. Here non-isomorphic Latin squares – one constructed from \(Z/9Z\), and the other from \((Z/3Z)^2\) – lead to non-isomorphic graphs.

See also

EXAMPLES:

Using default G and L.

sage: from sage.graphs.generators.families import MathonPseudocyclicStronglyRegularGraph
sage: G = MathonPseudocyclicStronglyRegularGraph(1); G                          # needs sage.modules sage.rings.finite_rings
Mathon's PC SRG on 45 vertices: Graph on 45 vertices
sage: G.is_strongly_regular(parameters=True)                                    # needs sage.modules sage.rings.finite_rings
(45, 22, 10, 11)

Supplying G and L (constructed from the automorphism group of G). The entries of L can’t be tested directly because there’s some unpredictability in the way that GAP chooses a representative in NormalSubgroups(), the function that underlies our own normal_subgroups() method:

sage: # needs sage.groups sage.libs.gap sage.rings.finite_rings
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))
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^d-1)/(n-1)+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^{d-1}(m-1) - 1,\mu - 2,\mu)\), where \(\mu=\frac{n^{d-1}-1}{n-1}n^{d-1}\) and \(m:=\frac{n^d-1}{n-1}+1\).

Some details on \(\Phi\) and \(\Sigma\) are as follows. Let \(L\) be the complete graph on \(M:=\{0,..., m-1\}\) 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 non-isomorphic graphs, are in [Muz2007].

INPUT:

  • n (integer) – a prime power

  • d (integer) – must be odd if \(n\) is odd

  • Phi 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: # needs sage.combinat sage.modules sage.rings.finite_rings
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 triangle-free and has chromatic number equal to \(k\). These graphs show, constructively, that there are triangle-free 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 integers range(n) where n is the number of vertices in the graph.

EXAMPLES:

The Mycielski graph \(M_k\) is triangle-free 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:

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 5-cycle 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                             # needs sage.plot
Graphics object consisting of 31 graphics primitives

REFERENCES:

  • Wei-Kuo, Chiang, and Chen Rong-Jaye. “The (n, k)-star graph: A generalized star graph.” Information Processing Letters 56, no. 5 (December 8, 1995): 259-264.

AUTHORS:

  • Michael Yurko (2009-09-01)

sage.graphs.generators.families.NStarGraph(n)#

Returns the n-star graph.

The vertices of the n-star 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                             # needs sage.plot
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 n-cube. In: Proc. Internat. Conf. on Parallel Processing (1987), pp. 393–400.

AUTHORS:

  • Michael Yurko (2009-09-01)

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 \(2n-1,n-1\). Equivalently, the Odd Graph is the graph whose vertices are the \(n-1\)-subsets of \([0,1,\dots,2(n-1)]\), 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                                               # needs sage.rings.finite_rings
Paley graph with parameter 9: Graph on 9 vertices
sage: G.is_regular()                                                            # needs sage.rings.finite_rings
True

A Paley graph is always self-complementary:

sage: G.is_self_complementary()                                                 # needs sage.rings.finite_rings
True
sage.graphs.generators.families.PasechnikGraph(n)#

Pasechnik strongly regular graph on \((4n-1)^2\) vertices

A strongly regular graph with parameters of the orthogonal array graph OrthogonalArrayBlockGraph(), also known as pseudo Latin squares graph \(L_{2n-1}(4n-1)\), constructed from a skew Hadamard matrix of order \(4n\) following [Pas1992].

See also

EXAMPLES:

sage: graphs.PasechnikGraph(4).is_strongly_regular(parameters=True)             # needs sage.combinat sage.modules
(225, 98, 43, 42)
sage: graphs.PasechnikGraph(5).is_strongly_regular(parameters=True)     # long time, needs sage.combinat sage.modules
(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 k-levels.

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=`2^{i+1}-1\).

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: # needs networkx
sage: G = graphs.RingedTree(5)
sage: P = G.plot(vertex_labels=False, vertex_size=10)                           # needs sage.plot
sage: P.show()                          # long time                             # needs sage.plot
sage: G.vertices(sort=True)
['', '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\) determining a-spoke edges

  • r – integer such that \(1 \leq r < n\) and \(r \neq n / 2\) determining how inner vertices are connected

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout 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 outer-circle, 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^{n-1}+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.

../../../_images/families-2.svg

See also

EXAMPLES:

sage: # needs sage.modules
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:

[LLWC2011]

sage.graphs.generators.families.SquaredSkewHadamardMatrixGraph(n)#

Pseudo-\(OA(2n,4n-1)\)-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}(4n-1)\), constructed from a skew Hadamard matrix of order \(4n\), due to Goethals and Seidel, see [BL1984].

See also

EXAMPLES:

sage: # needs sage.combinat sage.modules
sage: G = graphs.SquaredSkewHadamardMatrixGraph(4)
sage: G.is_strongly_regular(parameters=True)
(225, 112, 55, 56)
sage: G = graphs.SquaredSkewHadamardMatrixGraph(5)
sage: G.is_strongly_regular(parameters=True)    # long time
(361, 180, 89, 90)
sage: G = graphs.SquaredSkewHadamardMatrixGraph(9)
sage: G.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 1-vertex graph and the one produced by Pseudo-L_{2n}(4n-1)

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: # needs sage.combinat sage.modules
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: gc = g.complement()
sage: twograph_descendant(gc, 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 a-spoke edges

  • b – integer such that \(0 < b < n\) and \(b \neq a\), that determines b-spoke edges

  • r – 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 spring-layout 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 outer-circle, 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 spring-layout algorithm. By convention, the cycle graph will be drawn in the lower-left 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                             # needs sage.plot
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 \(\frac{(r-1)(n^2-s^2)}{2r} + \frac{s(s-1)}{2}\) edges, where \(s = n \mod r\) (github issue #34249):

sage: n = 12
sage: r = 8
sage: g = graphs.TuranGraph(n, r)
sage: def count(n, r):
....:     s = n % r
....:     return (r - 1) * (n**2 - s**2) / (2*r) + s*(s - 1)/2
sage: g.size() == count(n, r)
True
sage: n = randint(3, 100)
sage: r = randint(2, n - 1)
sage: g = graphs.TuranGraph(n, r)
sage: g.size() == count(n, 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 spring-layout 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 spring-layout to give a counter-intuitive 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: # needs sage.plot
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 spring-layout algorithm:

sage: # needs networkx sage.plot
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: # needs networkx sage.plot
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 \((k-1)n+1\) vertices and \(nk(k-1)/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 \((k-1)\)-edge-connected. It is trivially perfect and a block graph.

See also

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 non-isomorphic 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(sort=False),                            # needs sage.modules
....:      [(0,1,None),(2,3,None),(4,5,None),(6,7,None)],
....:      K8.subgraph_search(c3c5).edges(sort=False)]
sage: [T8.seidel_switching(x, inplace=False).is_isomorphic(G)                   # needs sage.modules
....:  for x, G in zip(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.nauty_gentreeg(options='', debug=False)#

Return a generator which creates non-isomorphic trees from nauty’s gentreeg program.

INPUT:

  • options – string (default: ""); a string passed to gentreeg as if it was run at a system command line. At a minimum, you must pass the number of vertices you desire. Sage expects the graphs to be in nauty’s “sparse6” format, do not set an option to change this default or results will be unpredictable.

  • debug – boolean (default: False); if True the first line of gentreeg’s output to standard error is captured and the first call to the generator’s next() function will return this line as a string. A line leading with “>A” indicates a successful initiation of the program with some information on the arguments, while a line beginning with “>E” indicates an error with the input.

The possible options, obtained as output of gentreeg -help:

   n            : the number of vertices. Must be in range 1..128
res/mod         : only generate subset res out of subsets 0..mod-1
  -D<int>       : an upper bound for the maximum degree
  -Z<int>:<int> : bounds on the diameter
  -q            : suppress auxiliary output

Options which cause gentreeg to use an output format different than the sparse6 format are not listed above (-p, -l, -u) as they will confuse the creation of a Sage graph. The res/mod option can be useful when using the output in a routine run several times in parallel.

OUTPUT:

A generator which will produce the graphs as Sage graphs. These will be simple graphs: no loops, no multiple edges, no directed edges.

See also

trees() – another generator of trees

EXAMPLES:

The generator can be used to construct trees for testing, one at a time (usually inside a loop). Or it can be used to create an entire list all at once if there is sufficient memory to contain it:

sage: gen = graphs.nauty_gentreeg("4")
sage: next(gen)
Graph on 4 vertices
sage: next(gen)
Graph on 4 vertices
sage: next(gen)
Traceback (most recent call last):
...
StopIteration

The number of trees on the first few vertex counts. This agrees with OEIS sequence A000055:

sage: [len(list(graphs.nauty_gentreeg(str(i)))) for i in range(1, 15)]
[1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159]

The debug switch can be used to examine gentreeg’s reaction to the input in the options string. We illustrate success. (A failure will be a string beginning with “>E”.) Passing the “-q” switch to gentreeg will suppress the indicator of a successful initiation, and so the first returned value might be an empty string if debug is True:

sage: gen = graphs.nauty_gentreeg("4", debug=True)
sage: print(next(gen))
>A ...gentreeg ...
sage: gen = graphs.nauty_gentreeg("4 -q", debug=True)
sage: next(gen)
''
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 \(\Delta-Y\) transformations. When set to False (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)                                # needs sage.modules
sage: F1 = [g.canonical_label().graph6_string() for g in F1]
sage: F2 = [g.canonical_label().graph6_string() for g in F2]                    # needs sage.modules
sage: set(F1) == set(F2)                                                        # needs sage.modules
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, duplicate-free 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]