A collection of constructors of common graphs.¶

USE:

To see a list of all graph constructors, type “graphs.” and then press the tab key. The documentation for each constructor includes information about each graph, which provides a useful reference.

PLOTTING:

All graphs (i.e., networks) have an associated Sage graphics object, which you can display:

sage: G = graphs.WheelGraph(15)
sage: P = G.plot()
sage: P.show() # long time

If you create a graph in Sage using the Graph command, then plot that graph, the positioning of nodes is determined using the spring-layout algorithm. For the special graph constructors, which you get using graphs.[tab], the positions are preset. For example, consider the Petersen graph with default node positioning vs. the Petersen graph constructed by this database:

sage: petersen_spring = Graph({0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[0,3,9], 5:[0,7,8], 6:[1,8,9], 7:[2,5,9], 8:[3,5,6], 9:[4,6,7]})
sage: petersen_spring.show() # long time
sage: petersen_database = graphs.PetersenGraph()
sage: petersen_database.show() # long time

For all the constructors in this database (except the octahedral, dodecahedral, random and empty graphs), the position dictionary is filled in, instead of using the spring-layout algorithm.

For further visual examples and explanation, see the docstrings below, particularly for CycleGraph, StarGraph, WheelGraph, CompleteGraph and CompleteBipartiteGraph.

ORGANIZATION:

The constructors available in this database are organized as follows:

Basic Structures:
    - BarbellGraph
    - BullGraph
    - CircularLadderGraph
    - ClawGraph
    - CycleGraph
    - Circuit
    - DiamondGraph
    - EmptyGraph
    - Grid2dGraph
    - GridGraph
    - HouseGraph
    - HouseXGraph
    - KrackhardtKiteGraph
    - LadderGraph
    - LollipopGraph
    - PathGraph
    - StarGraph
    - ToroidalGrid2dGraph
    - WheelGraph
Platonic Solids:
    - TetrahedralGraph
    - HexahedralGraph
    - OctahedralGraph
    - IcosahedralGraph
    - DodecahedralGraph
Named Graphs:
    - ChvatalGraph
    - DesarguesGraph
    - FlowerSnark
    - FruchtGraph
    - HeawoodGraph
    - HigmanSimsGraph
    - HoffmanSingletonGraph
    - MoebiusKantorGraph
    - Pappus Graph
    - PetersenGraph
    - ThomsenGraph
Families of Graphs:
    - BalancedTree
    - BubbleSortGraph
    - CirculantGraph
    - CompleteGraph
    - CompleteBipartiteGraph
    - CompleteMultipartiteGraph
    - CubeGraph
    - FibonacciTree
    - FuzzyBallGraph
    - GeneralizedPetersenGraph
    - HyperStarGraph
    - KneserGraph
    - LCFGraph
    - NKStarGraph
    - NStarGraph
    - OddGraph
Pseudofractal Graphs:
    - DorogovtsevGoltsevMendesGraph
Random Graphs:
    - RandomGNP
    - RandomBarabasiAlbert
    - RandomBipartite
    - RandomGNM
    - RandomNewmanWattsStrogatz
    - RandomHolmeKim
    - RandomInterval
    - RandomLobster
    - RandomTreePowerlaw
    - RandomRegular
    - RandomShell
Random Directed Graphs:
    - RandomDirectedGN
    - RandomDirectedGNC
    - RandomDirectedGNR
Graphs with a given degree sequence:
    - DegreeSequence
    - DegreeSequenceBipartite
    - DegreeSequenceConfigurationModel
    - DegreeSequenceTree
    - DegreeSequenceExpected
Oddities :
    - WorldMap

AUTHORS:

Robert Miller (2006-11-05): initial version, empty, random, petersen
Emily Kirkman (2006-11-12): basic structures, node positioning for all constructors
Emily Kirkman (2006-11-19): docstrings, examples
William Stein (2006-12-05): Editing.
Robert Miller (2007-01-16): Cube generation and plotting
Emily Kirkman (2007-01-16): more basic structures, docstrings
Emily Kirkman (2007-02-14): added more named graphs
Robert Miller (2007-06-08-11): Platonic solids, random graphs, graphs with a given degree sequence, random directed graphs
Robert Miller (2007-10-24): Isomorph free exhaustive generation
Nathann Cohen (2009-08-12): WorldMap
Michael Yurko (2009-9-01): added hyperstar, (n,k)-star, n-star, and bubblesort graphs
Anders Jonsson (2009-10-15): added generalized Petersen graphs
Harald Schilly and Yann Laigle-Chapuy (2010-03-24): added Fibonacci Tree

class sage.graphs.graph_generators.GraphGenerators¶

A class consisting of constructors for several common graphs, as well as orderly generation of isomorphism class representatives.

A list of all graphs and graph structures (other than iso. class rep’s) in this database is available via tab completion. Type “graphs.” and then hit tab to see which graphs are available.

The docstrings include educational information about each named graph with the hopes that this class can be used as a reference.

For all the constructors in this class (except the octahedral, dodecahedral, random and empty graphs), the position dictionary is filled to override the spring-layout algorithm.

The constructors currently in this class include:

Basic Structures:
    - BarbellGraph
    - BullGraph
    - CircularLadderGraph
    - ClawGraph
    - CycleGraph
    - Circuit
    - DiamondGraph
    - EmptyGraph
    - Grid2dGraph
    - GridGraph
    - HouseGraph
    - HouseXGraph
    - KrackhardtKiteGraph
    - LadderGraph
    - LollipopGraph
    - PathGraph
    - StarGraph
    - ToroidalGrid2dGraph
    - WheelGraph
Platonic Solids:
    - TetrahedralGraph
    - HexahedralGraph
    - OctahedralGraph
    - IcosahedralGraph
    - DodecahedralGraph
Named Graphs:
    - ChvatalGraph
    - DesarguesGraph
    - FlowerSnark
    - FruchtGraph
    - HeawoodGraph
    - HigmanSimsGraph
    - HoffmanSingletonGraph
    - MoebiusKantorGraph
    - PappusGraph
    - PetersenGraph
    - ThomsenGraph
Families of Graphs:
    - BalancedTree
    - CirculantGraph
    - CompleteGraph
    - CompleteBipartiteGraph
    - CompleteMultipartiteGraph
    - CubeGraph
    - FuzzyBallGraph
    - FibonacciTree
    - KneserGraph
    - LCFGraph
    - OddGraph
Pseudofractal Graphs:
    - DorogovtsevGoltsevMendesGraph
Random Graphs:
    - RandomGNP
    - RandomBarabasiAlbert
    - RandomBipartite
    - RandomGNM
    - RandomNewmanWattsStrogatz
    - RandomHolmeKim
    - RandomInterval
    - RandomLobster
    - RandomTreePowerlaw
    - RandomRegular
    - RandomShell
Graphs with a given degree sequence:
    - DegreeSequence
    - DegreeSequenceBipartite
    - DegreeSequenceConfigurationModel
    - DegreeSequenceTree
    - DegreeSequenceExpected
Oddities :
    - WorldMap

ORDERLY GENERATION: graphs(vertices, property=lambda x: True, augment=’edges’, size=None)

This syntax accesses the generator of isomorphism class representatives. Iterates over distinct, exhaustive representatives.

INPUT:

vertices - natural number
property - any property to be tested on graphs before generation. (Ignored if deg_seq is specified.)
augment - choices:
'vertices' - augments by adding a vertex, and edges incident to that vertex. In this case, all graphs on up to n=vertices are generated. If for any graph G satisfying the property, every subgraph, obtained from G by deleting one vertex and only edges incident to that vertex, satisfies the property, then this will generate all graphs with that property. If this does not hold, then all the graphs generated will satisfy the property, but there will be some missing.
'edges' - augments a fixed number of vertices by adding one edge In this case, all graphs on exactly n=vertices are generated. If for any graph G satisfying the property, every subgraph, obtained from G by deleting one edge but not the vertices incident to that edge, satisfies the property, then this will generate all graphs with that property. If this does not hold, then all the graphs generated will satisfy the property, but there will be some missing.
deg_seq - a sequence of non-negative integers, or None. If specified, the generated graphs will have these integers for degrees. In this case property and size are both ignored.
loops - whether to allow loops in the graph or not.
implementation - which underlying implementation to use (see Graph?)
sparse - ignored if implementation is not c_graph

EXAMPLES: Print graphs on 3 or less vertices.

sage: for G in graphs(3, augment='vertices'):
...    print G
Graph on 0 vertices
Graph on 1 vertex
Graph on 2 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 2 vertices
Graph on 3 vertices

Note that we can also get graphs with underlying Cython implementation:

sage: for G in graphs(3, augment='vertices', implementation='c_graph'):
...    print G
Graph on 0 vertices
Graph on 1 vertex
Graph on 2 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 2 vertices
Graph on 3 vertices

Print graphs on 3 vertices.

sage: for G in graphs(3):
...    print G
Graph on 3 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 3 vertices

Generate all graphs with 5 vertices and 4 edges.

sage: L = graphs(5, size=4)
sage: len(list(L))
6

Generate all graphs with 5 vertices and up to 4 edges.

sage: L = list(graphs(5, lambda G: G.size() <= 4))
sage: len(L)
14
sage: graphs_list.show_graphs(L) # long time

Generate all graphs with up to 5 vertices and up to 4 edges.

sage: L = list(graphs(5, lambda G: G.size() <= 4, augment='vertices'))
sage: len(L)
31
sage: graphs_list.show_graphs(L)              # long time

Generate all graphs with degree at most 2, up to 6 vertices.

sage: property = lambda G: ( max([G.degree(v) for v in G] + [0]) <= 2 )
sage: L = list(graphs(6, property, augment='vertices'))
sage: len(L)
45

