Various families of graphs#
The methods defined here appear in sage.graphs.graph_generators.
- sage.graphs.generators.families.AztecDiamondGraph(n)[source]#
-
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
>>> from sage.all import * >>> graphs.AztecDiamondGraph(Integer(2)) Aztec Diamond graph of order 2 >>> [graphs.AztecDiamondGraph(i).num_verts() for i in range(Integer(8))] [0, 4, 12, 24, 40, 60, 84, 112] >>> [graphs.AztecDiamondGraph(i).num_edges() for i in range(Integer(8))] [0, 4, 16, 36, 64, 100, 144, 196] >>> G = graphs.AztecDiamondGraph(Integer(3)) >>> sum(Integer(1) for p in G.perfect_matchings()) 64
- sage.graphs.generators.families.BalancedTree(r, h)[source]#
Return 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\).
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() 3 sage: G.size() 2 sage: r = 2; h = 1 sage: v = 1 + r sage: v; v - 1 3 2
>>> from sage.all import * >>> G = graphs.BalancedTree(Integer(2), Integer(1)); G Balanced tree: Graph on 3 vertices >>> G.order() 3 >>> G.size() 2 >>> r = Integer(2); h = Integer(1) >>> v = Integer(1) + r >>> v; v - Integer(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.plot() # long time # needs sage.plot Graphics object consisting of 728 graphics primitives
>>> from sage.all import * >>> G = graphs.BalancedTree(Integer(3), Integer(5)) >>> G.plot() # long time # needs sage.plot Graphics object consisting of 728 graphics primitives
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
>>> from sage.all import * >>> # needs networkx >>> r = randint(Integer(2), Integer(5)); h = randint(Integer(1), Integer(7)) >>> T = graphs.BalancedTree(r, h) >>> T.is_bipartite() True >>> T.is_planar() True >>> v = (r**(h + Integer(1)) - Integer(1)) / (r - Integer(1)) >>> T.order() == v True >>> T.size() == v - Integer(1) True
- sage.graphs.generators.families.BarbellGraph(n1, n2)[source]#
Returns a barbell graph with \(2*n_1 + n_2\) nodes.
The argument \(n_1\) must be greater than or equal to 2.
A barbell graph is a basic structure that consists of a path graph of order \(n_2\) connecting two complete graphs of order \(n_1\) 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*n_1 + n_2\). A
ValueErroris returned if \(n_1 < 2\) or \(n_2 < 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 \(n_1\)-th node will be drawn at a 45 degree angle from the horizontal right center of the first complete graph, and the \(n_1 + n_2 + 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
>>> from sage.all import * >>> g = graphs.BarbellGraph(Integer(9), Integer(4)); g Barbell graph: Graph on 22 vertices >>> g.show() # long time # needs sage.plot
An \(n_1 \geq 2\), \(n_2 \geq 0\) barbell graph has order \(2*n_1 + n_2\). It has the complete graph on \(n_1\) vertices as a subgraph. It also has the path graph on \(n_2\) 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
>>> from sage.all import * >>> n1 = randint(Integer(2), Integer(2)*Integer(10)**Integer(2)) >>> n2 = randint(Integer(0), Integer(2)*Integer(10)**Integer(2)) >>> g = graphs.BarbellGraph(n1, n2) >>> v = Integer(2)*n1 + n2 >>> g.order() == v True >>> K_n1 = graphs.CompleteGraph(n1) >>> P_n2 = graphs.PathGraph(n2) >>> # needs sage.modules >>> s_K = g.subgraph_search(K_n1, induced=True) >>> s_P = g.subgraph_search(P_n2, induced=True) >>> K_n1.is_isomorphic(s_K) True >>> P_n2.is_isomorphic(s_P) True
- sage.graphs.generators.families.BubbleSortGraph(n)[source]#
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
ValueErroris 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
>>> from sage.all import * >>> g = graphs.BubbleSortGraph(Integer(4)); g Bubble sort: Graph on 24 vertices >>> 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
>>> from sage.all import * >>> graphs.BubbleSortGraph(Integer(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
>>> from sage.all import * >>> n = randint(Integer(1), Integer(8)) >>> g = graphs.BubbleSortGraph(n) >>> g.order() == factorial(n) True
See also
AUTHORS:
Michael Yurko (2009-09-01)
- sage.graphs.generators.families.CaiFurerImmermanGraph(G, twisted=False)[source]#
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 theCai-Furer-Immerman graph
twisted– A boolean indicating if the version to constructis a twisted one or not
OUTPUT:
H– The Cai-Furer-Immerman graph onGcoloring– 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)]
>>> from sage.all import * >>> G = graphs.CycleGraph(Integer(4)) >>> CFI, p = graphs.CaiFurerImmermanGraph(G) >>> 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'))] >>> 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)[source]#
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 graphadjacency– 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
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: # 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
>>> from sage.all import * >>> # needs networkx >>> import networkx >>> n = networkx.cycle_graph(Integer(23)) >>> spring23 = Graph(n) >>> posdict23 = graphs.CirculantGraph(Integer(23),Integer(2)) >>> spring23.show() # long time >>> posdict23.show() # long time
We next view many cycle graphs as a Sage graphics array. First we use the
CirculantGraphconstructor, 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
>>> from sage.all import * >>> # needs sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.CirculantGraph(i+Integer(4), i+Integer(1)) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> 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
>>> from sage.all import * >>> # needs networkx sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... spr = networkx.cycle_graph(i+Integer(3)) ... k = Graph(spr) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> 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)]
>>> from sage.all import * >>> graphs.CirculantGraph(Integer(6),Integer(1)) == graphs.CycleGraph(Integer(6)) True >>> graphs.CirculantGraph(Integer(7),[Integer(1),Integer(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)[source]#
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
>>> from sage.all import * >>> d = Integer(3) >>> g = graphs.CubeConnectedCycle(d) >>> len(g) == d*Integer(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
>>> from sage.all import * >>> d = Integer(4) >>> g = graphs.CubeConnectedCycle(d) >>> g.diameter() == Integer(2)*d+d//Integer(2)-Integer(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
>>> from sage.all import * >>> g = graphs.CubeConnectedCycle(Integer(5)) >>> all(g.degree(v) == Integer(3) for v in g) True
- sage.graphs.generators.families.CubeGraph(n, embedding=1)[source]#
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 graphembedding– 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.NoneorO: 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
>>> from sage.all import * >>> g = graphs.CubeGraph(Integer(7)) >>> 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
>>> from sage.all import * >>> # needs sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(6)): ... k = graphs.CubeGraph(i+Integer(1)) ... g.append(k) ... >>> for i in range(Integer(2)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) ... >>> G = graphics_array(j) >>> G.show(figsize=[Integer(6),Integer(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
>>> from sage.all import * >>> g = graphs.CubeGraph(Integer(9), embedding=Integer(1)) >>> g.show(figsize=[Integer(12),Integer(12)],vertex_labels=False, vertex_size=Integer(20)) # long time, needs sage.plot >>> g = graphs.CubeGraph(Integer(9), embedding=Integer(2)) >>> g.show(figsize=[Integer(12),Integer(12)],vertex_labels=False, vertex_size=Integer(20)) # long time, needs sage.plot >>> g = graphs.CubeGraph(Integer(9), embedding=Integer(3)) >>> g.show(figsize=[Integer(12),Integer(12)],vertex_labels=False, vertex_size=Integer(20)) # long time, needs sage.plot
AUTHORS:
Robert Miller
David Coudert
- sage.graphs.generators.families.DipoleGraph(n)[source]#
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
>>> from sage.all import * >>> g = graphs.DipoleGraph(Integer(13)); g Dipole graph: Multi-graph on 2 vertices >>> g.show() # long time # needs sage.plot
- sage.graphs.generators.families.DorogovtsevGoltsevMendesGraph(n)[source]#
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
>>> from sage.all import * >>> G = graphs.DorogovtsevGoltsevMendesGraph(Integer(8)) # needs networkx >>> 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)[source]#
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
>>> from sage.all import * >>> g = graphs.DoubleGeneralizedPetersenGraph(Integer(10), Integer(2)) >>> g2 = graphs.DoubleGeneralizedPetersenGraph(Integer(10), Integer(3)) >>> g.is_isomorphic(g2) True
- sage.graphs.generators.families.EgawaGraph(p, s)[source]#
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 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
>>> from sage.all import * >>> g = graphs.EgawaGraph(Integer(1), Integer(2)) >>> 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
>>> from sage.all import * >>> g = graphs.EgawaGraph(Integer(0), Integer(4)) >>> g.is_isomorphic(graphs.HammingGraph(Integer(4),Integer(4))) True
- sage.graphs.generators.families.FibonacciTree(n)[source]#
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
>>> from sage.all import * >>> g = graphs.FibonacciTree(Integer(3)) # needs sage.libs.pari >>> 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
>>> from sage.all import * >>> l1 = [ len(graphs.FibonacciTree(_)) + Integer(1) for _ in range(Integer(6)) ] # needs sage.libs.pari >>> l2 = list(fibonacci_sequence(Integer(2),Integer(8))) # needs sage.libs.pari >>> l1 == l2 # needs sage.libs.pari True
AUTHORS:
Harald Schilly and Yann Laigle-Chapuy (2010-03-25)
- sage.graphs.generators.families.FoldedCubeGraph(n)[source]#
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
>>> from sage.all import * >>> fc = graphs.FoldedCubeGraph(Integer(5)) >>> clebsch = graphs.ClebschGraph() >>> fc.is_isomorphic(clebsch) True
- sage.graphs.generators.families.FriendshipGraph(n)[source]#
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
>>> from sage.all import * >>> # needs sage.plot >>> A = []; B = [] >>> for i in range(Integer(9)): ... g = graphs.FriendshipGraph(i + Integer(1)) ... A.append(g) >>> for i in range(Integer(3)): ... n = [] ... for j in range(Integer(3)): ... n.append(A[Integer(3)*i + j].plot(vertex_size=Integer(20), vertex_labels=False)) ... B.append(n) >>> G = graphics_array(B) >>> 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
>>> from sage.all import * >>> G = graphs.FriendshipGraph(Integer(1)); G Friendship graph: Graph on 3 vertices >>> G.show() # long time # needs sage.plot >>> G.is_isomorphic(graphs.CycleGraph(Integer(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
>>> from sage.all import * >>> G = graphs.FriendshipGraph(Integer(2)); G Friendship graph: Graph on 5 vertices >>> 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
>>> from sage.all import * >>> n = randint(Integer(2), Integer(10)**Integer(3)) >>> G = graphs.FriendshipGraph(n) >>> G.order() == Integer(2)*n + Integer(1) True >>> G.size() == Integer(3)*n True >>> G.radius() 1 >>> G.diameter() 2 >>> G.girth() 3 >>> G.chromatic_number() 3 >>> G.is_planar() True >>> G.is_eulerian() True
- sage.graphs.generators.families.FurerGadget(k, prefix=None)[source]#
Return a Furer gadget of order
kand 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 orderkcoloring– 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)]
>>> from sage.all import * >>> G, p = graphs.FurerGadget(Integer(3)) >>> sorted(G, key=str) [(), (0, 'a'), (0, 'b'), (0, 1), (0, 2), (1, 'a'), (1, 'b'), (1, 2), (2, 'a'), (2, 'b')] >>> 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)]
>>> from sage.all import * >>> G, p = graphs.FurerGadget(Integer(3), 'Prefix') >>> 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'))] >>> 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)[source]#
Construct a Fuzzy Ball graph with the integer partition
partitionandqextra 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]
>>> from sage.all import * >>> F = graphs.FuzzyBallGraph([Integer(3),Integer(1)],Integer(2)) >>> 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}
>>> from sage.all import * >>> m = Integer(4); q = Integer(2); k = Integer(2) >>> g_list = [graphs.FuzzyBallGraph(p,q) # needs sage.combinat sage.modules ... for p in Partitions(m, length=k)] >>> 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)[source]#
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
>>> from sage.all import * >>> g = graphs.GeneralizedPetersenGraph(Integer(13),Integer(1)) >>> g2 = graphs.CircularLadderGraph(Integer(13)) >>> g.is_isomorphic(g2) True
The Desargues graph:
sage: g = graphs.GeneralizedPetersenGraph(10,3) sage: g.girth() 6 sage: g.is_bipartite() True
>>> from sage.all import * >>> g = graphs.GeneralizedPetersenGraph(Integer(10),Integer(3)) >>> g.girth() 6 >>> g.is_bipartite() True
AUTHORS:
Anders Jonsson (2009-10-15)
- sage.graphs.generators.families.GeneralizedSierpinskiGraph(G, k, stretch=None)[source]#
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 Graphk– integer; the dimensionstretch– 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
>>> from sage.all import * >>> G = graphs.RandomGNP(Integer(10), RealNumber('.5')) >>> S = graphs.GeneralizedSierpinskiGraph(G, Integer(1)) >>> 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
>>> from sage.all import * >>> k = randint(Integer(1), Integer(5)) >>> S = graphs.GeneralizedSierpinskiGraph(graphs.CompleteGraph(Integer(3)), k) # needs sage.modules >>> H = graphs.HanoiTowerGraph(Integer(3), k) >>> 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
>>> from sage.all import * >>> # needs sage.modules >>> n = randint(Integer(2), Integer(6)) >>> k = randint(Integer(1), Integer(5)) >>> G = graphs.RandomGNP(n, RealNumber('.5')) >>> m = G.size() >>> S = graphs.GeneralizedSierpinskiGraph(G, k) >>> S.order() == n**k True >>> S.size() == m*sum([n**i for i in range(k)]) True >>> G = graphs.CompleteGraph(n) >>> S = graphs.GeneralizedSierpinskiGraph(G, k) >>> S.order() == n**k True >>> S.size() == (n*(n - Integer(1))/Integer(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
>>> from sage.all import * >>> G = graphs.HouseGraph() >>> G.get_pos() is not None True >>> H = graphs.GeneralizedSierpinskiGraph(G, Integer(2)) # needs sage.symbolic >>> H.get_pos() is not None # needs sage.symbolic True >>> G = Graph([(Integer(0), Integer(1))]) >>> G.get_pos() is not None False >>> H = graphs.GeneralizedSierpinskiGraph(G, Integer(2)) # needs sage.symbolic >>> H.get_pos() is not None # needs sage.symbolic False
- sage.graphs.generators.families.GoethalsSeidelGraph(k, r)[source]#
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)-BIBDwith \(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+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)
>>> from sage.all import * >>> graphs.GoethalsSeidelGraph(Integer(3),Integer(3)) # needs sage.combinat sage.modules Graph on 28 vertices >>> graphs.GoethalsSeidelGraph(Integer(3),Integer(3)).is_strongly_regular(parameters=True) # needs sage.combinat sage.modules (28, 15, 6, 10)
- sage.graphs.generators.families.HammingGraph(n, q, X=None)[source]#
Return 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 whichXwill be raised to provide verticesfor the Hamming graph
q– cardinality ofXX– list of labels representing the vertices of theunderlying 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
>>> from sage.all import * >>> g = graphs.HammingGraph(Integer(3), Integer(7)) >>> g.is_distance_regular() True >>> g.is_regular() True >>> 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
>>> from sage.all import * >>> g = graphs.HammingGraph(Integer(1), Integer(23)) >>> g.is_isomorphic(graphs.CompleteGraph(Integer(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
>>> from sage.all import * >>> X = ['a','b','c','d','e'] >>> g = graphs.HammingGraph(Integer(2), Integer(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)[source]#
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, ifTruethe graph contains more meaningful labels, see explanation below. For large instances, turn off labels for much faster creation of the graph.positions– default:True, ifTruethe 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 thepadstooption 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 = Truewill 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
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(3), Integer(5), labels=False, positions=False) >>> H.distance(Integer(0), Integer(3)**Integer(5)-Integer(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
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(4), Integer(6), labels=False, positions=False) >>> H.num_verts() 4096 >>> H.distance(Integer(0), Integer(4)**Integer(6)-Integer(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)]
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(3), Integer(3), labels=True, positions=True) >>> H.shortest_path((Integer(0),Integer(0),Integer(0)), (Integer(1),Integer(1),Integer(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
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(3), Integer(4), labels=False, positions=False) >>> H.automorphism_group().is_isomorphic(SymmetricGroup(Integer(3))) # needs sage.groups True >>> H.chromatic_number() 3 >>> len(H.independent_set()) == Integer(3)**(Integer(4)-Integer(1)) True
AUTHOR:
Rob Beezer, (2009-12-26), with assistance from Su Doree
- sage.graphs.generators.families.HararyGraph(k, n)[source]#
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 [West2001] 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
>>> from sage.all import * >>> h = graphs.HararyGraph(Integer(5),Integer(9)); h Harary graph 5, 9: Graph on 9 vertices >>> h.order() 9 >>> h.size() 23 >>> h.vertex_connectivity() # needs sage.numerical.mip 5
- sage.graphs.generators.families.HyperStarGraph(n, k)[source]#
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 stringsk– 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
>>> from sage.all import * >>> g = graphs.HyperStarGraph(Integer(6),Integer(3)) >>> sorted(g.neighbors('011100')) ['101100', '110100', '111000'] >>> 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)[source]#
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 connectedk– 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
>>> from sage.all import * >>> g = graphs.IGraph(Integer(7),Integer(1),Integer(2)) >>> g2 = graphs.GeneralizedPetersenGraph(Integer(7),Integer(2)) >>> 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
>>> from sage.all import * >>> g = graphs.IGraph(Integer(7), Integer(2), Integer(3)) >>> h = graphs.IGraph(Integer(7), Integer(3), Integer(2)) >>> g.is_isomorphic(h) True
- sage.graphs.generators.families.JohnsonGraph(n, k)[source]#
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
>>> from sage.all import * >>> g = graphs.JohnsonGraph(Integer(7), Integer(3)) >>> 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
>>> from sage.all import * >>> g = graphs.JohnsonGraph(Integer(6), Integer(4)) >>> 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
>>> from sage.all import * >>> g = graphs.JohnsonGraph(Integer(5),Integer(2)) >>> g.complement().is_isomorphic(graphs.PetersenGraph()) True
- sage.graphs.generators.families.KneserGraph(n, k)[source]#
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
>>> from sage.all import * >>> KG = graphs.KneserGraph(Integer(5),Integer(2)) >>> 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}] >>> P = graphs.PetersenGraph() >>> P.is_isomorphic(KG) True
- sage.graphs.generators.families.LCFGraph(n, shift_list, repeats)[source]#
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 \in \{0, 1, \dots, k-1\}\), connect vertex \(i\) to vertex \((i + s_i) \pmod{n}\). Then,repeatsspecifies the number of times to repeat this process, where on the \(j\)-th repeat we connect vertex \((i + j k) \pmod{n}\) to vertex \((i + j k + s_i) \pmod{n}\).For more details, see the Wikipedia article LCF_notation and [Fru1977], [Gru2003] pp. 357-365, and [Led1965].
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
>>> from sage.all import * >>> G = graphs.LCFGraph(Integer(4), [Integer(2),-Integer(2)], Integer(2)) # needs networkx >>> 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
>>> from sage.all import * >>> G = graphs.LCFGraph(Integer(20), [Integer(10),Integer(7),Integer(4),-Integer(4),-Integer(7),Integer(10),-Integer(4),Integer(7),-Integer(7),Integer(4)], Integer(2)) # needs networkx >>> 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
>>> from sage.all import * >>> G = graphs.LCFGraph(Integer(14), [Integer(5),-Integer(5)], Integer(7)) # needs networkx >>> 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
>>> from sage.all import * >>> # needs networkx >>> G = graphs.LCFGraph(Integer(20), [-Integer(10),-Integer(7),-Integer(5),Integer(4),Integer(7),-Integer(10),-Integer(7),-Integer(4),Integer(5),Integer(7), ... -Integer(10),-Integer(7),Integer(6),-Integer(5),Integer(7),-Integer(10),-Integer(7),Integer(5),-Integer(6),Integer(7)], Integer(1)) >>> G.degree() [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] >>> G.diameter() 3 >>> G.show() # long time # needs sage.plot
PLOTTING: LCF Graphs are plotted as an \(n\)-cycle with edges in the middle, as described above.
- sage.graphs.generators.families.LollipopGraph(n1, n2)[source]#
Returns a lollipop graph with \(n_1 + n_2\) nodes.
A lollipop graph is a path graph (order \(n_2\)) connected to a complete graph (order \(n_1\)). (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 \(n_1\)-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
>>> from sage.all import * >>> g = graphs.LollipopGraph(Integer(13),Integer(4)); g Lollipop graph: Graph on 17 vertices >>> g.show() # long time # needs sage.plot
- sage.graphs.generators.families.MathonPseudocyclicMergingGraph(M, t)[source]#
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)[source]#
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 integerG– ifNone(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– ifNone(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
GandL.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)
>>> from sage.all import * >>> from sage.graphs.generators.families import MathonPseudocyclicStronglyRegularGraph >>> G = MathonPseudocyclicStronglyRegularGraph(Integer(1)); G # needs sage.modules sage.rings.finite_rings Mathon's PC SRG on 45 vertices: Graph on 45 vertices >>> G.is_strongly_regular(parameters=True) # needs sage.modules sage.rings.finite_rings (45, 22, 10, 11)
Supplying
GandL(constructed from the automorphism group ofG). The entries of L can’t be tested directly because there’s some unpredictability in the way that GAP chooses a representative inNormalSubgroups(), the function that underlies our ownnormal_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
>>> from sage.all import * >>> # needs sage.groups sage.libs.gap sage.rings.finite_rings >>> G = graphs.PaleyGraph(Integer(9)) >>> a = G.automorphism_group(partition=[sorted(G)]) >>> it = (x for x in a.normal_subgroups() if x.order() == Integer(9)) >>> subg = next(iter(it)) >>> r = [matrix(libgap.PermutationMat(libgap(z), Integer(9)).sage()) ... for z in subg] >>> ff = list(map(lambda y: (y[Integer(0)]-Integer(1),y[Integer(1)]-Integer(1)), ... Permutation(map(lambda x: Integer(1)+r.index(x**-Integer(1)), r)).cycle_tuples()[Integer(1):])) >>> L = sum(i*(r[a]-r[b]) for i,(a,b) in zip(range(Integer(1),len(ff)+Integer(1)), ff)) >>> G.relabel(range(Integer(9))) >>> G3x3 = graphs.MathonPseudocyclicStronglyRegularGraph(Integer(2), G=G, L=L) >>> G3x3.is_strongly_regular(parameters=True) (441, 220, 109, 110) >>> G3x3.automorphism_group(algorithm="bliss").order() # optional - bliss 27 >>> G9 = graphs.MathonPseudocyclicStronglyRegularGraph(Integer(2)) >>> G9.is_strongly_regular(parameters=True) (441, 220, 109, 110) >>> G9.automorphism_group(algorithm="bliss").order() # optional - bliss 9
- sage.graphs.generators.families.MuzychukS6Graph(n, d, Phi='fixed', Sigma='fixed', verbose=False)[source]#
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 powerd(integer) – must be odd if \(n\) is oddPhiis 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, orA 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.
Sigmais 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 isFalse. IfTrue, 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)
>>> from sage.all import * >>> # needs sage.combinat sage.modules sage.rings.finite_rings >>> graphs.MuzychukS6Graph(Integer(3), Integer(3)).is_strongly_regular(parameters=True) (378, 116, 34, 36) >>> phi = {(Integer(2),(Integer(0),Integer(2))):Integer(0), (Integer(1),(Integer(1),Integer(3))):Integer(1), (Integer(0),(Integer(0),Integer(3))):Integer(1), (Integer(2),(Integer(1),Integer(2))):Integer(1), ... (Integer(1),(Integer(1),Integer(2))):Integer(0), (Integer(0),(Integer(0),Integer(2))):Integer(0), (Integer(3),(Integer(0),Integer(3))):Integer(0), (Integer(3),(Integer(1),Integer(3))):Integer(1)} >>> graphs.MuzychukS6Graph(Integer(2), Integer(2), Phi=phi).is_strongly_regular(parameters=True) (16, 5, 0, 2)
- sage.graphs.generators.families.MycielskiGraph(k=1, relabel=True)[source]#
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\).
For more details, see the Wikipedia article Mycielskian.
INPUT:
kNumber of steps in the construction process.relabelRelabel the vertices so their names are the integersrange(n)wherenis 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
>>> from sage.all import * >>> g = graphs.MycielskiGraph(Integer(5)) >>> g.is_triangle_free() True >>> 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
>>> from sage.all import * >>> g = graphs.MycielskiGraph(Integer(4)) >>> g.is_isomorphic(graphs.GrotzschGraph()) True
- sage.graphs.generators.families.MycielskiStep(g)[source]#
Perform one iteration of the Mycielski construction.
See the documentation for
MycielskiGraphwhich 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
>>> from sage.all import * >>> g = graphs.CycleGraph(Integer(5)) >>> h = graphs.MycielskiStep(g) >>> h.is_isomorphic(graphs.GrotzschGraph()) True
- sage.graphs.generators.families.NKStarGraph(n, k)[source]#
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– integer; number of symbolsk– integer; length of the labels of the vertices
EXAMPLES:
sage: g = graphs.NKStarGraph(4,2) sage: g.plot() # long time # needs sage.plot Graphics object consisting of 31 graphics primitives
>>> from sage.all import * >>> g = graphs.NKStarGraph(Integer(4),Integer(2)) >>> g.plot() # long time # needs sage.plot Graphics object consisting of 31 graphics primitives
REFERENCES:
AUTHORS:
Michael Yurko (2009-09-01)
- sage.graphs.generators.families.NStarGraph(n)[source]#
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– integer; number of symbols
EXAMPLES:
sage: g = graphs.NStarGraph(4) sage: g.plot() # long time # needs sage.plot Graphics object consisting of 61 graphics primitives
>>> from sage.all import * >>> g = graphs.NStarGraph(Integer(4)) >>> g.plot() # long time # needs sage.plot Graphics object consisting of 61 graphics primitives
REFERENCES:
AUTHORS:
Michael Yurko (2009-09-01)
- sage.graphs.generators.families.OddGraph(n)[source]#
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
>>> from sage.all import * >>> OG = graphs.OddGraph(Integer(3)) >>> 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}] >>> P = graphs.PetersenGraph() >>> P.is_isomorphic(OG) True
- sage.graphs.generators.families.PaleyGraph(q)[source]#
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
>>> from sage.all import * >>> G = graphs.PaleyGraph(Integer(9)); G # needs sage.rings.finite_rings Paley graph with parameter 9: Graph on 9 vertices >>> 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
>>> from sage.all import * >>> G.is_self_complementary() # needs sage.rings.finite_rings True
- sage.graphs.generators.families.PasechnikGraph(n)[source]#
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)
>>> from sage.all import * >>> graphs.PasechnikGraph(Integer(4)).is_strongly_regular(parameters=True) # needs sage.combinat sage.modules (225, 98, 43, 42) >>> graphs.PasechnikGraph(Integer(5)).is_strongly_regular(parameters=True) # long time, needs sage.combinat sage.modules (361, 162, 73, 72) >>> graphs.PasechnikGraph(Integer(9)).is_strongly_regular(parameters=True) # not tested (1225, 578, 273, 272)
- sage.graphs.generators.families.RingedTree(k, vertex_labels=True)[source]#
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']
>>> from sage.all import * >>> # needs networkx >>> G = graphs.RingedTree(Integer(5)) >>> P = G.plot(vertex_labels=False, vertex_size=Integer(10)) # needs sage.plot >>> P.show() # long time # needs sage.plot >>> 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)[source]#
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 edgesr– 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 \pmod{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
>>> from sage.all import * >>> G = graphs.RoseWindowGraph(Integer(5), Integer(1), Integer(2)) >>> all(G.degree(u) == Integer(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
>>> from sage.all import * >>> G = graphs.RoseWindowGraph(Integer(3), Integer(2), Integer(1)) >>> all(G.degree(u) == Integer(4) for u in G) True
- sage.graphs.generators.families.SierpinskiGasketGraph(n)[source]#
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.
See also
HanoiTowerGraph(). There is another family of graphs called Sierpinski graphs, where all vertices but 3 have valence 3. They are available usinggraphs.HanoiTowerGraph(3, n).
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
>>> from sage.all import * >>> # needs sage.modules >>> s4 = graphs.SierpinskiGasketGraph(Integer(4)); s4 Graph on 42 vertices >>> s4.size() 81 >>> s4.degree_histogram() [0, 0, 3, 0, 39] >>> s4.is_hamiltonian() True
REFERENCES:
- sage.graphs.generators.families.SquaredSkewHadamardMatrixGraph(n)[source]#
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)
>>> from sage.all import * >>> # needs sage.combinat sage.modules >>> G = graphs.SquaredSkewHadamardMatrixGraph(Integer(4)) >>> G.is_strongly_regular(parameters=True) (225, 112, 55, 56) >>> G = graphs.SquaredSkewHadamardMatrixGraph(Integer(5)) >>> G.is_strongly_regular(parameters=True) # long time (361, 180, 89, 90) >>> G = graphs.SquaredSkewHadamardMatrixGraph(Integer(9)) >>> G.is_strongly_regular(parameters=True) # not tested (1225, 612, 305, 306)
- sage.graphs.generators.families.SwitchedSquaredSkewHadamardMatrixGraph(n)[source]#
A strongly regular graph in Seidel switching class of
SquaredSkewHadamardMatrixGraph().A strongly regular graph in the
Seidel switchingclass of the disjoint union of a 1-vertex graph and the one produced byPseudo-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)
>>> from sage.all import * >>> # needs sage.combinat sage.modules >>> g = graphs.SwitchedSquaredSkewHadamardMatrixGraph(Integer(4)) >>> g.is_strongly_regular(parameters=True) (226, 105, 48, 49) >>> from sage.combinat.designs.twographs import twograph_descendant >>> twograph_descendant(g, Integer(0)).is_strongly_regular(parameters=True) (225, 112, 55, 56) >>> gc = g.complement() >>> twograph_descendant(gc, Integer(0)).is_strongly_regular(parameters=True) (225, 112, 55, 56)
- sage.graphs.generators.families.TabacjnGraph(n, a, b, r)[source]#
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 edgesb– integer such that \(0 < b < n\) and \(b \neq a\), that determines b-spoke 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 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 \pmod{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
>>> from sage.all import * >>> G = graphs.TabacjnGraph(Integer(3), Integer(1), Integer(2), Integer(1)) >>> G.degree() [5, 5, 5, 5, 5, 5] >>> G.is_isomorphic(graphs.CompleteGraph(Integer(6))) True >>> G = graphs.TabacjnGraph(Integer(6), Integer(1), Integer(5), Integer(2)) >>> I = graphs.IcosahedralGraph() >>> G.is_isomorphic(I) True
- sage.graphs.generators.families.TadpoleGraph(n1, n2)[source]#
Return a tadpole graph with \(n_1 + n_2\) nodes.
A tadpole graph is a path graph (order \(n_2\)) connected to a cycle graph (order \(n_1\)).
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 \(n_1\)-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
>>> from sage.all import * >>> g = graphs.TadpoleGraph(Integer(13), Integer(4)); g Tadpole graph: Graph on 17 vertices >>> g.show() # long time # needs sage.plot
- sage.graphs.generators.families.TuranGraph(n, r)[source]#
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 graphr– 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
>>> from sage.all import * >>> g = graphs.TuranGraph(Integer(13), Integer(4)) >>> k = graphs.CompleteMultipartiteGraph([Integer(3),Integer(3),Integer(3),Integer(4)]) >>> 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\) (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
>>> from sage.all import * >>> n = Integer(12) >>> r = Integer(8) >>> g = graphs.TuranGraph(n, r) >>> def count(n, r): ... s = n % r ... return (r - Integer(1)) * (n**Integer(2) - s**Integer(2)) / (Integer(2)*r) + s*(s - Integer(1))/Integer(2) >>> g.size() == count(n, r) True >>> n = randint(Integer(3), Integer(100)) >>> r = randint(Integer(2), n - Integer(1)) >>> g = graphs.TuranGraph(n, r) >>> g.size() == count(n, r) True
- sage.graphs.generators.families.WheelGraph(n)[source]#
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
>>> from sage.all import * >>> # needs sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.WheelGraph(i+Integer(3)) ... g.append(k) ... >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) ... >>> G = graphics_array(j) >>> 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
>>> from sage.all import * >>> # needs networkx sage.plot >>> import networkx >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... spr = networkx.wheel_graph(i+Integer(3)) ... k = Graph(spr) ... g.append(k) ... >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) ... >>> G = graphics_array(j) >>> 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
>>> from sage.all import * >>> # needs networkx sage.plot >>> n = networkx.wheel_graph(Integer(23)) >>> spring23 = Graph(n) >>> posdict23 = graphs.WheelGraph(Integer(23)) >>> spring23.show() # long time >>> posdict23.show() # long time
- sage.graphs.generators.families.WindmillGraph(k, n)[source]#
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
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
>>> from sage.all import * >>> n = Integer(5) >>> W = graphs.WindmillGraph(Integer(2), n) >>> 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
>>> from sage.all import * >>> n = Integer(5) >>> W = graphs.WindmillGraph(Integer(3), n) >>> 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
>>> from sage.all import * >>> W = graphs.WindmillGraph(Integer(3), Integer(2)) >>> 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
>>> from sage.all import * >>> n,k = Integer(5),Integer(6) >>> W = graphs.WindmillGraph(k, n) >>> W.chromatic_number() == k True
- sage.graphs.generators.families.chang_graphs()[source]#
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)
>>> from sage.all import * >>> chang_graphs = graphs.chang_graphs() >>> K8 = graphs.CompleteGraph(Integer(8)) >>> T8 = K8.line_graph() >>> four_srg = chang_graphs + [T8] >>> 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) >>> from itertools import combinations >>> for g1,g2 in combinations(four_srg,Integer(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]
>>> from sage.all import * >>> c3c5 = graphs.CycleGraph(Integer(3)).disjoint_union(graphs.CycleGraph(Integer(5))) >>> c8 = graphs.CycleGraph(Integer(8)) >>> s = [K8.subgraph_search(c8).edges(sort=False), # needs sage.modules ... [(Integer(0),Integer(1),None),(Integer(2),Integer(3),None),(Integer(4),Integer(5),None),(Integer(6),Integer(7),None)], ... K8.subgraph_search(c3c5).edges(sort=False)] >>> [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()[source]#
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]
>>> from sage.all import * >>> 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)[source]#
Return a generator which creates non-isomorphic trees from nauty’s gentreeg program.
INPUT:
options– string (default:""); a string passed togentreegas 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); ifTruethe first line ofgentreeg’s output to standard error is captured and the first call to the generator’snext()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
gentreegto 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 treesEXAMPLES:
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
>>> from sage.all import * >>> gen = graphs.nauty_gentreeg("4") >>> next(gen) Graph on 4 vertices >>> next(gen) Graph on 4 vertices >>> 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]
>>> from sage.all import * >>> [len(list(graphs.nauty_gentreeg(str(i)))) for i in range(Integer(1), Integer(15))] [1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159]
The
debugswitch can be used to examinegentreeg’s reaction to the input in theoptionsstring. We illustrate success. (A failure will be a string beginning with “>E”.) Passing the “-q” switch togentreegwill suppress the indicator of a successful initiation, and so the first returned value might be an empty string ifdebugisTrue: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) ''
>>> from sage.all import * >>> gen = graphs.nauty_gentreeg("4", debug=True) >>> print(next(gen)) >A ...gentreeg ... >>> gen = graphs.nauty_gentreeg("4 -q", debug=True) >>> next(gen) ''
- sage.graphs.generators.families.petersen_family(generate=False)[source]#
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 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]
>>> from sage.all import * >>> 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
>>> from sage.all import * >>> F1 = graphs.petersen_family(generate=False) >>> F2 = graphs.petersen_family(generate=True) # needs sage.modules >>> F1 = [g.canonical_label().graph6_string() for g in F1] >>> F2 = [g.canonical_label().graph6_string() for g in F2] # needs sage.modules >>> set(F1) == set(F2) # needs sage.modules True
- sage.graphs.generators.families.trees(vertices)[source]#
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
verticesnumber 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.treesmodule, 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]
>>> from sage.all import * >>> tree_iterator = graphs.trees(Integer(7)) >>> 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]
>>> from sage.all import * >>> [len(list(graphs.trees(i))) for i in range(Integer(0), Integer(15))] [1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159]