Graph Constructors

Constructors

The SimpleGraph module provides functions to create a wide variety of graphs.

Complete Graphs

• Complete(n): complete graph with vertex set {1,2,...,n}.
• Complete(n,m): complete bipartite graph.
• Complete([n1,n2,n3,...,nk]): complete multipartite graph.

Common Graphs

• Path(n): path graph with vertices {1,2,...,n}. Also Path(list).
• Cycle(n): cycle graph with vertices {1,2,...,n}.
• Wheel(n): wheel graph with n vertices.
• Grid(n,m): n-by-m grid graph.
• Cube(n): hypercube with 2^n vertices.

Geometric Graphs

• Dodecahedron(): 1-skeleton of a dodecahedron.
• Icosahedron(): 1-skeleton of an icosahedron.
• Octahedron(): 1-skeleton of an octahedron.
• Tetrahedron(): Same as Complete(4).
• Spindle(): Moser's spindle graph.
• Golomb(): Golomb's graph.
• • Note: The function is_unit_distance determines if the (embedded) graph is a unit distance graph.
• BuckyBall(): molecular graph of Buckminsterfullerene (soccer ball).

Combinatorial/Number Theory Graphs

• Petersen(): Petersen's graph.
• Kneser(n,k): Kneser graph.
• Johnson(n,k): Johnson graph.
• Knight(n,m): Knight's move graph on n-by-m chess board.
• Paley(p): Paley graph for primes congruent to 1 mod 4.

Random Graphs

• RandomGraph(n,p=0.5): Erdos-Renyi random graph.
• RandomTree(n): random tree with n vertices. See also prufer_code and prufer_restore.
• RandomRegular(n,d): random d-regular graph with n vertices.
• RandomSBM(...): random stochastic block model graph (various calling conventions).

Other

• Doyle(): Doyle/Holt graph.
• Hoffman(): Hoffman graph.
• HoffmanSingleton(): Hoffman-Singleton graph.
• Tutte(): Tutte graph (planar, 3-connected, 3-regular, non-Hamiltonian).