Generate all bipartite graphs on up to 7 vertices: (see http://www.research.att.com/~njas/sequences/A033995)

sage: L = list( graphs(7, lambda G: G.is_bipartite(), augment='vertices') )
sage: [len([g for g in L if g.order() == i]) for i in [1..7]]
[1, 2, 3, 7, 13, 35, 88]

Generate all bipartite graphs on exactly 7 vertices:

sage: L = list( graphs(7, lambda G: G.is_bipartite()) )
sage: len(L)
88

Generate all bipartite graphs on exactly 8 vertices:

sage: L = list( graphs(8, lambda G: G.is_bipartite()) ) # long time
sage: len(L)                                            # long time
303

Generate graphs on the fly: (see http://www.research.att.com/~njas/sequences/A000088)

sage: for i in range(0, 7):
...    print len(list(graphs(i)))
1
1
2
4
11
34
156

Generate all simple graphs, allowing loops: (see http://www.research.att.com/~njas/sequences/A000666)

sage: L = list(graphs(5,augment='vertices',loops=True))               # long time
sage: for i in [0..5]: print i, len([g for g in L if g.order() == i]) # long time
1
2
6
20
90
544

Generate all graphs with a specified degree sequence: (see http://www.research.att.com/~njas/sequences/A002851)

sage: for i in [4,6,8]:
...    print i, len([g for g in graphs(i,deg_seq=[3]*i) if g.is_connected()])
4 1
6 2
8 5
sage: for i in [4,6,8]:                                                                          # long time
...    print i, len([g for g in graphs(i,augment='vertices',deg_seq=[3]*i) if g.is_connected()]) # long time
4 1
6 2
8 5

sage: print 10, len([g for g in graphs(10,deg_seq=[3]*10) if g.is_connected()]) # not tested
10 19

REFERENCE:

Brendan D. McKay, Isomorph-Free Exhaustive generation. Journal of Algorithms Volume 26, Issue 2, February 1998, pages 306-324.

BalancedTree(r, h)¶

Returns the perfectly balanced tree of height $h \geq 1$ , whose root has degree $r \geq 2$ .

The number of vertices of this graph is $1 + r + r^2 + \cdots + r^h$ , that is, $\frac{r^{h+1} - 1}{r - 1}$ . The number of edges is one less than the number of vertices.

EXAMPLE: Plot a balanced tree of height 4 with r = 3

sage: G = graphs.BalancedTree(3, 5)
sage: G.show()   # long time

BarbellGraph(n1, n2)¶

Returns a barbell graph with 2*n1 + n2 nodes. n1 must be greater than or equal to 2.

A barbell graph is a basic structure that consists of a path graph of order n2 connecting two complete graphs of order n1 each.

This constructor depends on NetworkX numeric labels. In this case, the (n1)th node connects to the path graph from one complete graph and the (n1+n2+1)th node connects to the path graph from the other complete graph.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each barbell graph will be displayed with the two complete graphs in the lower-left and upper-right corners, with the path graph connecting diagonally between the two. Thus the (n1)th node will be drawn at a 45 degree angle from the horizontal right center of the first complete graph, and the (n1+n2+1)th node will be drawn 45 degrees below the left horizontal center of the second complete graph.

EXAMPLES: Construct and show a barbell graph Bar = 4, Bells = 9

sage: g = graphs.BarbellGraph(9,4)
sage: g.show() # long time

Create several barbell graphs in a Sage graphics array

sage: g = []
sage: j = []
sage: for i in range(6):
...    k = graphs.BarbellGraph(i+2,4)
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

BubbleSortGraph(n)¶

Returns the bubble sort graph, B(n).

The vertices of the bubble sort graph are the set of permutations on n symbols. Two vertices are adjacent if one can be obtained from the other by swapping the labels in the ith and (i+1)th position for $1 \leq i \leq n-1$ .

INPUT:

n

EXAMPLES:

sage: g = graphs.BubbleSortGraph(4)
sage: g.plot() # long time

AUTHORS:

Michael Yurko (2009-09-01)

BullGraph()¶

Returns a bull graph with 5 nodes.

A bull graph is named for its shape. It’s a triangle with horns.

This constructor depends on NetworkX numeric labeling.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the bull graph is drawn as a triangle with the first node (0) on the bottom. The second and third nodes (1 and 2) complete the triangle. Node 3 is the horn connected to 1 and node 4 is the horn connected to node 2.

EXAMPLES: Construct and show a bull graph

sage: g = graphs.BullGraph()
sage: g.show() # long time

ChvatalGraph()¶

Returns the Chvatal graph.

The Chvatal graph has 12 vertices. It is a 4-regular, 4-chromatic graph. It is one of the few known graphs to satisfy Grunbaum’s conjecture that for every m 1, n 2, there is an m-regular, m-chromatic graph of girth at least n.

EXAMPLE:

sage: G = graphs.ChvatalGraph()
sage: G.degree()
[4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4]

CirculantGraph(n, adjacency)¶

Returns a circulant graph with n nodes.

A circulant graph has the property that the vertex i is connected with the vertices i+j and i-j for each j in adj.

INPUT:

n - number of vertices in the graph
adjacency - the list of j values

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each circulant graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.

Filling the position dictionary in advance adds O(n) to the constructor.

EXAMPLES: Compare plotting using the predefined layout and networkx:

sage: import networkx            
sage: n = networkx.cycle_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.CirculantGraph(23,2)
sage: spring23.show() # long time
sage: posdict23.show() # long time

We next view many cycle graphs as a Sage graphics array. First we use the CirculantGraph constructor, which fills in the position dictionary:

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.CirculantGraph(i+3,i)
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

Compare to plotting with the spring-layout algorithm:

sage: g = []
sage: j = []
sage: for i in range(9):
...    spr = networkx.cycle_graph(i+3)       
...    k = Graph(spr)
...    g.append(k)
...
sage: for i in range(3):
...    n = []
...    for m in range(3):
...        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
...    j.append(n)
...
sage: G = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

Passing a 1 into adjacency should give the cycle.

sage: graphs.CirculantGraph(6,1)==graphs.CycleGraph(6)
True
sage: graphs.CirculantGraph(7,[1,3]).edges(labels=false)
[(0, 1),
(0, 3),
(0, 4),
(0, 6),
(1, 2),
(1, 4),
(1, 5),
(2, 3),
(2, 5),
(2, 6),
(3, 4),
(3, 6),
(4, 5),
(5, 6)]

CircularLadderGraph(n)¶

Returns a circular ladder graph with 2*n nodes.

A Circular ladder graph is a ladder graph that is connected at the ends, i.e.: a ladder bent around so that top meets bottom. Thus it can be described as two parallel cycle graphs connected at each corresponding node pair.

This constructor depends on NetworkX numeric labels.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the circular ladder graph is displayed as an inner and outer cycle pair, with the first n nodes drawn on the inner circle. The first (0) node is drawn at the top of the inner-circle, moving clockwise after that. The outer circle is drawn with the (n+1)th node at the top, then counterclockwise as well.

EXAMPLES: Construct and show a circular ladder graph with 26 nodes

sage: g = graphs.CircularLadderGraph(13)
sage: g.show() # long time

Create several circular ladder graphs in a Sage graphics array

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.CircularLadderGraph(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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

ClawGraph()¶

Returns a claw graph.

A claw graph is named for its shape. It is actually a complete bipartite graph with (n1, n2) = (1, 3).

PLOTTING: See CompleteBipartiteGraph.

EXAMPLES: Show a Claw graph

sage: (graphs.ClawGraph()).show() # long time

Inspect a Claw graph

sage: G = graphs.ClawGraph()
sage: G
Claw graph: Graph on 4 vertices

CompleteBipartiteGraph(n1, n2)¶

Returns a Complete Bipartite Graph sized n1+n2, with each of the nodes [0,(n1-1)] connected to each of the nodes [n1,(n2-1)] and vice versa.

A Complete Bipartite Graph is a graph with its vertices partitioned into two groups, V1 and V2. Each v in V1 is connected to every v in V2, and vice versa.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each complete bipartite graph will be displayed with the first n1 nodes on the top row (at y=1) from left to right. The remaining n2 nodes appear at y=0, also from left to right. The shorter row (partition with fewer nodes) is stretched to the same length as the longer row, unless the shorter row has 1 node; in which case it is centered. The x values in the plot are in domain [0,maxn1,n2].

In the Complete Bipartite graph, there is a visual difference in using the spring-layout algorithm vs. the position dictionary used in this constructor. The position dictionary flattens the graph and separates the partitioned nodes, making it clear which nodes an edge is connected to. The Complete Bipartite graph plotted with the spring-layout algorithm tends to center the nodes in n1 (see spring_med in examples below), thus overlapping its nodes and edges, making it typically hard to decipher.

Filling the position dictionary in advance adds O(n) to the constructor. Feel free to race the constructors below in the examples section. The much larger difference is the time added by the spring-layout algorithm when plotting. (Also shown in the example below). The spring model is typically described as $O(n^3)$ , as appears to be the case in the NetworkX source code.

EXAMPLES: Two ways of constructing the complete bipartite graph, using different layout algorithms:

sage: import networkx        
sage: n = networkx.complete_bipartite_graph(389,157); spring_big = Graph(n)   # long time
sage: posdict_big = graphs.CompleteBipartiteGraph(389,157)                    # long time

Compare the plotting:

sage: n = networkx.complete_bipartite_graph(11,17)
sage: spring_med = Graph(n)
sage: posdict_med = graphs.CompleteBipartiteGraph(11,17)

Notice here how the spring-layout tends to center the nodes of n1

sage: spring_med.show() # long time
sage: posdict_med.show() # long time

View many complete bipartite graphs with a Sage Graphics Array, with this constructor (i.e., the position dictionary filled):

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.CompleteBipartiteGraph(i+1,4)
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

We compare to plotting with the spring-layout algorithm:

sage: g = []
sage: j = []
sage: for i in range(9):
...    spr = networkx.complete_bipartite_graph(i+1,4)       
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

CompleteGraph(n)¶

Returns a complete graph on n nodes.

A Complete Graph is a graph in which all nodes are connected to all other nodes.

This constructor is dependent on vertices numbered 0 through n-1 in NetworkX complete_graph()

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each complete graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.

In the complete graph, there is a big difference visually in using the spring-layout algorithm vs. the position dictionary used in this constructor. The position dictionary flattens the graph, making it clear which nodes an edge is connected to. But the complete graph offers a good example of how the spring-layout works. The edges push outward (everything is connected), causing the graph to appear as a 3-dimensional pointy ball. (See examples below).

EXAMPLES: We view many Complete graphs with a Sage Graphics Array, first with this constructor (i.e., the position dictionary filled):

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.CompleteGraph(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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

We compare to plotting with the spring-layout algorithm:

sage: import networkx        
sage: g = []
sage: j = []
sage: for i in range(9):
...    spr = networkx.complete_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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

Compare the constructors (results will vary)

sage: import networkx                
sage: t = cputime()
sage: n = networkx.complete_graph(389); spring389 = Graph(n)
sage: cputime(t)           # random
0.59203700000000126
sage: t = cputime()
sage: posdict389 = graphs.CompleteGraph(389)
sage: cputime(t)           # random
0.6680419999999998

We compare plotting:

sage: import networkx        
sage: n = networkx.complete_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.CompleteGraph(23)
sage: spring23.show() # long time
sage: posdict23.show() # long time

CompleteMultipartiteGraph(l)¶

Returns a complete multipartite graph.

INPUT:

l – a list of integers : the respective sizes of the components.

EXAMPLE:

A complete tripartite graph with sets of sizes $5, 6, 8$ :

sage: g = graphs.CompleteMultipartiteGraph([5, 6, 8]); g
Multipartite Graph with set sizes [5, 6, 8]: Graph on 19 vertices

It clearly has a chromatic number of 3:

sage: g.chromatic_number()
3

CubeGraph(n)¶

Returns the hypercube in $n$ dimensions.

The hypercube in $n$ dimension is build upon the binary strings on $n$ bits, two of them being adjacent if they differ in exactly one bit. Hence, the distance between two vertices in the hypercube is the Hamming distance.

EXAMPLES:

The distance between $0100110$ and $1011010$ is $5$ , as expected

sage: g = graphs.CubeGraph(7)
sage: g.distance('0100110','1011010')
5

Plot several $n$ -cubes in a Sage Graphics Array

sage: g = []
sage: j = []
sage: for i in range(6):
...    k = graphs.CubeGraph(i+1)
...    g.append(k)
...
sage: for i in range(2):
...    n = []
...    for m in range(3):
...        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
...    j.append(n)
...
sage: G = sage.plot.plot.GraphicsArray(j)
sage: G.show(figsize=[6,4]) # long time

Use the plot options to display larger $n$ -cubes

sage: g = graphs.CubeGraph(9)
sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20) # long time

AUTHORS:

Robert Miller

CycleGraph(n)¶

Returns a cycle graph with n nodes.

A cycle graph is a basic structure which is also typically called an n-gon.

This constructor is dependent on vertices numbered 0 through n-1 in NetworkX cycle_graph()

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each cycle graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.

The cycle graph is a good opportunity to compare efficiency of filling a position dictionary vs. using the spring-layout algorithm for plotting. Because the cycle graph is very symmetric, the resulting plots should be similar (in cases of small n).

Filling the position dictionary in advance adds O(n) to the constructor.

EXAMPLES: Compare plotting using the predefined layout and networkx:

sage: import networkx            
sage: n = networkx.cycle_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.CycleGraph(23)
sage: spring23.show() # long time
sage: posdict23.show() # long time

We next view many cycle graphs as a Sage graphics array. First we use the CycleGraph constructor, which fills in the position dictionary:

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.CycleGraph(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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

Compare to plotting with the spring-layout algorithm:

sage: g = []
sage: j = []
sage: for i in range(9):
...    spr = networkx.cycle_graph(i+3)       
...    k = Graph(spr)
...    g.append(k)
...
sage: for i in range(3):
...    n = []
...    for m in range(3):
...        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
...    j.append(n)
...
sage: G = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

DegreeSequence(deg_sequence)¶

Returns a graph with the given degree sequence. Raises a NetworkX error if the proposed degree sequence cannot be that of a graph.

Graph returned is the one returned by the Havel-Hakimi algorithm, which constructs a simple graph by connecting vertices of highest degree to other vertices of highest degree, resorting the remaining vertices by degree and repeating the process. See Theorem 1.4 in [1].

INPUT:

deg_sequence - a list of integers with each entry corresponding to the degree of a different vertex.

EXAMPLES:

sage: G = graphs.DegreeSequence([3,3,3,3])
sage: G.edges(labels=False)
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
sage: G.show()  # long time

sage: G = graphs.DegreeSequence([3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3])
sage: G.show()  # long time

sage: G = graphs.DegreeSequence([4,4,4,4,4,4,4,4])
sage: G.show()  # long time

sage: G = graphs.DegreeSequence([1,2,3,4,3,4,3,2,3,2,1])
sage: G.show()  # long time

REFERENCE:

[1] Chartrand, G. and Lesniak, L. Graphs and Digraphs. Chapman and Hall/CRC, 1996.

DegreeSequenceBipartite(s1, s2)¶

Returns a bipartite graph whose two sets have the given degree sequences.

Given two different sequences of degrees $s_1$ and $s_2$ , this functions returns ( if possible ) a bipartite graph on sets $A$ and $B$ such that the vertices in $A$ have $s_1$ as their degree sequence, while $s_2$ is the degree sequence of the vertices in $B$ .

INPUT:

s_1 – list of integers corresponding to the degree sequence of the first set.
s_2 – list of integers corresponding to the degree sequence of the seccond set.

ALGORITHM:

This function works through the computation of the matrix given by the Gale-Ryser theorem, which is in this case the adjacency matrix of the bipartite graph.

EXAMPLES:

If we are given as sequences [2,2,2,2,2] and [5,5] we are given as expected the complete bipartite graph $K_{2,5}$

sage: g = graphs.DegreeSequenceBipartite([2,2,2,2,2],[5,5])
sage: g.is_isomorphic(graphs.CompleteBipartiteGraph(5,2))
True

Some sequences being uncompatible if, for example, their sums are different, the functions raises a ValueError when no graph corresponding to the degree sequences exists.

sage: g = graphs.DegreeSequenceBipartite([2,2,2,2,1],[5,5])
...
ValueError: There exists no bipartite graph corresponding to the given degree sequences

DegreeSequenceConfigurationModel(deg_sequence, seed=None)¶

Returns a random pseudograph with the given degree sequence. Raises a NetworkX error if the proposed degree sequence cannot be that of a graph with multiple edges and loops.

One requirement is that the sum of the degrees must be even, since every edge must be incident with two vertices.

INPUT:

deg_sequence - a list of integers with each entry corresponding to the expected degree of a different vertex.
seed - for the random number generator.

EXAMPLES:

sage: G = graphs.DegreeSequenceConfigurationModel([1,1])
sage: G.adjacency_matrix()
[0 1]
[1 0]

Note: as of this writing, plotting of loops and multiple edges is not supported, and the output is allowed to contain both types of edges.

sage: G = graphs.DegreeSequenceConfigurationModel([3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3])
sage: G.edges(labels=False)
[(0, 2), (0, 10), (0, 15), (1, 6), (1, 16), (1, 17), (2, 5), (2, 19), (3, 7), (3, 14), (3, 14), (4, 9), (4, 13), (4, 19), (5, 6), (5, 15), (6, 11), (7, 11), (7, 17), (8, 11), (8, 18), (8, 19), (9, 12), (9, 13), (10, 15), (10, 18), (12, 13), (12, 16), (14, 17), (16, 18)]
sage: G.show()  # long time

REFERENCE:

[1] Newman, M.E.J. The Structure and function of complex networks, SIAM Review vol. 45, no. 2 (2003), pp. 167-256.

DegreeSequenceExpected(deg_sequence, seed=None)¶

Returns a random graph with expected given degree sequence. Raises a NetworkX error if the proposed degree sequence cannot be that of a graph.

One requirement is that the sum of the degrees must be even, since every edge must be incident with two vertices.

INPUT:

deg_sequence - a list of integers with each entry corresponding to the expected degree of a different vertex.
seed - for the random number generator.

EXAMPLE:

sage: G = graphs.DegreeSequenceExpected([1,2,3,2,3])
sage: G.edges(labels=False)
[(0, 2), (1, 1), (1, 3), (2, 2), (2, 4), (3, 3)]
sage: G.show()  # long time

REFERENCE:

[1] Chung, Fan and Lu, L. Connected components in random graphs with given expected degree sequences. Ann. Combinatorics (6), 2002 pp. 125-145.

DegreeSequenceTree(deg_sequence)¶

Returns a tree with the given degree sequence. Raises a NetworkX error if the proposed degree sequence cannot be that of a tree.

Since every tree has one more vertex than edge, the degree sequence must satisfy len(deg_sequence) - sum(deg_sequence)/2 == 1.

INPUT:

deg_sequence - a list of integers with each entry corresponding to the expected degree of a different vertex.

EXAMPLE:

sage: G = graphs.DegreeSequenceTree([3,1,3,3,1,1,1,2,1])
sage: G.show()  # long time

DesarguesGraph()¶

Returns the Desargues graph.

PLOTTING: The layout chosen is the same as on the cover of [1].

EXAMPLE:

sage: D = graphs.DesarguesGraph()
sage: L = graphs.LCFGraph(20,[5,-5,9,-9],5)
sage: D.is_isomorphic(L)
True
sage: D.show()  # long time

REFERENCE:

[1] Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

DiamondGraph()¶

Returns a diamond graph with 4 nodes.

A diamond graph is a square with one pair of diagonal nodes connected.

This constructor depends on NetworkX numeric labeling.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the diamond graph is drawn as a diamond, with the first node on top, second on the left, third on the right, and fourth on the bottom; with the second and third node connected.

EXAMPLES: Construct and show a diamond graph

sage: g = graphs.DiamondGraph()
sage: g.show() # long time

DodecahedralGraph()¶

Returns a Dodecahedral graph (with 20 nodes)

The dodecahedral graph is cubic symmetric, so the spring-layout algorithm will be very effective for display. It is dual to the icosahedral graph.

PLOTTING: The Dodecahedral graph should be viewed in 3 dimensions. We chose to use the default spring-layout algorithm here, so that multiple iterations might yield a different point of reference for the user. We hope to add rotatable, 3-dimensional viewing in the future. In such a case, a string argument will be added to select the flat spring-layout over a future implementation.

EXAMPLES: Construct and show a Dodecahedral graph

sage: g = graphs.DodecahedralGraph()
sage: g.show() # long time

Create several dodecahedral graphs in a Sage graphics array They will be drawn differently due to the use of the spring-layout algorithm

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.DodecahedralGraph()
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

DorogovtsevGoltsevMendesGraph(n)¶

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

EXAMPLE:

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

REFERENCE:

[1] Dorogovtsev, S. N., Goltsev, A. V., and Mendes, J. F. F., Pseudofractal scale-free web, Phys. Rev. E 066122 (2002).

EmptyGraph()¶

Returns an empty graph (0 nodes and 0 edges).

This is useful for constructing graphs by adding edges and vertices individually or in a loop.

PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.

EXAMPLES: Add one vertex to an empty graph and then show:

sage: empty1 = graphs.EmptyGraph()
sage: empty1.add_vertex()
sage: empty1.show() # long time

Use for loops to build a graph from an empty graph:

sage: empty2 = graphs.EmptyGraph()
sage: for i in range(5):
...    empty2.add_vertex() # add 5 nodes, labeled 0-4
...
sage: for i in range(3):
...    empty2.add_edge(i,i+1) # add edges {[0:1],[1:2],[2:3]}
...
sage: for i in range(4)[1:]:
...    empty2.add_edge(4,i) # add edges {[1:4],[2:4],[3:4]}
...
sage: empty2.show() # long time

FibonacciTree(n)¶

Returns the graph of the Fibonacci Tree $F_{i}$ of order $n$ . $F_{i}$ is recursively defined as the a 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) sage: g.is_tree() True sage: l1 = [ len(graphs.FibonacciTree(_)) + 1 for _ in range(6) ] sage: l2 = list(fibonacci_sequence(2,8)) sage: l1 == l2 True

AUTHORS:

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

FlowerSnark()¶

Returns a Flower Snark.

A flower snark has 20 vertices. It is part of the class of biconnected cubic graphs with edge chromatic number = 4, known as snarks. (i.e.: the Petersen graph). All snarks are not Hamiltonian, non-planar and have Petersen graph graph minors.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the nodes are drawn 0-14 on the outer circle, and 15-19 in an inner pentagon.

REFERENCES:

[1] Weisstein, E. (1999). “Flower Snark - from Wolfram MathWorld”. [Online] Available: http://mathworld.wolfram.com/FlowerSnark.html [2007, February 17]

EXAMPLES: Inspect a flower snark:

sage: F = graphs.FlowerSnark()
sage: F
Flower Snark: Graph on 20 vertices
sage: F.graph6_string()
'ShCGHC@?GGg@?@?Gp?K??C?CA?G?_G?Cc'

Now show it:

sage: F.show() # long time

FruchtGraph()¶

Returns a Frucht Graph.

A Frucht graph has 12 nodes and 18 edges. It is the smallest cubic identity graph. It is planar and it is Hamiltonian.

This constructor is dependent on NetworkX’s numeric labeling.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the first seven nodes are on the outer circle, with the next four on an inner circle and the last in the center.

REFERENCES:

[1] Weisstein, E. (1999). “Frucht Graph - from Wolfram MathWorld”. [Online] Available: http://mathworld.wolfram.com/FruchtGraph.html [2007, February 17]

EXAMPLES:

sage: FRUCHT = graphs.FruchtGraph()
sage: FRUCHT
Frucht graph: Graph on 12 vertices
sage: FRUCHT.graph6_string()
'KhCKM?_EGK?L'
sage: (graphs.FruchtGraph()).show() # long time

FuzzyBallGraph(partition, q)¶

Construct a Fuzzy Ball graph with the integer partition partition and q extra vertices.

Let $q$ be an integer and let $m_1,m_2,...,m_k$ be a set of positive integers. Let $n=q+m_1+...+m_k$ . The Fuzzy Ball graph with partition $m_1,m_2,...,m_k$ and $q$ extra vertices is the graph constructed from the graph $G=K_n$ by attaching, for each $i=1,2,...,k$ , a new vertex $a_i$ to $m_i$ distinct vertices of $G$ .

For given positive integers $k$ and $m$ and nonnegative integer $q$ , the set of graphs FuzzyBallGraph(p, q) for all partitions $p$ of $m$ with $k$ parts are cospectral with respect to the normalized Laplacian.

EXAMPLES:

sage: graphs.FuzzyBallGraph([3,1],2).adjacency_matrix()
[0 1 1 1 1 1 1 0]
[1 0 1 1 1 1 1 0]
[1 1 0 1 1 1 1 0]
[1 1 1 0 1 1 0 1]
[1 1 1 1 0 1 0 0]
[1 1 1 1 1 0 0 0]
[1 1 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]    

Pick positive integers $m$ and $k$ and a nonnegative integer $q$ . All the FuzzyBallGraphs constructed from partitions of $m$ with $k$ parts should be cospectral with respect to the normalized Laplacian:

sage: m=4; q=2; k=2
sage: g_list=[graphs.FuzzyBallGraph(p,q) for p in Partitions(m, length=k)]
sage: charpolys=set([g.laplacian_matrix(normalized=True).charpoly() for g in g_list])
sage: charpolys
set([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])

GeneralizedPetersenGraph(n, k)¶

Returns a generalized Petersen graph with $2n$ nodes. The variables $n$ , $k$ are integers such that $n>2$ and $0<k\leq\lfloor(n-1)$ / $2\rfloor$

For $k=1$ the result is a graph isomorphic to the circular ladder graph with the same $n$ . The regular Petersen Graph has $n=5$ and $k=2$ . Other named graphs that can be described using this notation include the Desargues graph and the Moebius-Kantor graph.

INPUT:

n - the number of nodes is $2*n$ .
k - integer $0<k\leq\lfloor(n-1)$ / $2\rfloor$ . Decides how inner vertices are connected.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the generalized Petersen graphs are displayed as an inner and outer cycle pair, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outer-circle, moving counterclockwise after that. The inner circle is drawn with the (n)th node at the top, then counterclockwise as well.

EXAMPLES: For $k=1$ the resulting graph will be isomorphic to a circular ladder graph.

sage: g = graphs.GeneralizedPetersenGraph(13,1)
sage: g2 = graphs.CircularLadderGraph(13)
sage: g.is_isomorphic(g2)
True

The Desargues graph:

sage: g = graphs.GeneralizedPetersenGraph(10,3)
sage: g.girth()
6
sage: g.is_bipartite()
True

AUTHORS:

Anders Jonsson (2009-10-15)

Grid2dGraph(n1, n2)¶

Returns a $2$ -dimensional grid graph with $n_1n_2$ nodes ( $n_1$ rows and $n_2$ columns).

A 2d grid graph resembles a $2$ dimensional grid. All inner nodes are connected to their $4$ neighbors. Outer (non-corner) nodes are connected to their $3$ neighbors. Corner nodes are connected to their 2 neighbors.

This constructor depends on NetworkX numeric labels.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, nodes are labelled in (row, column) pairs with $(0, 0)$ in the top left corner. Edges will always be horizontal and vertical - another advantage of filling the position dictionary.

EXAMPLES: Construct and show a grid 2d graph Rows = $5$ , Columns = $7$

sage: g = graphs.Grid2dGraph(5,7)
sage: g.show() # long time

GridGraph(dim_list)¶

Returns an n-dimensional grid graph.

INPUT:

dim_list - a list of integers representing the number of nodes to extend in each dimension.

PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.

EXAMPLES:

sage: G = graphs.GridGraph([2,3,4])
sage: G.show()  # long time

sage: C = graphs.CubeGraph(4)
sage: G = graphs.GridGraph([2,2,2,2])
sage: C.show()  # long time
sage: G.show()  # long time

HanoiTowerGraph(pegs, disks, labels=True, positions=True)¶

Returns the graph whose vertices are the states of the Tower of Hanoi puzzle, with edges representing legal moves between states.

INPUT:

pegs - the number of pegs in the puzzle, 2 or greater
disks - the number of disks in the puzzle, 1 or greater
labels - default: True, if True the graph contains more meaningful labels, see explanation below. For large instances, turn off labels for much faster creation of the graph.
positions - default: True, if True the graph contains layout information. This creates a planar layout for the case of three pegs. For large instances, turn off layout information for much faster creation of the graph.

OUTPUT:

The Tower of Hanoi puzzle has a certain number of identical pegs and a certain number of disks, each of a different radius. Initially the disks are all on a single peg, arranged in order of their radii, with the largest on the bottom.

The goal of the puzzle is to move the disks to any other peg, arranged in the same order. The one constraint is that the disks resident on any one peg must always be arranged with larger radii lower down.

The vertices of this graph represent all the possible states of this puzzle. Each state of the puzzle is a tuple with length equal to the number of disks, ordered by largest disk first. The entry of the tuple is the peg where that disk resides. Since disks on a given peg must go down in size as we go up the peg, this totally describes the state of the puzzle.

For example (2,0,0) means the large disk is on peg 2, the medium disk is on peg 0, and the small disk is on peg 0 (and we know the small disk must be above the medium disk). We encode these tuples as integers with a base equal to the number of pegs, and low-order digits to the right.

Two vertices are adjacent if we can change the puzzle from one state to the other by moving a single disk. For example, (2,0,0) is adjacent to (2,0,1) since we can move the small disk off peg 0 and onto (the empty) peg 1. So the solution to a 3-disk puzzle (with at least two pegs) can be expressed by the shortest path between (0,0,0) and (1,1,1).

For 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 explicily as needed. The sage.rings.integer.Integer.digits() with the padsto option is a quick way to do this, though you may want to reverse the list that is output.

PLOTTING:

The layout computed when positions = True will look especially good for the three-peg case, when the graph is known to be planar. Except for two small cases on 4 pegs, the graph is otherwise not planar, and likely there is a better way to layout the vertices.

EXAMPLES:

A classic puzzle uses 3 pegs. We solve the 5 disk puzzle using integer labels and report the minimum number of moves required. Note that $3^5-1$ is the state where all 5 disks are on peg 2.

sage: H = graphs.HanoiTowerGraph(3, 5, labels=False, positions=False)
sage: H.distance(0, 3^5-1)
31

A slightly larger instance.

sage: H = graphs.HanoiTowerGraph(4, 6, labels=False, positions=False)
sage: H.num_verts()
4096
sage: H.distance(0, 4^6-1)
17

For a small graph, labels and layout information can be useful. Here we explicitly list a solution as a list of states.

sage: H = graphs.HanoiTowerGraph(3, 3, labels=True, positions=True)
sage: H.shortest_path((0,0,0), (1,1,1))
[(0, 0, 0), (0, 0, 1), (0, 2, 1), (0, 2, 2), (1, 2, 2), (1, 2, 0), (1, 1, 0), (1, 1, 1)]

Some facts about this graph with $p$ pegs and $d$ disks:

only automorphisms are the “obvious” ones - renumber the pegs.
chromatic number is less than or equal to $p$
independence number is $p^{d-1}$

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

TESTS:

It is an error to have just one peg (or less).

sage: graphs.HanoiTowerGraph(1, 5)
...
ValueError: Pegs for Tower of Hanoi graph should be two or greater (not 1)

It is an error to have zero disks (or less).

sage: graphs.HanoiTowerGraph(2, 0)
...
ValueError: Disks for Tower of Hanoi graph should be one or greater (not 0)

Citations

[ARETT-DOREE]

Danielle Arett and Su Doree, Coloring and counting on the tower of Hanoi graphs, Mathematics Magazine, to appear.

AUTHOR:

Rob Beezer, (2009-12-26), with assistance from Su Doree

HeawoodGraph()¶

Returns a Heawood graph.

The Heawood graph is a cage graph that has 14 nodes. It is a cubic symmetric graph. (See also the Moebius-Kantor graph). It is nonplanar and Hamiltonian. It has diameter = 3, radius = 3, girth = 6, chromatic number = 2. It is 4-transitive but not 5-transitive.

This constructor is dependent on NetworkX’s numeric labeling.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the nodes are positioned in a circular layout with the first node appearing at the top, and then continuing counterclockwise.

REFERENCES:

[1] Weisstein, E. (1999). “Heawood Graph - from Wolfram MathWorld”. [Online] Available: http://mathworld.wolfram.com/HeawoodGraph.html [2007, February 17]

EXAMPLES:

sage: H = graphs.HeawoodGraph()
sage: H
Heawood graph: Graph on 14 vertices
sage: H.graph6_string()
'MhEGHC@AI?_PC@_G_'
sage: (graphs.HeawoodGraph()).show() # long time

HexahedralGraph()¶

Returns a hexahedral graph (with 8 nodes).

A regular hexahedron is a 6-sided cube. The hexahedral graph corresponds to the connectivity of the vertices of the hexahedron. This graph is equivalent to a 3-cube.

PLOTTING: The hexahedral graph should be viewed in 3 dimensions. We chose to use the default spring-layout algorithm here, so that multiple iterations might yield a different point of reference for the user. We hope to add rotatable, 3-dimensional viewing in the future. In such a case, a string argument will be added to select the flat spring-layout over a future implementation.

EXAMPLES: Construct and show a Hexahedral graph

sage: g = graphs.HexahedralGraph()
sage: g.show() # long time

Create several hexahedral graphs in a Sage graphics array. They will be drawn differently due to the use of the spring-layout algorithm.

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.HexahedralGraph()
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

HigmanSimsGraph(relabel=True)¶

The Higman-Sims graph is a remarkable strongly regular graph of degree 22 on 100 vertices. For example, it can be split into two sets of 50 vertices each, so that each half induces a subgraph isomorphic to the Hoffman-Singleton graph (HoffmanSingletonGraph()). This can be done in 352 ways (see [BROUWER-HS-2009]).

Its most famous property is that the automorphism group has an index 2 subgroup which is one of the 26 sporadic groups. [HIGMAN1968]

The construction used here follows [HAFNER2004].

INPUT:

relabel - default: True. If True the vertices will be labeled with consecutive integers. If False the labels are strings that are three digits long. “xyz” means the vertex is in group x (zero through three), pentagon or pentagram y (zero through four), and is vertex z (zero through four) of that pentagon or pentagram. See [HAFNER2004] for more.

OUTPUT:

The Higman-Sims graph.

EXAMPLES:

A split into the first 50 and last 50 vertices will induce two copies of the Hoffman-Singleton graph, and we illustrate another such split, which is obvious based on the construction used.

sage: H = graphs.HigmanSimsGraph()
sage: A = H.subgraph(range(0,50))
sage: B = H.subgraph(range(50,100))
sage: K = graphs.HoffmanSingletonGraph()
sage: K.is_isomorphic(A) and K.is_isomorphic(B)
True
sage: C = H.subgraph(range(25,75))
sage: D = H.subgraph(range(0,25)+range(75,100))
sage: K.is_isomorphic(C) and K.is_isomorphic(D)
True

The automorphism group contains only one nontrivial proper normal subgroup, which is of index 2 and is simple. It is known as the Higman-Sims group.

sage: H = graphs.HigmanSimsGraph()
sage: G = H.automorphism_group()
sage: g=G.order(); g
88704000
sage: K = G.normal_subgroups()[1]
sage: K.is_simple()
True
sage: g//K.order()
2

REFERENCES:

[BROUWER-HS-2009] Higman-Sims graph. Andries E. Brouwer, accessed 24 October 2009.

[HIGMAN1968] A simple group of order 44,352,000, Math.Z. 105 (1968) 110-113. D.G. Higman & C. Sims.

[HAFNER2004] (1, 2) On the graphs of Hoffman-Singleton and Higman-Sims. The Electronic Journal of Combinatorics 11 (2004), #R77, Paul R. Hafner, accessed 24 October 2009.

AUTHOR:

Rob Beezer (2009-10-24)

HoffmanSingletonGraph()¶

Returns the Hoffman-Singleton graph.

The Hoffman-Singleton graph is the Moore graph of degree 7, diameter 2 and girth 5. The Hoffman-Singleton theorem states that any Moore graph with girth 5 must have degree 2, 3, 7 or 57. The first three respectively are the pentagon, the Petersen graph, and the Hoffman-Singleton graph. The existence of a Moore graph with girth 5 and degree 57 is still open.

A Moore graph is a graph with diameter $d$ and girth $2d + 1$ . This implies that the graph is regular, and distance regular.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. A novel algorithm written by Tom Boothby gives a random layout which is pleasing to the eye.

REFERENCES:

[1] Godsil, C. and Royle, G. Algebraic Graph Theory. Springer, 2001.

EXAMPLES:

sage: HS = graphs.HoffmanSingletonGraph()
sage: Set(HS.degree())
{7}
sage: HS.girth()
5
sage: HS.diameter()
2
sage: HS.num_verts()
50

HouseGraph()¶

Returns a house graph with 5 nodes.

A house graph is named for its shape. It is a triangle (roof) over a square (walls).

This constructor depends on NetworkX numeric labeling.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the house graph is drawn with the first node in the lower-left corner of the house, the second in the lower-right corner of the house. The third node is in the upper-left corner connecting the roof to the wall, and the fourth is in the upper-right corner connecting the roof to the wall. The fifth node is the top of the roof, connected only to the third and fourth.

EXAMPLES: Construct and show a house graph

sage: g = graphs.HouseGraph()
sage: g.show() # long time

HouseXGraph()¶

Returns a house X graph with 5 nodes.

A house X graph is a house graph with two additional edges. The upper-right corner is connected to the lower-left. And the upper-left corner is connected to the lower-right.

This constructor depends on NetworkX numeric labeling.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the house X graph is drawn with the first node in the lower-left corner of the house, the second in the lower-right corner of the house. The third node is in the upper-left corner connecting the roof to the wall, and the fourth is in the upper-right corner connecting the roof to the wall. The fifth node is the top of the roof, connected only to the third and fourth.

EXAMPLES: Construct and show a house X graph

sage: g = graphs.HouseXGraph()
sage: g.show() # long time

HyperStarGraph(n, k)¶

Returns 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.

INPUT:

n
k

EXAMPLES:

sage: g = graphs.HyperStarGraph(6,3)
sage: g.plot() # long time

REFERENCES:

Lee, Hyeong-Ok, Jong-Seok Kim, Eunseuk Oh, and Hyeong-Seok Lim. “Hyper-Star Graph: A New Interconnection Network Improving the Network Cost of the Hypercube.” In Proceedings of the First EurAsian Conference on Information and Communication Technology, 858-865. Springer-Verlag, 2002.

AUTHORS:

Michael Yurko (2009-09-01)

IcosahedralGraph()¶

Returns an Icosahedral graph (with 12 nodes).

The regular icosahedron is a 20-sided triangular polyhedron. The icosahedral graph corresponds to the connectivity of the vertices of the icosahedron. It is dual to the dodecahedral graph. The icosahedron is symmetric, so the spring-layout algorithm will be very effective for display.

PLOTTING: The Icosahedral graph should be viewed in 3 dimensions. We chose to use the default spring-layout algorithm here, so that multiple iterations might yield a different point of reference for the user. We hope to add rotatable, 3-dimensional viewing in the future. In such a case, a string argument will be added to select the flat spring-layout over a future implementation.

EXAMPLES: Construct and show an Octahedral graph

sage: g = graphs.IcosahedralGraph()
sage: g.show() # long time

Create several icosahedral graphs in a Sage graphics array. They will be drawn differently due to the use of the spring-layout algorithm.

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.IcosahedralGraph()
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

IntervalGraph(intervals)¶

Returns the graph corresponding to the given intervals.

An interval graph is built from a list $(a_i,b_i)_{1\leq i \leq n}$ of intervals : to each interval of the list is associated one vertex, two vertices being adjacent if the two corresponding (closed) intervals intersect.

INPUT:

intervals – the list of pairs $(a_i,b_i)$ defining the graph.

NOTE:

The intervals $(a_i,b_i)$ must verify $a_i<b_i$ .

EXAMPLE:

The following line creates the sequence of intervals $(i, i+2)$ for i in $[0, ..., 8]$ :

sage: intervals = [(i,i+2) for i in range(9)]

In the corresponding graph...:

sage: g = graphs.IntervalGraph(intervals)
sage: sorted(g.neighbors((3,5)))
[(1, 3), (2, 4), (4, 6), (5, 7)]

And the clique number is as expected

sage: g.clique_number()
3

KneserGraph(n, k)¶

Returns the Kneser Graph with parameters $n, k$ .

The Kneser Graph with parameters $n,k$ is the graph whose vertices are the $k$ -subsets of $[0,1,\dots,n-1]$ , and such that two vertices are adjacent if their corresponding sets are disjoint.

For example, the Petersen Graph can be defined as the Kneser Graph with parameters $5,2$ .

EXAMPLE:

sage: KG=graphs.KneserGraph(5,2)
sage: print KG.vertices()
[{4, 5}, {1, 3}, {2, 5}, {2, 3}, {3, 4}, {3, 5}, {1, 4}, {1, 5}, {1, 2}, {2, 4}]
sage: P=graphs.PetersenGraph()
sage: P.is_isomorphic(KG)
True

TESTS:

sage: KG=graphs.KneserGraph(0,0)
...
ValueError: Parameter n should be a strictly positive integer
sage: KG=graphs.KneserGraph(5,6)
...
ValueError: Parameter k should be a strictly positive integer inferior to n

KrackhardtKiteGraph()¶

Returns a Krackhardt kite graph with 10 nodes.

The Krackhardt kite graph was originally developed by David Krackhardt for the purpose of studying social networks. It is used to show the distinction between: degree centrality, betweeness centrality, and closeness centrality. For more information read the plotting section below in conjunction with the example.

REFERENCES:

[1] Kreps, V. (2002). “Social Network Analysis”. [Online] Available: http://www.fsu.edu/~spap/water/network/intro.htm [2007, January 17]

This constructor depends on NetworkX numeric labeling.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the graph is drawn left to right, in top to bottom row sequence of [2, 3, 2, 1, 1, 1] nodes on each row. This places the fourth node (3) in the center of the kite, with the highest degree. But the fourth node only connects nodes that are otherwise connected, or those in its clique (i.e.: Degree Centrality). The eighth (7) node is where the kite meets the tail. It has degree = 3, less than the average, but is the only connection between the kite and tail (i.e.: Betweenness Centrality). The sixth and seventh nodes (5 and 6) are drawn in the third row and have degree = 5. These nodes have the shortest path to all other nodes in the graph (i.e.: Closeness Centrality). Please execute the example for visualization.

EXAMPLE: Construct and show a Krackhardt kite graph

sage: g = graphs.KrackhardtKiteGraph()
sage: g.show() # long time

LCFGraph(n, shift_list, repeats)¶

Returns the cubic graph specified in LCF notation.

LCF (Lederberg-Coxeter-Fruchte) notation is a concise way of describing cubic Hamiltonian graphs. The way a graph is constructed is as follows. Since there is a Hamiltonian cycle, we first create a cycle on n nodes. The variable shift_list = [s_0, s_1, ..., s_k-1] describes edges to be created by the following scheme: for each i, connect vertex i to vertex (i + s_i). Then, repeats specifies the number of times to repeat this process, where on the jth repeat we connect vertex (i + j*len(shift_list)) to vertex ( i + j*len(shift_list) + s_i).

INPUT:

n - the number of nodes.
shift_list - a list of integer shifts mod n.
repeats - the number of times to repeat the process.

EXAMPLES:

sage: G = graphs.LCFGraph(4, [2,-2], 2)
sage: G.is_isomorphic(graphs.TetrahedralGraph())
True

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

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

The largest cubic nonplanar graph of diameter three:

sage: G = graphs.LCFGraph(20, [-10,-7,-5,4,7,-10,-7,-4,5,7,-10,-7,6,-5,7,-10,-7,5,-6,7], 1)
sage: G.degree()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
sage: G.diameter()
3
sage: G.show()  # long time

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

REFERENCES:

[1] Frucht, R. “A Canonical Representation of Trivalent Hamiltonian Graphs.” J. Graph Th. 1, 45-60, 1976.
[2] Grunbaum, B. Convex Polytope es. New York: Wiley, pp. 362-364, 1967.
[3] Lederberg, J. ‘DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs.’ Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. http://profiles.nlm.nih.gov/BB/A/B/I/U/_/bbabiu.pdf.

LadderGraph(n)¶

Returns a ladder graph with 2*n nodes.

A ladder graph is a basic structure that is typically displayed as a ladder, i.e.: two parallel path graphs connected at each corresponding node pair.

This constructor depends on NetworkX numeric labels.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each ladder graph will be displayed horizontally, with the first n nodes displayed left to right on the top horizontal line.

EXAMPLES: Construct and show a ladder graph with 14 nodes

sage: g = graphs.LadderGraph(7)
sage: g.show() # long time

Create several ladder graphs in a Sage graphics array

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.LadderGraph(i+2)
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

LollipopGraph(n1, n2)¶

Returns a lollipop graph with n1+n2 nodes.

A lollipop graph is a path graph (order n2) connected to a complete graph (order n1). (A barbell graph minus one of the bells).

This constructor depends on NetworkX numeric labels.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the complete graph will be drawn in the lower-left corner with the (n1)th node at a 45 degree angle above the right horizontal center of the complete graph, leading directly into the path graph.

EXAMPLES: Construct and show a lollipop graph Candy = 13, Stick = 4

sage: g = graphs.LollipopGraph(13,4)
sage: g.show() # long time

Create several lollipop graphs in a Sage graphics array

sage: g = []
sage: j = []
sage: for i in range(6):
...    k = graphs.LollipopGraph(i+3,4)
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

MoebiusKantorGraph()¶

Returns a Moebius-Kantor Graph.

A Moebius-Kantor graph is a cubic symmetric graph. (See also the Heawood graph). It has 16 nodes and 24 edges. It is nonplanar and Hamiltonian. It has diameter = 4, girth = 6, and chromatic number = 2. It is identical to the Generalized Petersen graph, P[8,3].

PLOTTING: See the plotting section for the generalized Petersen graphs.

REFERENCES:

[1] Weisstein, E. (1999). “Moebius-Kantor Graph - from Wolfram MathWorld”. [Online] Available: http://mathworld.wolfram.com/Moebius-KantorGraph.html [2007, February 17]

EXAMPLES:

sage: MK = graphs.MoebiusKantorGraph()
sage: MK
Moebius-Kantor Graph: Graph on 16 vertices
sage: MK.graph6_string()
'OhCGKE?O@?ACAC@I?Q_AS'
sage: (graphs.MoebiusKantorGraph()).show() # long time

NKStarGraph(n, k)¶

Returns the (n,k)-star graph.

The vertices of the (n,k)-star graph are the set of all arrangements of n symbols into labels of length k. There are two adjacency rules for the (n,k)-star graph. First, two vertices are adjacent if one can be obtained from the other by swapping the first symbol with another symbol. Second, two vertices are adjacent if one can be obtained from the other by swapping the first symbol with an external symbol (a symbol not used in the original label).

INPUT:

n
k

EXAMPLES:

sage: g = graphs.NKStarGraph(4,2)
sage: g.plot() # long time

REFERENCES:

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

AUTHORS:

Michael Yurko (2009-09-01)

NStarGraph(n)¶

Returns the n-star graph.

The vertices of the n-star graph are the set of permutations on n symbols. There is an edge between two vertices if their labels differ only in the first and one other position.

INPUT:

n

EXAMPLES:

sage: g = graphs.NStarGraph(4)
sage: g.plot() # long time

REFERENCES:

S.B. Akers, D. Horel and B. Krishnamurthy, The star graph: An attractive alternative to the previous n-cube. In: Proc. Internat. Conf. on Parallel Processing (1987), pp. 393–400.

AUTHORS:

Michael Yurko (2009-09-01)

OctahedralGraph()¶

Returns an Octahedral graph (with 6 nodes).

The regular octahedron is an 8-sided polyhedron with triangular faces. The octahedral graph corresponds to the connectivity of the vertices of the octahedron. It is the line graph of the tetrahedral graph. The octahedral is symmetric, so the spring-layout algorithm will be very effective for display.

PLOTTING: The Octahedral graph should be viewed in 3 dimensions. We chose to use the default spring-layout algorithm here, so that multiple iterations might yield a different point of reference for the user. We hope to add rotatable, 3-dimensional viewing in the future. In such a case, a string argument will be added to select the flat spring-layout over a future implementation.

EXAMPLES: Construct and show an Octahedral graph

sage: g = graphs.OctahedralGraph()
sage: g.show() # long time

Create several octahedral graphs in a Sage graphics array They will be drawn differently due to the use of the spring-layout algorithm

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.OctahedralGraph()
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

OddGraph(n)¶

Returns the Odd Graph with parameter $n$ .

The Odd Graph with parameter $n$ is defined as the Kneser Graph with parameters $2n-1,n-1$ . Equivalently, the Odd Graph is the graph whose vertices are the $n-1$ -subsets of $[0,1,\dots,2(n-1)]$ , and such that two vertices are adjacent if their corresponding sets are disjoint.

For example, the Petersen Graph can be defined as the Odd Graph with parameter $3$ .

EXAMPLE:

sage: OG=graphs.OddGraph(3)
sage: print OG.vertices()
[{4, 5}, {1, 3}, {2, 5}, {2, 3}, {3, 4}, {3, 5}, {1, 4}, {1, 5}, {1, 2}, {2, 4}]
sage: P=graphs.PetersenGraph()
sage: P.is_isomorphic(OG)
True

TESTS:

sage: KG=graphs.OddGraph(1)
...
ValueError: Parameter n should be an integer strictly greater than 1

PappusGraph()¶

Returns the Pappus graph, a graph on 18 vertices.

The Pappus graph is cubic, symmetric, and distance-regular.

EXAMPLES:

sage: G = graphs.PappusGraph()
sage: G.show()  # long time
sage: L = graphs.LCFGraph(18, [5,7,-7,7,-7,-5], 3)
sage: L.show()  # long time
sage: G.is_isomorphic(L)
True

PathGraph(n, pos=None)¶

Returns a path graph with n nodes. Pos argument takes a string which is either ‘circle’ or ‘line’, (otherwise the default is used). See the plotting section below for more detail.

A path graph is a graph where all inner nodes are connected to their two neighbors and the two end-nodes are connected to their one inner neighbors. (i.e.: a cycle graph without the first and last node connected).

This constructor depends on NetworkX numeric labels.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the graph may be drawn in one of two ways: The ‘line’ argument will draw the graph in a horizontal line (left to right) if there are less than 11 nodes. Otherwise the ‘line’ argument will append horizontal lines of length 10 nodes below, alternating left to right and right to left. The ‘circle’ argument will cause the graph to be drawn in a cycle-shape, with the first node at the top and then about the circle in a clockwise manner. By default (without an appropriate string argument) the graph will be drawn as a ‘circle’ if 10 n 41 and as a ‘line’ for all other n.

EXAMPLES: Show default drawing by size: ‘line’: n 11

sage: p = graphs.PathGraph(10)
sage: p.show() # long time

‘circle’: 10 n 41

sage: q = graphs.PathGraph(25)
sage: q.show() # long time

‘line’: n 40

sage: r = graphs.PathGraph(55)
sage: r.show() # long time

Override the default drawing:

sage: s = graphs.PathGraph(5,'circle')
sage: s.show() # long time

PetersenGraph()¶

The Petersen Graph is a named graph that consists of 10 vertices and 15 edges, usually drawn as a five-point star embedded in a pentagon.

The Petersen Graph is a common counterexample. For example, it is not Hamiltonian.

PLOTTING: See the plotting section for the generalized Petersen graphs.

EXAMPLES: We compare below the Petersen graph with the default spring-layout versus a planned position dictionary of [x,y] tuples:

sage: petersen_spring = Graph({0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[0,3,9], 5:[0,7,8], 6:[1,8,9], 7:[2,5,9], 8:[3,5,6], 9:[4,6,7]})
sage: petersen_spring.show() # long time
sage: petersen_database = graphs.PetersenGraph()
sage: petersen_database.show() # long time

RandomBarabasiAlbert(n, m, seed=None)¶

Return a random graph created using the Barabasi-Albert preferential attachment model.

A graph with m vertices and no edges is initialized, and a graph of n vertices is grown by attaching new vertices each with m edges that are attached to existing vertices, preferentially with high degree.

INPUT:

n - number of vertices in the graph
m - number of edges to attach from each new node
seed - for random number generator

EXAMPLES:

We show the edge list of a random graph on 6 nodes with m = 2.

sage: graphs.RandomBarabasiAlbert(6,2).edges(labels=False)
[(0, 2), (0, 3), (0, 4), (1, 2), (2, 3), (2, 4), (2, 5), (3, 5)]

We plot a random graph on 12 nodes with m = 3.

sage: ba = graphs.RandomBarabasiAlbert(12,3)
sage: ba.show()  # long time

We view many random graphs using a graphics array:

sage: g = []
sage: j = []
sage: for i in range(1,10):
...    k = graphs.RandomBarabasiAlbert(i+3, 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 = sage.plot.plot.GraphicsArray(j)
sage: G.show()  # long time

RandomBipartite(n1, n2, p)¶

Returns a bipartite graph with $n1+n2$ vertices such that any edge from $[n1]$ to $[n2]$ exists with probability $p$ .

INPUT:

n1,n2 : Cardinalities of the two sets

p : Probability for an edge to exist

EXAMPLE:

sage: g=graphs.RandomBipartite(5,2,0.5)
sage: g.vertices()
[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1)]

TESTS:

sage: g=graphs.RandomBipartite(5,-3,0.5)
...
ValueError: n1 and n2 should be integers strictly greater than 0
sage: g=graphs.RandomBipartite(5,3,1.5)
...
ValueError: Parameter p is a probability, and so should be a real value between 0 and 1

RandomGNM(n, m, dense=False, seed=None)¶

Returns a graph randomly picked out of all graphs on n vertices with m edges.

INPUT:

n - number of vertices.
m - number of edges.
dense - whether to use NetworkX’s dense_gnm_random_graph or gnm_random_graph

EXAMPLES: We show the edge list of a random graph on 5 nodes with 10 edges.

sage: graphs.RandomGNM(5, 10).edges(labels=False)
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

We plot a random graph on 12 nodes with m = 12.

sage: gnm = graphs.RandomGNM(12, 12)
sage: gnm.show()  # long time

We view many random graphs using a graphics array:

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.RandomGNM(i+3, i^2-i)
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show()  # long time

RandomGNP(n, p, seed=None, fast=True)¶

Returns a Random graph on $n$ nodes. Each edge is inserted independently with probability $p$ .

IMPLEMENTATION: This function calls the NetworkX function fast_gnp_random_graph, unless fast==False, then gnp_random_graph.

REFERENCES:

[1] P. Erdos and A. Renyi, On Random Graphs, Publ. Math. 6, 290 (1959).
[2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959).

PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.

EXAMPLES: We show the edge list of a random graph on 6 nodes with probability $p = .4$ :

sage: graphs.RandomGNP(6, .4).edges(labels=False)
[(0, 1), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5)]

We plot a random graph on 12 nodes with probability $p = .71$ :

sage: gnp = graphs.RandomGNP(12,.71)
sage: gnp.show() # long time

We view many random graphs using a graphics array:

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.RandomGNP(i+3,.43)
...    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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time
sage: graphs.RandomGNP(4,1)
Complete graph: Graph on 4 vertices

TIMINGS: The following timings compare the speed with fast==False and fast==True for sparse and dense graphs. (It’s no different?)

sage: t=cputime(); regular_sparse = graphs.RandomGNP(389,.22)
sage: cputime(t)     # slightly random
0.2240130000000029

sage: t=cputime(); fast_sparse =  graphs.RandomGNP(389,.22,fast=True)
sage: cputime(t)     # slightly random
0.22401400000000038

sage: t=cputime(); regular_dense = graphs.RandomGNP(389,.88)    # long time
sage: cputime(t)     # slightly random, long time
0.87205499999999958

sage: t=cputime(); fast_dense = graphs.RandomGNP(389,.88,fast=True)    # long time
sage: cputime(t)     # slightly random, long time
0.90005700000000033

RandomHolmeKim(n, m, p, seed=None)¶

Returns a random graph generated by the Holme and Kim algorithm for graphs with power law degree distribution and approximate average clustering.

INPUT:

n - number of vertices.
m - number of random edges to add for each new node.
p - probability of adding a triangle after adding a random edge.
seed - for the random number generator.

From the NetworkX documentation: The average clustering has a hard time getting above a certain cutoff that depends on m. This cutoff is often quite low. Note that the transitivity (fraction of triangles to possible triangles) seems to go down with network size. It is essentially the Barabasi-Albert growth model with an extra step that each random edge is followed by a chance of making an edge to one of its neighbors too (and thus a triangle). This algorithm improves on B-A in the sense that it enables a higher average clustering to be attained if desired. It seems possible to have a disconnected graph with this algorithm since the initial m nodes may not be all linked to a new node on the first iteration like the BA model.

EXAMPLE: We show the edge list of a random graph on 8 nodes with 2 random edges per node and a probability $p = 0.5$ of forming triangles.

sage: graphs.RandomHolmeKim(8, 2, 0.5).edges(labels=False)
[(0, 2), (0, 4), (1, 2), (1, 3), (2, 3), (3, 4), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6)]

sage: G = graphs.RandomHolmeKim(12, 3, .3)
sage: G.show()  # long time

REFERENCE:

[1] Holme, P. and Kim, B.J. Growing scale-free networks with tunable clustering, Phys. Rev. E (2002). vol 65, no 2, 026107.

RandomInterval(n)¶

Returns a random interval graph.

An interval graph is built from a list $(a_i,b_i)_{1\leq i \leq n}$ of intervals : to each interval of the list is associated one vertex, two vertices being adjacent if the two corresponding intervals intersect.

A random interval graph of order $n$ is generated by picking random values for the $(a_i,b_j)$ , each of the two coordinates being generated from the uniform distribution on the interval $[0,1]$ .

This definitions follows [boucheron2001].

INPUT:

n (integer) – the number of vertices in the random graph.

EXAMPLE:

As for any interval graph, the chromatic number is equal to the clique number

sage: g = graphs.RandomInterval(8)
sage: g.clique_number() == g.chromatic_number()
True

REFERENCE:

[boucheron2001]

Boucheron, S. and FERNANDEZ de la VEGA, W., On the Independence Number of Random Interval Graphs, Combinatorics, Probability and Computing v10, issue 05, Pages 385–396, Cambridge Univ Press, 2001

RandomLobster(n, p, q, seed=None)¶

Returns a random lobster.

A lobster is a tree that reduces to a caterpillar when pruning all leaf vertices. A caterpillar is a tree that reduces to a path when pruning all leaf vertices (q=0).

INPUT:

n - expected number of vertices in the backbone
p - probability of adding an edge to the backbone
q - probability of adding an edge (claw) to the arms
seed - for the random number generator

EXAMPLE: We show the edge list of a random graph with 3 backbone nodes and probabilities $p = 0.7$ and $q = 0.3$ :

sage: graphs.RandomLobster(3, 0.7, 0.3).edges(labels=False)        
[(0, 1), (1, 2)]

sage: G = graphs.RandomLobster(9, .6, .3)
sage: G.show()  # long time

RandomNewmanWattsStrogatz(n, k, p, seed=None)¶

Returns a Newman-Watts-Strogatz small world random graph on n vertices.

From the NetworkX documentation: First create a ring over n nodes. Then each node in the ring is connected with its k nearest neighbors. Then shortcuts are created by adding new edges as follows: for each edge u-v in the underlying “n-ring with k nearest neighbors”; with probability p add a new edge u-w with randomly-chosen existing node w. In contrast with watts_strogatz_graph(), no edges are removed.

INPUT:

n - number of vertices.
k - each vertex is connected to its k nearest neighbors
p - the probability of adding a new edge for each edge
seed - for the random number generator

EXAMPLE: We show the edge list of a random graph on 7 nodes with 2 “nearest neighbors” and probability $p = 0.2$ :

sage: graphs.RandomNewmanWattsStrogatz(7, 2, 0.2).edges(labels=False)
[(0, 1), (0, 2), (0, 3), (0, 6), (1, 2), (2, 3), (2, 4), (3, 4), (3, 6), (4, 5), (5, 6)]

sage: G = graphs.RandomNewmanWattsStrogatz(12, 2, .3)       
sage: G.show()  # long time

REFERENCE:

[1] Newman, M.E.J., Watts, D.J. and Strogatz, S.H. Random graph models of social networks. Proc. Nat. Acad. Sci. USA 99, 2566-2572.

RandomRegular(d, n, seed=None)¶

Returns a random d-regular graph on n vertices, or returns False on failure.

Since every edge is incident to two vertices, n*d must be even.

INPUT:

n - number of vertices
d - degree
seed - for the random number generator

EXAMPLE: We show the edge list of a random graph with 8 nodes each of degree 3.

sage: graphs.RandomRegular(3, 8).edges(labels=False)
[(0, 1), (0, 4), (0, 7), (1, 5), (1, 7), (2, 3), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5), (6, 7)]

sage: G = graphs.RandomRegular(3, 20)
sage: if G:
...    G.show()  # random output, long time

REFERENCES:

[1] Kim, Jeong Han and Vu, Van H. Generating random regular graphs. Proc. 35th ACM Symp. on Thy. of Comp. 2003, pp 213-222. ACM Press, San Diego, CA, USA. http://doi.acm.org/10.1145/780542.780576
[2] Steger, A. and Wormald, N. Generating random regular graphs quickly. Prob. and Comp. 8 (1999), pp 377-396.

RandomShell(constructor, seed=None)¶

Returns a random shell graph for the constructor given.

INPUT:

constructor - a list of 3-tuples (n,m,d), each representing a shell
n - the number of vertices in the shell
m - the number of edges in the shell
d - the ratio of inter (next) shell edges to intra shell edges
seed - for the random number generator

EXAMPLE:

sage: G = graphs.RandomShell([(10,20,0.8),(20,40,0.8)])
sage: G.edges(labels=False)
[(0, 3), (0, 7), (0, 8), (1, 2), (1, 5), (1, 8), (1, 9), (3, 6), (3, 11), (4, 6), (4, 7), (4, 8), (4, 21), (5, 8), (5, 9), (6, 9), (6, 10), (7, 8), (7, 9), (8, 18), (10, 11), (10, 13), (10, 19), (10, 22), (10, 26), (11, 18), (11, 26), (11, 28), (12, 13), (12, 14), (12, 28), (12, 29), (13, 16), (13, 21), (13, 29), (14, 18), (16, 20), (17, 18), (17, 26), (17, 28), (18, 19), (18, 22), (18, 27), (18, 28), (19, 23), (19, 25), (19, 28), (20, 22), (24, 26), (24, 27), (25, 27), (25, 29)]
sage: G.show()  # long time

RandomTreePowerlaw(n, gamma=3, tries=100, seed=None)¶

Returns a tree with a power law degree distribution. Returns False on failure.

From the NetworkX documentation: A trial power law degree sequence is chosen and then elements are swapped with new elements from a power law distribution until the sequence makes a tree (size = order - 1).

INPUT:

n - number of vertices
gamma - exponent of power law
tries - number of attempts to adjust sequence to make a tree
seed - for the random number generator

EXAMPLE: We show the edge list of a random graph with 10 nodes and a power law exponent of 2.

sage: graphs.RandomTreePowerlaw(10, 2).edges(labels=False)
[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (6, 8), (6, 9)]

sage: G = graphs.RandomTreePowerlaw(15, 2)
sage: if G:
...    G.show()  # random output, long time

StarGraph(n)¶

Returns a star graph with n+1 nodes.

A Star graph is a basic structure where one node is connected to all other nodes.

This constructor is dependent on NetworkX numeric labels.

PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each star graph will be displayed with the first (0) node in the center, the second node (1) at the top, with the rest following in a counterclockwise manner. (0) is the node connected to all other nodes.

The star graph is a good opportunity to compare efficiency of filling a position dictionary vs. using the spring-layout algorithm for plotting. As far as display, the spring-layout should push all other nodes away from the (0) node, and thus look very similar to this constructor’s positioning.

EXAMPLES:

sage: import networkx

Compare the plots:

sage: n = networkx.star_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.StarGraph(23)
sage: spring23.show() # long time
sage: posdict23.show() # long time

View many star graphs as a Sage Graphics Array

With this constructor (i.e., the position dictionary filled)

sage: g = []
sage: j = []
sage: for i in range(9):
...    k = graphs.StarGraph(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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

Compared to plotting with the spring-layout algorithm

sage: g = []
sage: j = []
sage: for i in range(9):
...    spr = networkx.star_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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

TetrahedralGraph()¶

Returns a tetrahedral graph (with 4 nodes).

A tetrahedron is a 4-sided triangular pyramid. The tetrahedral graph corresponds to the connectivity of the vertices of the tetrahedron. This graph is equivalent to a wheel graph with 4 nodes and also a complete graph on four nodes. (See examples below).

PLOTTING: The tetrahedral graph should be viewed in 3 dimensions. We chose to use the default spring-layout algorithm here, so that multiple iterations might yield a different point of reference for the user. We hope to add rotatable, 3-dimensional viewing in the future. In such a case, a string argument will be added to select the flat spring-layout over a future implementation.

EXAMPLES: Construct and show a Tetrahedral graph

sage: g = graphs.TetrahedralGraph()
sage: g.show() # long time

The following example requires networkx:

sage: import networkx as NX

Compare this Tetrahedral, Wheel(4), Complete(4), and the Tetrahedral plotted with the spring-layout algorithm below in a Sage graphics array:

sage: tetra_pos = graphs.TetrahedralGraph()
sage: tetra_spring = Graph(NX.tetrahedral_graph())
sage: wheel = graphs.WheelGraph(4)
sage: complete = graphs.CompleteGraph(4)
sage: g = [tetra_pos, tetra_spring, wheel, complete]
sage: j = []
sage: for i in range(2):
...    n = []
...    for m in range(2):
...        n.append(g[i + m].plot(vertex_size=50, vertex_labels=False))
...    j.append(n)
sage: G = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

ThomsenGraph()¶

Returns the Thomsen Graph.

The Thomsen Graph is actually a complete bipartite graph with (n1, n2) = (3, 3). It is also called the Utility graph.

PLOTTING: See CompleteBipartiteGraph.

EXAMPLES:

sage: T = graphs.ThomsenGraph()
sage: T
Thomsen graph: Graph on 6 vertices
sage: T.graph6_string()
'EFz_'
sage: (graphs.ThomsenGraph()).show() # long time

ToroidalGrid2dGraph(n1, n2)¶

Returns a toroidal 2-dimensional grid graph with $n_1n_2$ nodes ( $n_1$ rows and $n_2$ columns).

The toroidal 2-dimensional grid with parameters $n_1,n_2$ is the 2-dimensional grid graph with identital parameters to which are added the edges $((i,0),(i,n_2-1))$ and $((0,i),(n_1-1,i))$ .

EXAMPLE:

The toroidal 2-dimensional grid is a regular graph, while the usual 2-dimensional grid is not

sage: tgrid = graphs.ToroidalGrid2dGraph(8,9)
sage: print tgrid
Toroidal 2D Grid Graph with parameters 8,9
sage: grid = graphs.Grid2dGraph(8,9)
sage: grid.is_regular()
False
sage: tgrid.is_regular()
True

WheelGraph(n)¶

Returns a Wheel graph with n nodes.

A Wheel graph is a basic structure where one node is connected to all other nodes and those (outer) nodes are connected cyclically.

This constructor depends on NetworkX numeric labels.

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: 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 = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

Next, using the spring-layout algorithm:

sage: import networkx
sage: g = []
sage: j = []
sage: for i in range(9):
...    spr = networkx.wheel_graph(i+3)       
...    k = Graph(spr)
...    g.append(k)
...
sage: for i in range(3):
...    n = []
...    for m in range(3):
...        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
...    j.append(n)
...
sage: G = sage.plot.plot.GraphicsArray(j)
sage: G.show() # long time

Compare the plotting:

sage: n = networkx.wheel_graph(23)
sage: spring23 = Graph(n)
sage: posdict23 = graphs.WheelGraph(23)
sage: spring23.show() # long time
sage: posdict23.show() # long time

WorldMap()¶

Returns the Graph of all the countries, in which two countries are adjacent in the graph if they have a common boundary.

This graph has been built from the data available in The CIA World Factbook [CIA] (2009-08-21).

The returned graph G has a member G.gps_coordinates equal to a dictionary containing the GPS coordinates of each country’s capital city.

EXAMPLE:

sage: g=graphs.WorldMap()
sage: g.has_edge("France","Italy")
True
sage: g.gps_coordinates["Bolivia"]
[[17, 'S'], [65, 'W']]
sage: sorted(g.connected_component_containing_vertex('Ireland'))
['Ireland', 'United Kingdom']

REFERENCE:

[CIA]

CIA Factbook 09 https://www.cia.gov/library/publications/the-world-factbook/

nauty_geng(options='')¶

Calls the geng program in the optional nauty spkg to generate graphs. The options argument is passed straight to nauty.

INPUT:

options - a string passed to the command line of geng. You must pass the number of vertices you desire.

EXAMPLES:

sage: graph_list = graphs.nauty_geng("-q 3") # requires the optional nauty package
sage: len(graph_list) # requires the optional nauty package
4

trees(vertices)¶

Accesses the generator of trees (graphs without cycles). Iterates over distinct, exhaustive representatives.

INPUT:

vertices - natural number

EXAMPLES: Sloane A000055:

sage: for i in range(0, 7):
...    print len(list(graphs.trees(i)))
1
1
1
1
2
3
6
sage: for i in range(7, 10):            # long time
...    print len(list(graphs.trees(i))) # long time
11
23
47

sage.graphs.graph_generators.canaug_traverse_edge(g, aut_gens, property, dig=False, loops=False, implementation='c_graph', sparse=True)¶

Main function for exhaustive generation. Recursive traversal of a canonically generated tree of isomorph free graphs satisfying a given property.

INPUT:

g - current position on the tree.
aut_gens - list of generators of Aut(g), in list notation.
property - check before traversing below g.

EXAMPLES:

sage: from sage.graphs.graph_generators import canaug_traverse_edge
sage: G = Graph(3)
sage: list(canaug_traverse_edge(G, [], lambda x: True))
[Graph on 3 vertices, ... Graph on 3 vertices]

The best way to access this function is through the graphs() iterator:

Print graphs on 3 or less vertices.

sage: for G in graphs(3):
...    print G
...
Graph on 3 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 3 vertices

Print digraphs on 3 or less vertices.

sage: for G in digraphs(3):
...    print G
...
Digraph on 3 vertices
Digraph on 3 vertices
...
Digraph on 3 vertices
Digraph on 3 vertices

sage.graphs.graph_generators.canaug_traverse_vert(g, aut_gens, max_verts, property, dig=False, loops=False, implementation='c_graph', sparse=True)¶

Main function for exhaustive generation. Recursive traversal of a canonically generated tree of isomorph free (di)graphs satisfying a given property.

INPUT:

g - current position on the tree.
aut_gens - list of generators of Aut(g), in list notation.
max_verts - when to retreat.
property - check before traversing below g.
deg_seq - specify a degree sequence to try to obtain.

EXAMPLES:

sage: from sage.graphs.graph_generators import canaug_traverse_vert
sage: list(canaug_traverse_vert(Graph(), [], 3, lambda x: True))
[Graph on 0 vertices, ... Graph on 3 vertices]

The best way to access this function is through the graphs() iterator:

Print graphs on 3 or less vertices.

sage: for G in graphs(3, augment='vertices'):
...    print G
...
Graph on 0 vertices
Graph on 1 vertex
Graph on 2 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 3 vertices
Graph on 2 vertices
Graph on 3 vertices

Print digraphs on 2 or less vertices.

sage: for D in digraphs(2, augment='vertices'):
...    print D
...
Digraph on 0 vertices
Digraph on 1 vertex
Digraph on 2 vertices
Digraph on 2 vertices
Digraph on 2 vertices

sage.graphs.graph_generators.check_aut(aut_gens, cut_vert, n)¶

Helper function for exhaustive generation.

At the start, check_aut is given a set of generators for the automorphism group, aut_gens. We already know we are looking for an element of the auto- morphism group that sends cut_vert to n, and check_aut generates these for the canaug_traverse function.

EXAMPLE: Note that the last two entries indicate that none of the automorphism group has yet been searched - we are starting at the identity [0, 1, 2, 3] and so far that is all we have seen. We return automorphisms mapping 2 to 3.

sage: from sage.graphs.graph_generators import check_aut
sage: list( check_aut( [ [0, 3, 2, 1], [1, 0, 3, 2], [2, 1, 0, 3] ], 2, 3))
[[1, 0, 3, 2], [1, 2, 3, 0]]

sage.graphs.graph_generators.check_aut_edge(aut_gens, cut_edge, i, j, n, dig=False)¶

Helper function for exhaustive generation.

At the start, check_aut_edge is given a set of generators for the automorphism group, aut_gens. We already know we are looking for an element of the auto- morphism group that sends cut_edge to {i, j}, and check_aut generates these for the canaug_traverse function.

EXAMPLE: Note that the last two entries indicate that none of the automorphism group has yet been searched - we are starting at the identity [0, 1, 2, 3] and so far that is all we have seen. We return automorphisms mapping 2 to 3.

sage: from sage.graphs.graph_generators import check_aut
sage: list( check_aut( [ [0, 3, 2, 1], [1, 0, 3, 2], [2, 1, 0, 3] ], 2, 3))
[[1, 0, 3, 2], [1, 2, 3, 0]]

A collection of constructors of common graphs.¶

Previous topic

Next topic

This Page

Navigation

A collection of constructors of common graphs.¶

Previous topic

Next topic

This Page

Quick search

Navigation