Common graphs#
All graphs in Sage can be built through the graphs object. In order to
build a complete graph on 15 elements, one can do:
sage: g = graphs.CompleteGraph(15)
>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(15))
To get a path with 4 vertices, and the house graph:
sage: p = graphs.PathGraph(4)
sage: h = graphs.HouseGraph()
>>> from sage.all import *
>>> p = graphs.PathGraph(Integer(4))
>>> h = graphs.HouseGraph()
More interestingly, one can get the list of all graphs that Sage knows how to
build by typing graphs. in Sage and then hitting Tab.
Basic structures
Small Graphs
A small graph is just a single graph and has no parameter influencing the number of edges or vertices.
Platonic solids (ordered ascending by number of vertices)
Families of graphs
A family of graph is an infinite set of graphs which can be indexed by fixed number of parameters, e.g. two integer parameters. (A method whose name starts with a small letter does not return a single graph object but a graph iterator or a list of graphs or …)
Graphs from classical geometries over finite fields
A number of classes of graphs related to geometries over finite fields and quadrics and Hermitean varieties there.
Chessboard Graphs
Intersection graphs
These graphs are generated by geometric representations. The objects of the representation correspond to the graph vertices and the intersections of objects yield the graph edges.
Random graphs
Graphs with a given degree sequence
Miscellaneous
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
Jason Grout (2010-06-04): cospectral_graphs
Edward Scheinerman (2010-08-11): RandomTree
Ed Scheinerman (2010-08-21): added Grotzsch graph and Mycielski graphs
Ed Scheinerman (2010-11-15): added RandomTriangulation
Minh Van Nguyen (2010-11-26): added more named graphs
Keshav Kini (2011-02-16): added Shrikhande and Dyck graphs
David Coudert (2012-02-10): new RandomGNP generator
David Coudert (2012-08-02): added chessboard graphs: Queen, King, Knight, Bishop, and Rook graphs
Nico Van Cleemput (2013-05-26): added fullerenes
Nico Van Cleemput (2013-07-01): added benzenoids
Birk Eisermann (2013-07-29): new section ‘intersection graphs’, added (random, bounded) tolerance graphs
Marco Cognetta (2016-03-03): added TuranGraph
Janmenjaya Panda (2024-05-26): added MoebiusLadderGraph
Functions and methods#
- class sage.graphs.graph_generators.GraphGenerators[source]#
Bases:
objectA class consisting of constructors for several common graphs, as well as orderly generation of isomorphism class representatives. See the
module's helpfor a list of supported constructors.A list of all graphs and graph structures (other than isomorphism class representatives) in this database is available via tab completion. Type “graphs.” and then hit the Tab key 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.
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.
Also: see the use of the nauty package for generating graphs at the
nauty_geng()method.INPUT:
vertices– a natural number orNoneto infinitely generate bigger and bigger graphs.property– (default:lambda x: True) any property to be tested on graphs before generation, but note that in general the graphs produced are not the same as those produced by using the property function to filter a list of graphs produced by using thelambda x: Truedefault. The generation process assumes the property has certain characteristics set by theaugmentargument, and only in the case of inherited properties such that all subgraphs of the relevant kind (foraugment='edges'oraugment='vertices') of a graph with the property also possess the property will there be no missing graphs. (Thepropertyargument is ignored ifdegree_sequenceis specified.)augment– (default:'edges') possible values:'edges'– augments a fixed number of vertices by adding one edge. In this case, all graphs on exactlyn=verticesare 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.'vertices'– augments by adding a vertex and edges incident to that vertex. In this case, all graphs up ton=verticesare 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.
size– (default:None) the size of the graph to be generated.degree_sequence– (default:None) a sequence of non-negative integers, orNone. If specified, the generated graphs will have these integers for degrees. In this case, property and size are both ignored.loops– (default:False) whether to allow loops in the graph or not.sparse– (default:True); whether to use a sparse or dense data structure. See the documentation ofGraph.copy(boolean) – If set toTrue(default) this method makes copies of the graphs before returning them. If set toFalsethe method returns the graph it is working on. The second alternative is faster, but modifying any of the graph instances returned by the method may break the function’s behaviour, as it is using these graphs to compute the next ones: only usecopy = Falsewhen you stick to reading the graphs returned.
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
>>> from sage.all import * >>> for G in graphs(Integer(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 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
>>> from sage.all import * >>> for G in graphs(Integer(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
>>> from sage.all import * >>> L = graphs(Integer(5), size=Integer(4)) >>> 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 # needs sage.plot
>>> from sage.all import * >>> L = list(graphs(Integer(5), lambda G: G.size() <= Integer(4))) >>> len(L) 14 >>> graphs_list.show_graphs(L) # long time # needs sage.plot
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 # needs sage.plot
>>> from sage.all import * >>> L = list(graphs(Integer(5), lambda G: G.size() <= Integer(4), augment='vertices')) >>> len(L) 31 >>> graphs_list.show_graphs(L) # long time # needs sage.plot
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
>>> from sage.all import * >>> property = lambda G: ( max([G.degree(v) for v in G] + [Integer(0)]) <= Integer(2) ) >>> L = list(graphs(Integer(6), property, augment='vertices')) >>> len(L) 45
Generate all bipartite graphs on up to 7 vertices: (see OEIS sequence 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]
>>> from sage.all import * >>> L = list( graphs(Integer(7), lambda G: G.is_bipartite(), augment='vertices') ) >>> [len([g for g in L if g.order() == i]) for i in (ellipsis_range(Integer(1),Ellipsis,Integer(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
>>> from sage.all import * >>> L = list( graphs(Integer(7), lambda G: G.is_bipartite()) ) >>> 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
>>> from sage.all import * >>> L = list( graphs(Integer(8), lambda G: G.is_bipartite()) ) # long time >>> len(L) # long time 303
Remember that the property argument does not behave as a filter, except for appropriately inheritable properties:
sage: property = lambda G: G.is_vertex_transitive() sage: len(list(graphs(4, property))) # needs sage.groups 1 sage: sum(1 for g in graphs(4) if property(g)) # needs sage.groups 4 sage: property = lambda G: G.is_bipartite() sage: len(list(graphs(4, property))) 7 sage: sum(1 for g in graphs(4) if property(g)) 7
>>> from sage.all import * >>> property = lambda G: G.is_vertex_transitive() >>> len(list(graphs(Integer(4), property))) # needs sage.groups 1 >>> sum(Integer(1) for g in graphs(Integer(4)) if property(g)) # needs sage.groups 4 >>> property = lambda G: G.is_bipartite() >>> len(list(graphs(Integer(4), property))) 7 >>> sum(Integer(1) for g in graphs(Integer(4)) if property(g)) 7
Generate graphs on the fly: (see OEIS sequence A000088)
sage: for i in range(7): ....: print(len(list(graphs(i)))) 1 1 2 4 11 34 156
>>> from sage.all import * >>> for i in range(Integer(7)): ... print(len(list(graphs(i)))) 1 1 2 4 11 34 156
Generate all simple graphs, allowing loops: (see OEIS sequence A000666)
sage: L = list(graphs(5,augment='vertices',loops=True)) # long time sage: for i in [0..5]: # long time ....: print((i, len([g for g in L if g.order() == i]))) (0, 1) (1, 2) (2, 6) (3, 20) (4, 90) (5, 544)
>>> from sage.all import * >>> L = list(graphs(Integer(5),augment='vertices',loops=True)) # long time >>> for i in (ellipsis_range(Integer(0),Ellipsis,Integer(5))): # long time ... print((i, len([g for g in L if g.order() == i]))) (0, 1) (1, 2) (2, 6) (3, 20) (4, 90) (5, 544)
Generate all graphs with a specified degree sequence (see OEIS sequence A002851):
sage: for i in [4,6,8]: # long time (4s on sage.math, 2012) ....: print((i, len([g for g in graphs(i, degree_sequence=[3]*i) if g.is_connected()]))) (4, 1) (6, 2) (8, 5) sage: for i in [4,6,8]: # long time (7s on sage.math, 2012) ....: print((i, len([g for g in graphs(i, augment='vertices', degree_sequence=[3]*i) if g.is_connected()]))) (4, 1) (6, 2) (8, 5)
>>> from sage.all import * >>> for i in [Integer(4),Integer(6),Integer(8)]: # long time (4s on sage.math, 2012) ... print((i, len([g for g in graphs(i, degree_sequence=[Integer(3)]*i) if g.is_connected()]))) (4, 1) (6, 2) (8, 5) >>> for i in [Integer(4),Integer(6),Integer(8)]: # long time (7s on sage.math, 2012) ... print((i, len([g for g in graphs(i, augment='vertices', degree_sequence=[Integer(3)]*i) if g.is_connected()]))) (4, 1) (6, 2) (8, 5)
sage: print((10, len([g for g in graphs(10,degree_sequence=[3]*10) if g.is_connected()]))) # not tested (10, 19)
>>> from sage.all import * >>> print((Integer(10), len([g for g in graphs(Integer(10),degree_sequence=[Integer(3)]*Integer(10)) if g.is_connected()]))) # not tested (10, 19)
Make sure that the graphs are really independent and the generator survives repeated vertex removal (Issue #8458):
sage: for G in graphs(3): ....: G.delete_vertex(0) ....: print(G.order()) 2 2 2 2
>>> from sage.all import * >>> for G in graphs(Integer(3)): ... G.delete_vertex(Integer(0)) ... print(G.order()) 2 2 2 2
REFERENCE:
Brendan D. McKay, Isomorph-Free Exhaustive generation. Journal of Algorithms, Volume 26, Issue 2, February 1998, pages 306-324.
- static AffineOrthogonalPolarGraph(d, q, sign='+')[source]#
Return the affine polar graph \(VO^+(d,q),VO^-(d,q)\) or \(VO(d,q)\).
Affine Polar graphs are built from a \(d\)-dimensional vector space over \(F_q\), and a quadratic form which is hyperbolic, elliptic or parabolic according to the value of
sign.Note that \(VO^+(d,q),VO^-(d,q)\) are strongly regular graphs, while \(VO(d,q)\) is not.
For more information on Affine Polar graphs, see Affine Polar Graphs page of Andries Brouwer’s website.
INPUT:
d– integer;dmust be even ifsign is not None, and odd otherwiseq– integer; a power of a prime number, as \(F_q\) must existsign– string (default:"+"); must be equal to"+","-", orNoneto compute (respectively) \(VO^+(d,q),VO^-(d,q)\) or \(VO(d,q)\)
Note
The graph \(VO^\epsilon(d,q)\) is the graph induced by the non-neighbors of a vertex in an
Orthogonal Polar Graph\(O^\epsilon(d+2,q)\).EXAMPLES:
The
Brouwer-Haemers graphis isomorphic to \(VO^-(4,3)\):sage: g = graphs.AffineOrthogonalPolarGraph(4,3,"-") # needs sage.libs.gap sage: g.is_isomorphic(graphs.BrouwerHaemersGraph()) # needs sage.libs.gap True
>>> from sage.all import * >>> g = graphs.AffineOrthogonalPolarGraph(Integer(4),Integer(3),"-") # needs sage.libs.gap >>> g.is_isomorphic(graphs.BrouwerHaemersGraph()) # needs sage.libs.gap True
Some examples from Brouwer’s table or strongly regular graphs:
sage: # needs sage.libs.gap sage: g = graphs.AffineOrthogonalPolarGraph(6,2,"-"); g Affine Polar Graph VO^-(6,2): Graph on 64 vertices sage: g.is_strongly_regular(parameters=True) (64, 27, 10, 12) sage: g = graphs.AffineOrthogonalPolarGraph(6,2,"+"); g Affine Polar Graph VO^+(6,2): Graph on 64 vertices sage: g.is_strongly_regular(parameters=True) (64, 35, 18, 20)
>>> from sage.all import * >>> # needs sage.libs.gap >>> g = graphs.AffineOrthogonalPolarGraph(Integer(6),Integer(2),"-"); g Affine Polar Graph VO^-(6,2): Graph on 64 vertices >>> g.is_strongly_regular(parameters=True) (64, 27, 10, 12) >>> g = graphs.AffineOrthogonalPolarGraph(Integer(6),Integer(2),"+"); g Affine Polar Graph VO^+(6,2): Graph on 64 vertices >>> g.is_strongly_regular(parameters=True) (64, 35, 18, 20)
When
sign is None:sage: # needs sage.libs.gap sage: g = graphs.AffineOrthogonalPolarGraph(5,2,None); g Affine Polar Graph VO^-(5,2): Graph on 32 vertices sage: g.is_strongly_regular(parameters=True) False sage: g.is_regular() True sage: g.is_vertex_transitive() True
>>> from sage.all import * >>> # needs sage.libs.gap >>> g = graphs.AffineOrthogonalPolarGraph(Integer(5),Integer(2),None); g Affine Polar Graph VO^-(5,2): Graph on 32 vertices >>> g.is_strongly_regular(parameters=True) False >>> g.is_regular() True >>> g.is_vertex_transitive() True
- static AfricaMap(continental=False, year=2018)[source]#
Return African states as a graph of common border.
“African state” here is defined as an independent state having the capital city in Africa. The graph has an edge between those countries that have common land border.
INPUT:
continental– boolean (default:False); whether to only return states in the continental Africa or all African statesyear– integer (default:2018); reserved for future use
EXAMPLES:
sage: Africa = graphs.AfricaMap(); Africa Africa Map: Graph on 54 vertices sage: sorted(Africa.neighbors('Libya')) ['Algeria', 'Chad', 'Egypt', 'Niger', 'Sudan', 'Tunisia'] sage: cont_Africa = graphs.AfricaMap(continental=True) sage: cont_Africa.order() 48 sage: 'Madagaskar' in cont_Africa False
>>> from sage.all import * >>> Africa = graphs.AfricaMap(); Africa Africa Map: Graph on 54 vertices >>> sorted(Africa.neighbors('Libya')) ['Algeria', 'Chad', 'Egypt', 'Niger', 'Sudan', 'Tunisia'] >>> cont_Africa = graphs.AfricaMap(continental=True) >>> cont_Africa.order() 48 >>> 'Madagaskar' in cont_Africa False
- static AhrensSzekeresGeneralizedQuadrangleGraph(q, dual=False)[source]#
Return the collinearity graph of the generalized quadrangle \(AS(q)\), or of its dual
Let \(q\) be an odd prime power. \(AS(q)\) is a generalized quadrangle (Wikipedia article Generalized_quadrangle) of order \((q-1,q+1)\), see 3.1.5 in [PT2009]. Its points are elements of \(F_q^3\), and lines are sets of size \(q\) of the form
\(\{ (\sigma, a, b) \mid \sigma\in F_q \}\)
\(\{ (a, \sigma, b) \mid \sigma\in F_q \}\)
\(\{ (c \sigma^2 - b \sigma + a, -2 c \sigma + b, \sigma) \mid \sigma\in F_q \}\),
where \(a\), \(b\), \(c\) are arbitrary elements of \(F_q\).
INPUT:
q– a power of an odd prime numberdual– boolean (default:False); whether to return the collinearity graph of \(AS(q)\) or of the dual \(AS(q)\) (whenTrue)
EXAMPLES:
sage: g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(5); g AS(5); GQ(4, 6): Graph on 125 vertices sage: g.is_strongly_regular(parameters=True) (125, 28, 3, 7) sage: g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(5, dual=True); g AS(5)*; GQ(6, 4): Graph on 175 vertices sage: g.is_strongly_regular(parameters=True) (175, 30, 5, 5)
>>> from sage.all import * >>> g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(Integer(5)); g AS(5); GQ(4, 6): Graph on 125 vertices >>> g.is_strongly_regular(parameters=True) (125, 28, 3, 7) >>> g = graphs.AhrensSzekeresGeneralizedQuadrangleGraph(Integer(5), dual=True); g AS(5)*; GQ(6, 4): Graph on 175 vertices >>> g.is_strongly_regular(parameters=True) (175, 30, 5, 5)
- static AlternatingFormsGraph(n, q)[source]#
Return the alternating forms graph with the given parameters.
This builds a graph whose vertices are all \(n`x`n\) skew-symmetric matrices over \(GF(q)\) with zero diagonal. Two vertices are adjacent if and only if the difference of the two matrices has rank 2.
This grap is distance-regular with classical parameters \((\lfloor \frac n 2 \rfloor, q^2, q^2 - 1, q^{2 \lceil \frac n 2 \rceil -1})\).
INPUT:
n– integerq– a prime power
EXAMPLES:
sage: G = graphs.AlternatingFormsGraph(5, 2) # long time sage: G.is_distance_regular(True) # long time ([155, 112, None], [None, 1, 20])
>>> from sage.all import * >>> G = graphs.AlternatingFormsGraph(Integer(5), Integer(2)) # long time >>> G.is_distance_regular(True) # long time ([155, 112, None], [None, 1, 20])
REFERENCES:
See [BCN1989] pp. 282-284 for a rather detailed discussion, otherwise see [VDKT2016] p. 22.
- static AztecDiamondGraph(n)[source]#
Return the Aztec Diamond graph of order
n.See the Wikipedia article Aztec_diamond for more information.
EXAMPLES:
sage: graphs.AztecDiamondGraph(2) Aztec Diamond graph of order 2 sage: [graphs.AztecDiamondGraph(i).num_verts() for i in range(8)] [0, 4, 12, 24, 40, 60, 84, 112] sage: [graphs.AztecDiamondGraph(i).num_edges() for i in range(8)] [0, 4, 16, 36, 64, 100, 144, 196] sage: G = graphs.AztecDiamondGraph(3) sage: sum(1 for p in G.perfect_matchings()) 64
>>> from sage.all import * >>> graphs.AztecDiamondGraph(Integer(2)) Aztec Diamond graph of order 2 >>> [graphs.AztecDiamondGraph(i).num_verts() for i in range(Integer(8))] [0, 4, 12, 24, 40, 60, 84, 112] >>> [graphs.AztecDiamondGraph(i).num_edges() for i in range(Integer(8))] [0, 4, 16, 36, 64, 100, 144, 196] >>> G = graphs.AztecDiamondGraph(Integer(3)) >>> sum(Integer(1) for p in G.perfect_matchings()) 64
- static Balaban10Cage(embedding=1)[source]#
Return the Balaban 10-cage.
The Balaban 10-cage is a 3-regular graph with 70 vertices and 105 edges. See the Wikipedia article Balaban_10-cage.
The default embedding gives a deeper understanding of the graph’s automorphism group. It is divided into 4 layers (each layer being a set of points at equal distance from the drawing’s center). From outside to inside:
L1: The outer layer (vertices which are the furthest from the origin) is actually the disjoint union of two cycles of length 10.
L2: The second layer is an independent set of 20 vertices.
L3: The third layer is a matching on 10 vertices.
L4: The inner layer (vertices which are the closest from the origin) is also the disjoint union of two cycles of length 10.
This graph is not vertex-transitive, and its vertices are partitioned into 3 orbits: L2, L3, and the union of L1 of L4 whose elements are equivalent.
INPUT:
embedding– integer (default:1); two embeddings are available, and can be selected by settingembeddingto be either 1 or 2
EXAMPLES:
sage: # needs networkx sage: g = graphs.Balaban10Cage() sage: g.girth() 10 sage: g.chromatic_number() 2 sage: g.diameter() 6 sage: g.is_hamiltonian() # needs sage.numerical.mip True sage: g.show(figsize=[10,10]) # long time # needs sage.plot
>>> from sage.all import * >>> # needs networkx >>> g = graphs.Balaban10Cage() >>> g.girth() 10 >>> g.chromatic_number() 2 >>> g.diameter() 6 >>> g.is_hamiltonian() # needs sage.numerical.mip True >>> g.show(figsize=[Integer(10),Integer(10)]) # long time # needs sage.plot
- static Balaban11Cage(embedding=1)[source]#
Return the Balaban 11-cage.
For more information, see the Wikipedia article Balaban_11-cage.
INPUT:
embedding– integer (default:1); three embeddings are available, and can be selected by settingembeddingto be 1, 2, or 3The first embedding is the one appearing on page 9 of the Fifth Annual Graph Drawing Contest report [EMMN1998]. It separates vertices based on their eccentricity (see
eccentricity()).The second embedding has been produced just for Sage and is meant to emphasize the automorphism group’s 6 orbits.
The last embedding is the default one produced by the
LCFGraph()constructor.
Note
The vertex labeling changes according to the value of
embedding=1.EXAMPLES:
Basic properties:
sage: g = graphs.Balaban11Cage() sage: g.order() 112 sage: g.size() 168 sage: g.girth() 11 sage: g.diameter() 8 sage: g.automorphism_group().cardinality() # needs sage.groups 64
>>> from sage.all import * >>> g = graphs.Balaban11Cage() >>> g.order() 112 >>> g.size() 168 >>> g.girth() 11 >>> g.diameter() 8 >>> g.automorphism_group().cardinality() # needs sage.groups 64
Our many embeddings:
sage: g1 = graphs.Balaban11Cage(embedding=1) sage: g2 = graphs.Balaban11Cage(embedding=2) # needs networkx sage: g3 = graphs.Balaban11Cage(embedding=3) # needs networkx sage: g1.show(figsize=[10,10]) # long time # needs sage.plot sage: g2.show(figsize=[10,10]) # long time # needs networkx sage.plot sage: g3.show(figsize=[10,10]) # long time # needs networkx sage.plot
>>> from sage.all import * >>> g1 = graphs.Balaban11Cage(embedding=Integer(1)) >>> g2 = graphs.Balaban11Cage(embedding=Integer(2)) # needs networkx >>> g3 = graphs.Balaban11Cage(embedding=Integer(3)) # needs networkx >>> g1.show(figsize=[Integer(10),Integer(10)]) # long time # needs sage.plot >>> g2.show(figsize=[Integer(10),Integer(10)]) # long time # needs networkx sage.plot >>> g3.show(figsize=[Integer(10),Integer(10)]) # long time # needs networkx sage.plot
Proof that the embeddings are the same graph:
sage: g1.is_isomorphic(g2) # g2 and g3 are obviously isomorphic # needs networkx True
>>> from sage.all import * >>> g1.is_isomorphic(g2) # g2 and g3 are obviously isomorphic # needs networkx True
- static BalancedTree(r, h)[source]#
Return the perfectly balanced tree of height \(h \geq 1\), whose root has degree \(r \geq 2\).
The number of vertices of this graph is \(1 + r + r^2 + \cdots + r^h\), that is, \(\frac{r^{h+1} - 1}{r - 1}\). The number of edges is one less than the number of vertices.
INPUT:
r– positive integer \(\geq 2\). The degree of the root node.h– positive integer \(\geq 1\). The height of the balanced tree.
OUTPUT:
The perfectly balanced tree of height \(h \geq 1\) and whose root has degree \(r \geq 2\).
EXAMPLES:
A balanced tree whose root node has degree \(r = 2\), and of height \(h = 1\), has order 3 and size 2:
sage: G = graphs.BalancedTree(2, 1); G Balanced tree: Graph on 3 vertices sage: G.order() 3 sage: G.size() 2 sage: r = 2; h = 1 sage: v = 1 + r sage: v; v - 1 3 2
>>> from sage.all import * >>> G = graphs.BalancedTree(Integer(2), Integer(1)); G Balanced tree: Graph on 3 vertices >>> G.order() 3 >>> G.size() 2 >>> r = Integer(2); h = Integer(1) >>> v = Integer(1) + r >>> v; v - Integer(1) 3 2
Plot a balanced tree of height 5, whose root node has degree \(r = 3\):
sage: G = graphs.BalancedTree(3, 5) sage: G.plot() # long time # needs sage.plot Graphics object consisting of 728 graphics primitives
>>> from sage.all import * >>> G = graphs.BalancedTree(Integer(3), Integer(5)) >>> G.plot() # long time # needs sage.plot Graphics object consisting of 728 graphics primitives
A tree is bipartite. If its vertex set is finite, then it is planar.
sage: # needs networkx sage: r = randint(2, 5); h = randint(1, 7) sage: T = graphs.BalancedTree(r, h) sage: T.is_bipartite() True sage: T.is_planar() True sage: v = (r^(h + 1) - 1) / (r - 1) sage: T.order() == v True sage: T.size() == v - 1 True
>>> from sage.all import * >>> # needs networkx >>> r = randint(Integer(2), Integer(5)); h = randint(Integer(1), Integer(7)) >>> T = graphs.BalancedTree(r, h) >>> T.is_bipartite() True >>> T.is_planar() True >>> v = (r**(h + Integer(1)) - Integer(1)) / (r - Integer(1)) >>> T.order() == v True >>> T.size() == v - Integer(1) True
- static BarbellGraph(n1, n2)[source]#
Returns a barbell graph with \(2*n_1 + n_2\) nodes.
The argument \(n_1\) must be greater than or equal to 2.
A barbell graph is a basic structure that consists of a path graph of order \(n_2\) connecting two complete graphs of order \(n_1\) each.
INPUT:
n1– integer \(\geq 2\). The order of each of the two complete graphs.n2– nonnegative integer. The order of the path graph connecting the two complete graphs.
OUTPUT:
A barbell graph of order \(2*n_1 + n_2\). A
ValueErroris returned if \(n_1 < 2\) or \(n_2 < 0\).PLOTTING:
Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each barbell graph will be displayed with the two complete graphs in the lower-left and upper-right corners, with the path graph connecting diagonally between the two. Thus the \(n_1\)-th node will be drawn at a 45 degree angle from the horizontal right center of the first complete graph, and the \(n_1 + n_2 + 1\)-th node will be drawn 45 degrees below the left horizontal center of the second complete graph.
EXAMPLES:
Construct and show a barbell graph
Bar = 4,Bells = 9:sage: g = graphs.BarbellGraph(9, 4); g Barbell graph: Graph on 22 vertices sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.BarbellGraph(Integer(9), Integer(4)); g Barbell graph: Graph on 22 vertices >>> g.show() # long time # needs sage.plot
An \(n_1 \geq 2\), \(n_2 \geq 0\) barbell graph has order \(2*n_1 + n_2\). It has the complete graph on \(n_1\) vertices as a subgraph. It also has the path graph on \(n_2\) vertices as a subgraph.
sage: n1 = randint(2, 2*10^2) sage: n2 = randint(0, 2*10^2) sage: g = graphs.BarbellGraph(n1, n2) sage: v = 2*n1 + n2 sage: g.order() == v True sage: K_n1 = graphs.CompleteGraph(n1) sage: P_n2 = graphs.PathGraph(n2) sage: # needs sage.modules sage: s_K = g.subgraph_search(K_n1, induced=True) sage: s_P = g.subgraph_search(P_n2, induced=True) sage: K_n1.is_isomorphic(s_K) True sage: P_n2.is_isomorphic(s_P) True
>>> from sage.all import * >>> n1 = randint(Integer(2), Integer(2)*Integer(10)**Integer(2)) >>> n2 = randint(Integer(0), Integer(2)*Integer(10)**Integer(2)) >>> g = graphs.BarbellGraph(n1, n2) >>> v = Integer(2)*n1 + n2 >>> g.order() == v True >>> K_n1 = graphs.CompleteGraph(n1) >>> P_n2 = graphs.PathGraph(n2) >>> # needs sage.modules >>> s_K = g.subgraph_search(K_n1, induced=True) >>> s_P = g.subgraph_search(P_n2, induced=True) >>> K_n1.is_isomorphic(s_K) True >>> P_n2.is_isomorphic(s_P) True
- static BidiakisCube()[source]#
Return the Bidiakis cube.
For more information, see the Wikipedia article Bidiakis_cube.
EXAMPLES:
The Bidiakis cube is a 3-regular graph having 12 vertices and 18 edges. This means that each vertex has a degree of 3:
sage: g = graphs.BidiakisCube(); g Bidiakis cube: Graph on 12 vertices sage: g.show() # long time # needs sage.plot sage: g.order() 12 sage: g.size() 18 sage: g.is_regular(3) True
>>> from sage.all import * >>> g = graphs.BidiakisCube(); g Bidiakis cube: Graph on 12 vertices >>> g.show() # long time # needs sage.plot >>> g.order() 12 >>> g.size() 18 >>> g.is_regular(Integer(3)) True
It is a Hamiltonian graph with diameter 3 and girth 4:
sage: g.is_hamiltonian() # needs sage.numerical.mip True sage: g.diameter() 3 sage: g.girth() 4
>>> from sage.all import * >>> g.is_hamiltonian() # needs sage.numerical.mip True >>> g.diameter() 3 >>> g.girth() 4
It is a planar graph with characteristic polynomial \((x - 3) (x - 2) (x^4) (x + 1) (x + 2) (x^2 + x - 4)^2\) and chromatic number 3:
sage: g.is_planar() True sage: char_poly = g.characteristic_polynomial() # needs sage.modules sage: x = char_poly.parent()('x') # needs sage.modules sage: char_poly == (x - 3) * (x - 2) * (x^4) * (x + 1) * (x + 2) * (x^2 + x - 4)^2 # needs sage.modules True sage: g.chromatic_number() # needs sage.modules 3
>>> from sage.all import * >>> g.is_planar() True >>> char_poly = g.characteristic_polynomial() # needs sage.modules >>> x = char_poly.parent()('x') # needs sage.modules >>> char_poly == (x - Integer(3)) * (x - Integer(2)) * (x**Integer(4)) * (x + Integer(1)) * (x + Integer(2)) * (x**Integer(2) + x - Integer(4))**Integer(2) # needs sage.modules True >>> g.chromatic_number() # needs sage.modules 3
- static BiggsSmithGraph(embedding=1)[source]#
Return the Biggs-Smith graph.
For more information, see the Wikipedia article Biggs-Smith_graph.
INPUT:
embedding– integer (default:1); two embeddings are available, and can be selected by settingembeddingto be 1 or 2
EXAMPLES:
Basic properties:
sage: # needs networkx sage: g = graphs.BiggsSmithGraph() sage: g.order() 102 sage: g.size() 153 sage: g.girth() 9 sage: g.diameter() 7 sage: g.automorphism_group().cardinality() # long time 2448 sage: g.show(figsize=[10, 10]) # long time # needs sage.plot
>>> from sage.all import * >>> # needs networkx >>> g = graphs.BiggsSmithGraph() >>> g.order() 102 >>> g.size() 153 >>> g.girth() 9 >>> g.diameter() 7 >>> g.automorphism_group().cardinality() # long time 2448 >>> g.show(figsize=[Integer(10), Integer(10)]) # long time # needs sage.plot
The other embedding:
sage: graphs.BiggsSmithGraph(embedding=2).show() # long time # needs networkx
>>> from sage.all import * >>> graphs.BiggsSmithGraph(embedding=Integer(2)).show() # long time # needs networkx
- static BilinearFormsGraph(d, e, q)[source]#
Return a bilinear forms graph with the given parameters.
This builds a graph whose vertices are all \(d`x`e\) matrices over \(GF(q)\). Two vertices are adjacent if the difference of the two matrices has rank 1.
The graph is distance-regular with classical parameters \((\min(d, e), q, q-1 , q^{\max(d, e)}-1)\).
INPUT:
d,e– integers; dimension of the matricesq– integer; a prime power
EXAMPLES:
sage: # needs sage.modules sage: G = graphs.BilinearFormsGraph(3, 3, 2) sage: G.is_distance_regular(True) ([49, 36, 16, None], [None, 1, 6, 28]) sage: G = graphs.BilinearFormsGraph(3,3,3) # not tested (20 s) # needs sage.rings.finite_rings sage: G.order() # not tested (due to above) # needs sage.rings.finite_rings 19683 sage: G = graphs.BilinearFormsGraph(3, 4, 2) # long time # needs sage.rings.finite_rings sage: G.is_distance_regular(True) # long time # needs sage.rings.finite_rings ([105, 84, 48, None], [None, 1, 6, 28])
>>> from sage.all import * >>> # needs sage.modules >>> G = graphs.BilinearFormsGraph(Integer(3), Integer(3), Integer(2)) >>> G.is_distance_regular(True) ([49, 36, 16, None], [None, 1, 6, 28]) >>> G = graphs.BilinearFormsGraph(Integer(3),Integer(3),Integer(3)) # not tested (20 s) # needs sage.rings.finite_rings >>> G.order() # not tested (due to above) # needs sage.rings.finite_rings 19683 >>> G = graphs.BilinearFormsGraph(Integer(3), Integer(4), Integer(2)) # long time # needs sage.rings.finite_rings >>> G.is_distance_regular(True) # long time # needs sage.rings.finite_rings ([105, 84, 48, None], [None, 1, 6, 28])
REFERENCES:
See [BCN1989] pp. 280-282 for a rather detailed discussion, otherwise see [VDKT2016] p. 21.
- static BishopGraph(dim_list, radius=None, relabel=False)[source]#
Return the \(d\)-dimensional Bishop Graph with prescribed dimensions.
The 2-dimensional Bishop Graph of parameters \(n\) and \(m\) is a graph with \(nm\) vertices in which each vertex represents a square in an \(n \times m\) chessboard, and each edge corresponds to a legal move by a bishop.
The \(d\)-dimensional Bishop Graph with \(d >= 2\) has for vertex set the cells of a \(d\)-dimensional grid with prescribed dimensions, and each edge corresponds to a legal move by a bishop in any pairs of dimensions.
The Bishop Graph is not connected.
INPUT:
dim_list– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardradius– integer (default:None); by setting the radius to a positive integer, one may decrease the power of the bishop to at mostradiussteps.relabel– boolean (default:False); indicates whether the vertices must be relabeled as integers
EXAMPLES:
The (n,m)-Bishop Graph is not connected:
sage: G = graphs.BishopGraph( [3, 4] ) sage: G.is_connected() False
>>> from sage.all import * >>> G = graphs.BishopGraph( [Integer(3), Integer(4)] ) >>> G.is_connected() False
The Bishop Graph can be obtained from Knight Graphs:
sage: for d in range(3,12): # long time ....: H = Graph() ....: for r in range(1,d+1): ....: B = graphs.BishopGraph([d,d],radius=r) ....: H.add_edges( graphs.KnightGraph([d,d],one=r,two=r).edges(sort=False) ) ....: if not B.is_isomorphic(H): ....: print("that's not good!")
>>> from sage.all import * >>> for d in range(Integer(3),Integer(12)): # long time ... H = Graph() ... for r in range(Integer(1),d+Integer(1)): ... B = graphs.BishopGraph([d,d],radius=r) ... H.add_edges( graphs.KnightGraph([d,d],one=r,two=r).edges(sort=False) ) ... if not B.is_isomorphic(H): ... print("that's not good!")
- static BlanusaFirstSnarkGraph()[source]#
Return the first Blanusa Snark Graph.
The Blanusa graphs are two snarks on 18 vertices and 27 edges. For more information on them, see the Wikipedia article Blanusa_snarks.
See also
EXAMPLES:
sage: g = graphs.BlanusaFirstSnarkGraph() sage: g.order() 18 sage: g.size() 27 sage: g.diameter() 4 sage: g.girth() 5 sage: g.automorphism_group().cardinality() # needs sage.groups 8
>>> from sage.all import * >>> g = graphs.BlanusaFirstSnarkGraph() >>> g.order() 18 >>> g.size() 27 >>> g.diameter() 4 >>> g.girth() 5 >>> g.automorphism_group().cardinality() # needs sage.groups 8
- static BlanusaSecondSnarkGraph()[source]#
Return the second Blanusa Snark Graph.
The Blanusa graphs are two snarks on 18 vertices and 27 edges. For more information on them, see the Wikipedia article Blanusa_snarks.
See also
EXAMPLES:
sage: g = graphs.BlanusaSecondSnarkGraph() sage: g.order() 18 sage: g.size() 27 sage: g.diameter() 4 sage: g.girth() 5 sage: g.automorphism_group().cardinality() # needs sage.groups 4
>>> from sage.all import * >>> g = graphs.BlanusaSecondSnarkGraph() >>> g.order() 18 >>> g.size() 27 >>> g.diameter() 4 >>> g.girth() 5 >>> g.automorphism_group().cardinality() # needs sage.groups 4
- static BrinkmannGraph()[source]#
Return the Brinkmann graph.
For more information, see the Wikipedia article Brinkmann_graph.
EXAMPLES:
The Brinkmann graph is a 4-regular graph having 21 vertices and 42 edges. This means that each vertex has degree 4:
sage: G = graphs.BrinkmannGraph(); G Brinkmann graph: Graph on 21 vertices sage: G.show() # long time # needs sage.plot sage: G.order() 21 sage: G.size() 42 sage: G.is_regular(4) True
>>> from sage.all import * >>> G = graphs.BrinkmannGraph(); G Brinkmann graph: Graph on 21 vertices >>> G.show() # long time # needs sage.plot >>> G.order() 21 >>> G.size() 42 >>> G.is_regular(Integer(4)) True
It is an Eulerian graph with radius 3, diameter 3, and girth 5:
sage: G.is_eulerian() True sage: G.radius() 3 sage: G.diameter() 3 sage: G.girth() 5
>>> from sage.all import * >>> G.is_eulerian() True >>> G.radius() 3 >>> G.diameter() 3 >>> G.girth() 5
The Brinkmann graph is also Hamiltonian with chromatic number 4:
sage: G.is_hamiltonian() # needs sage.numerical.mip True sage: G.chromatic_number() 4
>>> from sage.all import * >>> G.is_hamiltonian() # needs sage.numerical.mip True >>> G.chromatic_number() 4
Its automorphism group is isomorphic to \(D_7\):
sage: ag = G.automorphism_group() # needs sage.groups sage: ag.is_isomorphic(DihedralGroup(7)) # needs sage.groups True
>>> from sage.all import * >>> ag = G.automorphism_group() # needs sage.groups >>> ag.is_isomorphic(DihedralGroup(Integer(7))) # needs sage.groups True
- static BrouwerHaemersGraph()[source]#
Return the Brouwer-Haemers Graph.
The Brouwer-Haemers is the only strongly regular graph of parameters \((81,20,1,6)\). It is build in Sage as the Affine Orthogonal graph \(VO^-(6,3)\). For more information on this graph, see its corresponding page on Andries Brouwer’s website.
EXAMPLES:
sage: g = graphs.BrouwerHaemersGraph(); g # needs sage.modules Brouwer-Haemers: Graph on 81 vertices
>>> from sage.all import * >>> g = graphs.BrouwerHaemersGraph(); g # needs sage.modules Brouwer-Haemers: Graph on 81 vertices
It is indeed strongly regular with parameters \((81,20,1,6)\):
sage: g.is_strongly_regular(parameters=True) # long time # needs sage.modules sage.rings.finite_rings (81, 20, 1, 6)
>>> from sage.all import * >>> g.is_strongly_regular(parameters=True) # long time # needs sage.modules sage.rings.finite_rings (81, 20, 1, 6)
Its has as eigenvalues \(20,2\) and \(-7\):
sage: set(g.spectrum()) == {20,2,-7} # needs sage.modules sage.rings.finite_rings True
>>> from sage.all import * >>> set(g.spectrum()) == {Integer(20),Integer(2),-Integer(7)} # needs sage.modules sage.rings.finite_rings True
- static BubbleSortGraph(n)[source]#
Returns the bubble sort graph \(B(n)\).
The vertices of the bubble sort graph are the set of permutations on \(n\) symbols. Two vertices are adjacent if one can be obtained from the other by swapping the labels in the \(i\)-th and \((i+1)\)-th positions for \(1 \leq i \leq n-1\). In total, \(B(n)\) has order \(n!\). Swapping two labels as described previously corresponds to multiplying on the right the permutation corresponding to the node by an elementary transposition in the
SymmetricGroup.The bubble sort graph is the underlying graph of the
permutahedron().INPUT:
n– positive integer. The number of symbols to permute.
OUTPUT:
The bubble sort graph \(B(n)\) on \(n\) symbols. If \(n < 1\), a
ValueErroris returned.EXAMPLES:
sage: g = graphs.BubbleSortGraph(4); g Bubble sort: Graph on 24 vertices sage: g.plot() # long time # needs sage.plot Graphics object consisting of 61 graphics primitives
>>> from sage.all import * >>> g = graphs.BubbleSortGraph(Integer(4)); g Bubble sort: Graph on 24 vertices >>> g.plot() # long time # needs sage.plot Graphics object consisting of 61 graphics primitives
The bubble sort graph on \(n = 1\) symbol is the trivial graph \(K_1\):
sage: graphs.BubbleSortGraph(1) Bubble sort: Graph on 1 vertex
>>> from sage.all import * >>> graphs.BubbleSortGraph(Integer(1)) Bubble sort: Graph on 1 vertex
If \(n \geq 1\), then the order of \(B(n)\) is \(n!\):
sage: n = randint(1, 8) sage: g = graphs.BubbleSortGraph(n) sage: g.order() == factorial(n) True
>>> from sage.all import * >>> n = randint(Integer(1), Integer(8)) >>> g = graphs.BubbleSortGraph(n) >>> g.order() == factorial(n) True
See also
AUTHORS:
Michael Yurko (2009-09-01)
- static BuckyBall()[source]#
Return the Bucky Ball graph.
This graph is a 3-regular 60-vertex planar graph. Its vertices and edges correspond precisely to the carbon atoms and bonds in buckminsterfullerene. When embedded on a sphere, its 12 pentagon and 20 hexagon faces are arranged exactly as the sections of a soccer ball.
EXAMPLES:
The Bucky Ball is planar:
sage: g = graphs.BuckyBall() sage: g.is_planar() True
>>> from sage.all import * >>> g = graphs.BuckyBall() >>> g.is_planar() True
The Bucky Ball can also be created by extracting the 1-skeleton of the Bucky Ball polyhedron, but this is much slower:
sage: # needs sage.geometry.polyhedron sage.groups sage.rings.number_field sage: g = polytopes.buckyball().vertex_graph() sage: g.remove_loops() sage: h = graphs.BuckyBall() sage: g.is_isomorphic(h) True
>>> from sage.all import * >>> # needs sage.geometry.polyhedron sage.groups sage.rings.number_field >>> g = polytopes.buckyball().vertex_graph() >>> g.remove_loops() >>> h = graphs.BuckyBall() >>> g.is_isomorphic(h) True
The graph is returned along with an attractive embedding:
sage: g = graphs.BuckyBall() # long time sage: g.plot(vertex_labels=False, vertex_size=10).show() # long time, needs sage.plot
>>> from sage.all import * >>> g = graphs.BuckyBall() # long time >>> g.plot(vertex_labels=False, vertex_size=Integer(10)).show() # long time, needs sage.plot
- static BullGraph()[source]#
Return a bull graph with 5 nodes.
A bull graph is named for its shape. It’s a triangle with horns. See the Wikipedia article Bull_graph for more information.
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(); g Bull graph: Graph on 5 vertices sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.BullGraph(); g Bull graph: Graph on 5 vertices >>> g.show() # long time # needs sage.plot
The bull graph has 5 vertices and 5 edges. Its radius is 2, its diameter 3, and its girth 3. The bull graph is planar with chromatic number 3 and chromatic index also 3:
sage: g.order(); g.size() 5 5 sage: g.radius(); g.diameter(); g.girth() 2 3 3 sage: g.chromatic_number() 3
>>> from sage.all import * >>> g.order(); g.size() 5 5 >>> g.radius(); g.diameter(); g.girth() 2 3 3 >>> g.chromatic_number() 3
The bull graph has chromatic polynomial \(x(x - 2)(x - 1)^3\) and Tutte polynomial \(x^4 + x^3 + x^2 y\). Its characteristic polynomial is \(x(x^2 - x - 3)(x^2 + x - 1)\), which follows from the definition of characteristic polynomials for graphs, i.e. \(\det(xI - A)\), where \(x\) is a variable, \(A\) the adjacency matrix of the graph, and \(I\) the identity matrix of the same dimensions as \(A\):
sage: # needs sage.libs.flint sage: chrompoly = g.chromatic_polynomial() sage: x = chrompoly.parent()('x') sage: x * (x - 2) * (x - 1)^3 == chrompoly True sage: # needs sage.libs.flint sage.modules sage: charpoly = g.characteristic_polynomial() sage: M = g.adjacency_matrix(); M [0 1 1 0 0] [1 0 1 1 0] [1 1 0 0 1] [0 1 0 0 0] [0 0 1 0 0] sage: Id = identity_matrix(ZZ, M.nrows()) sage: D = x*Id - M sage: D.determinant() == charpoly # needs sage.symbolic True sage: x * (x^2 - x - 3) * (x^2 + x - 1) == charpoly True
>>> from sage.all import * >>> # needs sage.libs.flint >>> chrompoly = g.chromatic_polynomial() >>> x = chrompoly.parent()('x') >>> x * (x - Integer(2)) * (x - Integer(1))**Integer(3) == chrompoly True >>> # needs sage.libs.flint sage.modules >>> charpoly = g.characteristic_polynomial() >>> M = g.adjacency_matrix(); M [0 1 1 0 0] [1 0 1 1 0] [1 1 0 0 1] [0 1 0 0 0] [0 0 1 0 0] >>> Id = identity_matrix(ZZ, M.nrows()) >>> D = x*Id - M >>> D.determinant() == charpoly # needs sage.symbolic True >>> x * (x**Integer(2) - x - Integer(3)) * (x**Integer(2) + x - Integer(1)) == charpoly True
- static ButterflyGraph()[source]#
Return the butterfly graph.
Let \(C_3\) be the cycle graph on 3 vertices. The butterfly or bowtie graph is obtained by joining two copies of \(C_3\) at a common vertex, resulting in a graph that is isomorphic to the friendship graph \(F_2\). See the Wikipedia article Butterfly_graph for more information.
See also
EXAMPLES:
The butterfly graph is a planar graph on 5 vertices and having 6 edges:
sage: G = graphs.ButterflyGraph(); G Butterfly graph: Graph on 5 vertices sage: G.show() # long time # needs sage.plot sage: G.is_planar() True sage: G.order() 5 sage: G.size() 6
>>> from sage.all import * >>> G = graphs.ButterflyGraph(); G Butterfly graph: Graph on 5 vertices >>> G.show() # long time # needs sage.plot >>> G.is_planar() True >>> G.order() 5 >>> G.size() 6
It has diameter 2, girth 3, and radius 1:
sage: G.diameter() 2 sage: G.girth() 3 sage: G.radius() 1
>>> from sage.all import * >>> G.diameter() 2 >>> G.girth() 3 >>> G.radius() 1
The butterfly graph is Eulerian, with chromatic number 3:
sage: G.is_eulerian() True sage: G.chromatic_number() 3
>>> from sage.all import * >>> G.is_eulerian() True >>> G.chromatic_number() 3
- static CaiFurerImmermanGraph(G, twisted=False)[source]#
Return the a Cai-Furer-Immerman graph from \(G\), possibly a twisted one, and a partition of its nodes.
A Cai-Furer-Immerman graph from/on \(G\) is a graph created by applying the transformation described in [CFI1992] on a graph \(G\), that is substituting every vertex v in \(G\) with a Furer gadget \(F(v)\) of order d equal to the degree of the vertex, and then substituting every edge \((v,u)\) in \(G\) with a pair of edges, one connecting the two “a” nodes of \(F(v)\) and \(F(u)\) and the other their two “b” nodes. The returned coloring of the vertices is made by the union of the colorings of each single Furer gadget, individualised for each vertex of \(G\). To understand better what these “a” and “b” nodes are, see the documentation on Furer gadgets.
Furthermore, this method can apply what is described in the paper mentioned above as a “twist” on an edge, that is taking only one of the pairs of edges introduced in the new graph and swap two of their extremes, making each edge go from an “a” node to a “b” node. This is only doable if the original graph G is connected.
A CaiFurerImmerman graph on a graph with no balanced vertex separators smaller than s and its twisted version cannot be distinguished by k-WL for any k < s.
INPUT:
G– An undirected graph on which to construct theCai-Furer-Immerman graph
twisted– A boolean indicating if the version to constructis a twisted one or not
OUTPUT:
H– The Cai-Furer-Immerman graph onGcoloring– A list of list of vertices, representing thepartition induced by the coloring on
H
EXAMPLES:
CaiFurerImmerman graph with no balanced vertex separator smaller than 2
sage: G = graphs.CycleGraph(4) sage: CFI, p = graphs.CaiFurerImmermanGraph(G) sage: sorted(CFI, key=str) [(0, ()), (0, (0, 'a')), (0, (0, 'b')), (0, (0, 1)), (0, (1, 'a')), (0, (1, 'b')), (1, ()), (1, (0, 'a')), (1, (0, 'b')), (1, (0, 1)), (1, (1, 'a')), (1, (1, 'b')), (2, ()), (2, (0, 'a')), (2, (0, 'b')), (2, (0, 1)), (2, (1, 'a')), (2, (1, 'b')), (3, ()), (3, (0, 'a')), (3, (0, 'b')), (3, (0, 1)), (3, (1, 'a')), (3, (1, 'b'))] sage: sorted(CFI.edge_iterator(), key=str) [((0, ()), (0, (0, 'b')), None), ((0, ()), (0, (1, 'b')), None), ((0, (0, 'a')), (1, (0, 'a')), None), ((0, (0, 'b')), (1, (0, 'b')), None), ((0, (0, 1)), (0, (0, 'a')), None), ((0, (0, 1)), (0, (1, 'a')), None), ((0, (1, 'a')), (3, (0, 'a')), None), ((0, (1, 'b')), (3, (0, 'b')), None), ((1, ()), (1, (0, 'b')), None), ((1, ()), (1, (1, 'b')), None), ((1, (0, 1)), (1, (0, 'a')), None), ((1, (0, 1)), (1, (1, 'a')), None), ((1, (1, 'a')), (2, (0, 'a')), None), ((1, (1, 'b')), (2, (0, 'b')), None), ((2, ()), (2, (0, 'b')), None), ((2, ()), (2, (1, 'b')), None), ((2, (0, 1)), (2, (0, 'a')), None), ((2, (0, 1)), (2, (1, 'a')), None), ((2, (1, 'a')), (3, (1, 'a')), None), ((2, (1, 'b')), (3, (1, 'b')), None), ((3, ()), (3, (0, 'b')), None), ((3, ()), (3, (1, 'b')), None), ((3, (0, 1)), (3, (0, 'a')), None), ((3, (0, 1)), (3, (1, 'a')), None)]
>>> from sage.all import * >>> G = graphs.CycleGraph(Integer(4)) >>> CFI, p = graphs.CaiFurerImmermanGraph(G) >>> sorted(CFI, key=str) [(0, ()), (0, (0, 'a')), (0, (0, 'b')), (0, (0, 1)), (0, (1, 'a')), (0, (1, 'b')), (1, ()), (1, (0, 'a')), (1, (0, 'b')), (1, (0, 1)), (1, (1, 'a')), (1, (1, 'b')), (2, ()), (2, (0, 'a')), (2, (0, 'b')), (2, (0, 1)), (2, (1, 'a')), (2, (1, 'b')), (3, ()), (3, (0, 'a')), (3, (0, 'b')), (3, (0, 1)), (3, (1, 'a')), (3, (1, 'b'))] >>> sorted(CFI.edge_iterator(), key=str) [((0, ()), (0, (0, 'b')), None), ((0, ()), (0, (1, 'b')), None), ((0, (0, 'a')), (1, (0, 'a')), None), ((0, (0, 'b')), (1, (0, 'b')), None), ((0, (0, 1)), (0, (0, 'a')), None), ((0, (0, 1)), (0, (1, 'a')), None), ((0, (1, 'a')), (3, (0, 'a')), None), ((0, (1, 'b')), (3, (0, 'b')), None), ((1, ()), (1, (0, 'b')), None), ((1, ()), (1, (1, 'b')), None), ((1, (0, 1)), (1, (0, 'a')), None), ((1, (0, 1)), (1, (1, 'a')), None), ((1, (1, 'a')), (2, (0, 'a')), None), ((1, (1, 'b')), (2, (0, 'b')), None), ((2, ()), (2, (0, 'b')), None), ((2, ()), (2, (1, 'b')), None), ((2, (0, 1)), (2, (0, 'a')), None), ((2, (0, 1)), (2, (1, 'a')), None), ((2, (1, 'a')), (3, (1, 'a')), None), ((2, (1, 'b')), (3, (1, 'b')), None), ((3, ()), (3, (0, 'b')), None), ((3, ()), (3, (1, 'b')), None), ((3, (0, 1)), (3, (0, 'a')), None), ((3, (0, 1)), (3, (1, 'a')), None)]
- static CameronGraph()[source]#
Return the Cameron graph.
The Cameron graph is strongly regular with parameters \(v = 231, k = 30, \lambda = 9, \mu = 3\).
For more information on the Cameron graph, see https://www.win.tue.nl/~aeb/graphs/Cameron.html.
EXAMPLES:
sage: # needs sage.groups sage: g = graphs.CameronGraph() sage: g.order() 231 sage: g.size() 3465 sage: g.is_strongly_regular(parameters=True) # long time (231, 30, 9, 3)
>>> from sage.all import * >>> # needs sage.groups >>> g = graphs.CameronGraph() >>> g.order() 231 >>> g.size() 3465 >>> g.is_strongly_regular(parameters=True) # long time (231, 30, 9, 3)
- static Cell120()[source]#
Return the 120-Cell graph.
This is the adjacency graph of the 120-cell. It has 600 vertices and 1200 edges. For more information, see the Wikipedia article 120-cell.
EXAMPLES:
sage: # long time, needs sage.rings.number_field sage: g = graphs.Cell120() sage: g.size() 1200 sage: g.is_regular(4) True sage: g.is_vertex_transitive() True
>>> from sage.all import * >>> # long time, needs sage.rings.number_field >>> g = graphs.Cell120() >>> g.size() 1200 >>> g.is_regular(Integer(4)) True >>> g.is_vertex_transitive() True
- static Cell600(embedding=1)[source]#
Return the 600-Cell graph.
This is the adjacency graph of the 600-cell. It has 120 vertices and 720 edges. For more information, see the Wikipedia article 600-cell.
INPUT:
embedding– integer (default:1); two different embeddings for a plot
EXAMPLES:
sage: # long time, needs sage.rings.number_field sage: g = graphs.Cell600() sage: g.size() 720 sage: g.is_regular(12) True sage: g.is_vertex_transitive() True
>>> from sage.all import * >>> # long time, needs sage.rings.number_field >>> g = graphs.Cell600() >>> g.size() 720 >>> g.is_regular(Integer(12)) True >>> g.is_vertex_transitive() True
- static ChessboardGraphGenerator(dim_list, rook=True, rook_radius=None, bishop=True, bishop_radius=None, knight=True, knight_x=1, knight_y=2, relabel=False)[source]#
Return a Graph built on a \(d\)-dimensional chessboard with prescribed dimensions and interconnections.
This function allows to generate many kinds of graphs corresponding to legal movements on a \(d\)-dimensional chessboard: Queen Graph, King Graph, Knight Graphs, Bishop Graph, and many generalizations. It also allows to avoid redundant code.
INPUT:
dim_list– iterable (list, set, dict); provides the dimensions \(n_1, n_2, \ldots, n_d\), with \(n_i \geq 1\), of the chessboardrook– boolean (default:True); indicates whether the chess piece is able to move as a rook, that is at any distance along a dimensionrook_radius– integer (default:None); restriction on the rook-like movements to distance at mostrook_radiusbishop– boolean (default:True); indicates whether the chess piece is able to move like a bishop, that is along diagonalsbishop_radius– integer (default:None); restriction on the bishop-like movements to distance at mostbishop_radiusknight– boolean (default:True); indicating whether the chess piece is able to move like a knightknight_x– integer (default:1); indicates the number on steps the chess piece moves in one dimension when moving like a knightknight_y– integer (default:2); indicates the number on steps the chess piece moves in the second dimension when moving like a knightrelabel– boolean (default:False); indicates whether the vertices must be relabeled as integers
OUTPUT:
A Graph build on a \(d\)-dimensional chessboard with prescribed dimensions, and with edges according given parameters.
A string encoding the dimensions. This is mainly useful for providing names to graphs.
EXAMPLES:
A \((2,2)\)-King Graph is isomorphic to the complete graph on 4 vertices:
sage: G, _ = graphs.ChessboardGraphGenerator( [2,2] ) sage: G.is_isomorphic( graphs.CompleteGraph(4) ) True
>>> from sage.all import * >>> G, _ = graphs.ChessboardGraphGenerator( [Integer(2),Integer(2)] ) >>> G.is_isomorphic( graphs.CompleteGraph(Integer(4)) ) True
A Rook’s Graph in 2 dimensions is isomorphic to the Cartesian product of 2 complete graphs:
sage: G, _ = graphs.ChessboardGraphGenerator([3,4], rook=True, rook_radius=None, bishop=False, knight=False) sage: H = (graphs.CompleteGraph(3)).cartesian_product(graphs.CompleteGraph(4)) sage: G.is_isomorphic(H) True
>>> from sage.all import * >>> G, _ = graphs.ChessboardGraphGenerator([Integer(3),Integer(4)], rook=True, rook_radius=None, bishop=False, knight=False) >>> H = (graphs.CompleteGraph(Integer(3))).cartesian_product(graphs.CompleteGraph(Integer(4))) >>> G.is_isomorphic(H) True
- static ChvatalGraph()[source]#
Return the Chvatal graph.
Chvatal graph is one of the few known graphs to satisfy Grunbaum’s conjecture that for every \(m\), \(n\), there is an \(m\)-regular, \(m\)-chromatic graph of girth at least \(n\). For more information, see the Wikipedia article Chv%C3%A1tal_graph.
EXAMPLES:
The Chvatal graph has 12 vertices and 24 edges. It is a 4-regular, 4-chromatic graph with radius 2, diameter 2, and girth 4:
sage: G = graphs.ChvatalGraph(); G Chvatal graph: Graph on 12 vertices sage: G.order(); G.size() 12 24 sage: G.degree() [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4] sage: G.chromatic_number() 4 sage: G.radius(); G.diameter(); G.girth() 2 2 4
>>> from sage.all import * >>> G = graphs.ChvatalGraph(); G Chvatal graph: Graph on 12 vertices >>> G.order(); G.size() 12 24 >>> G.degree() [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4] >>> G.chromatic_number() 4 >>> G.radius(); G.diameter(); G.girth() 2 2 4
- static CirculantGraph(n, adjacency)[source]#
Returns a circulant graph with \(n\) nodes.
A circulant graph has the property that the vertex \(i\) is connected with the vertices \(i+j\) and \(i-j\) for each \(j\) in
adjacency.INPUT:
n– number of vertices in the graphadjacency– the list of \(j\) values
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, each circulant graph will be displayed with the first (0) node at the top, with the rest following in a counterclockwise manner.
Filling the position dictionary in advance adds \(O(n)\) to the constructor.
See also
is_circulant()– checks whether a (di)graph is circulant, and/or returns all possible sets of parameters.
EXAMPLES: Compare plotting using the predefined layout and networkx:
sage: # needs networkx sage: import networkx sage: n = networkx.cycle_graph(23) sage: spring23 = Graph(n) sage: posdict23 = graphs.CirculantGraph(23,2) sage: spring23.show() # long time sage: posdict23.show() # long time
>>> from sage.all import * >>> # needs networkx >>> import networkx >>> n = networkx.cycle_graph(Integer(23)) >>> spring23 = Graph(n) >>> posdict23 = graphs.CirculantGraph(Integer(23),Integer(2)) >>> spring23.show() # long time >>> posdict23.show() # long time
We next view many cycle graphs as a Sage graphics array. First we use the
CirculantGraphconstructor, which fills in the position dictionary:sage: # needs sage.plot sage: g = [] sage: j = [] sage: for i in range(9): ....: k = graphs.CirculantGraph(i+4, i+1) ....: g.append(k) sage: for i in range(3): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) sage: G = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.CirculantGraph(i+Integer(4), i+Integer(1)) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
Compare to plotting with the spring-layout algorithm:
sage: # needs networkx sage.plot sage: g = [] sage: j = [] sage: for i in range(9): ....: spr = networkx.cycle_graph(i+3) ....: k = Graph(spr) ....: g.append(k) sage: for i in range(3): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) sage: G = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs networkx sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... spr = networkx.cycle_graph(i+Integer(3)) ... k = Graph(spr) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
Passing a 1 into adjacency should give the cycle.
sage: graphs.CirculantGraph(6,1) == graphs.CycleGraph(6) True sage: graphs.CirculantGraph(7,[1,3]).edges(sort=True, labels=false) [(0, 1), (0, 3), (0, 4), (0, 6), (1, 2), (1, 4), (1, 5), (2, 3), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5), (5, 6)]
>>> from sage.all import * >>> graphs.CirculantGraph(Integer(6),Integer(1)) == graphs.CycleGraph(Integer(6)) True >>> graphs.CirculantGraph(Integer(7),[Integer(1),Integer(3)]).edges(sort=True, labels=false) [(0, 1), (0, 3), (0, 4), (0, 6), (1, 2), (1, 4), (1, 5), (2, 3), (2, 5), (2, 6), (3, 4), (3, 6), (4, 5), (5, 6)]
- static CircularLadderGraph(n)[source]#
Return 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.
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. When \(n == 2\), we rotate the outer circle by an angle of \(\pi/8\) to ensure that all edges are visible (otherwise the 4 vertices of the graph would be placed on a single line).
EXAMPLES:
Construct and show a circular ladder graph with 26 nodes:
sage: g = graphs.CircularLadderGraph(13) sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.CircularLadderGraph(Integer(13)) >>> g.show() # long time # needs sage.plot
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): # needs sage.plot ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) sage: G = graphics_array(j) # needs sage.plot sage: G.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.CircularLadderGraph(i+Integer(3)) ... g.append(k) >>> for i in range(Integer(3)): # needs sage.plot ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) # needs sage.plot >>> G.show() # long time # needs sage.plot
- static ClawGraph()[source]#
Return 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 # needs sage.plot
>>> from sage.all import * >>> (graphs.ClawGraph()).show() # long time # needs sage.plot
Inspect a Claw graph:
sage: G = graphs.ClawGraph() sage: G Claw graph: Graph on 4 vertices
>>> from sage.all import * >>> G = graphs.ClawGraph() >>> G Claw graph: Graph on 4 vertices
- static ClebschGraph()[source]#
Return the Clebsch graph.
See the Wikipedia article Clebsch_graph for more information.
EXAMPLES:
sage: g = graphs.ClebschGraph() sage: g.automorphism_group().cardinality() # needs sage.groups 1920 sage: g.girth() 4 sage: g.chromatic_number() 4 sage: g.diameter() 2 sage: g.show(figsize=[10, 10]) # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.ClebschGraph() >>> g.automorphism_group().cardinality() # needs sage.groups 1920 >>> g.girth() 4 >>> g.chromatic_number() 4 >>> g.diameter() 2 >>> g.show(figsize=[Integer(10), Integer(10)]) # long time # needs sage.plot
- static CompleteBipartiteGraph(p, q, set_position=True)[source]#
Return a Complete Bipartite Graph on \(p + q\) vertices.
A Complete Bipartite Graph is a graph with its vertices partitioned into two groups, \(V_1 = \{0,...,p-1\}\) and \(V_2 = \{p,...,p+q-1\}\). Each \(u \in V_1\) is connected to every \(v \in V_2\).
INPUT:
p,q– number of vertices in each sideset_position– boolean (defaultTrue); if set toTrue, we assign positions to the vertices so that the set of cardinality \(p\) is on the line \(y=1\) and the set of cardinality \(q\) is on the line \(y=0\).
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 \(p\) nodes on the top row (at \(y=1\)) from left to right. The remaining \(q\) 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, \max(p, q)]\).
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 \(p\) (see
spring_medin 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: # needs networkx sage: import networkx sage: n = networkx.complete_bipartite_graph(389, 157) # long time sage: spring_big = Graph(n) # long time sage: posdict_big = graphs.CompleteBipartiteGraph(389, 157) # long time
>>> from sage.all import * >>> # needs networkx >>> import networkx >>> n = networkx.complete_bipartite_graph(Integer(389), Integer(157)) # long time >>> spring_big = Graph(n) # long time >>> posdict_big = graphs.CompleteBipartiteGraph(Integer(389), Integer(157)) # long time
Compare the plotting:
sage: n = networkx.complete_bipartite_graph(11, 17) # needs networkx sage: spring_med = Graph(n) # needs networkx sage: posdict_med = graphs.CompleteBipartiteGraph(11, 17)
>>> from sage.all import * >>> n = networkx.complete_bipartite_graph(Integer(11), Integer(17)) # needs networkx >>> spring_med = Graph(n) # needs networkx >>> posdict_med = graphs.CompleteBipartiteGraph(Integer(11), Integer(17))
Notice here how the spring-layout tends to center the nodes of \(n1\):
sage: spring_med.show() # long time # needs networkx sage: posdict_med.show() # long time # needs sage.plot
>>> from sage.all import * >>> spring_med.show() # long time # needs networkx >>> posdict_med.show() # long time # needs sage.plot
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): # needs sage.plot ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) sage: G = graphics_array(j) # needs sage.plot sage: G.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.CompleteBipartiteGraph(i+Integer(1),Integer(4)) ... g.append(k) >>> for i in range(Integer(3)): # needs sage.plot ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) # needs sage.plot >>> G.show() # long time # needs sage.plot
We compare to plotting with the spring-layout algorithm:
sage: # needs networkx sage.plot sage: g = [] sage: j = [] sage: for i in range(9): ....: spr = networkx.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 = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs networkx sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... spr = networkx.complete_bipartite_graph(i+Integer(1),Integer(4)) ... k = Graph(spr) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
sage: graphs.CompleteBipartiteGraph(5,6).complement() complement(Complete bipartite graph of order 5+6): Graph on 11 vertices
>>> from sage.all import * >>> graphs.CompleteBipartiteGraph(Integer(5),Integer(6)).complement() complement(Complete bipartite graph of order 5+6): Graph on 11 vertices
- static CompleteGraph(n)[source]#
Return a complete graph on \(n\) nodes.
A Complete Graph is a graph in which all nodes are connected to all other nodes.
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: # needs sage.plot 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 = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.CompleteGraph(i+Integer(3)) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
We compare to plotting with the spring-layout algorithm:
sage: # needs networkx sage.plot 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 = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs networkx sage.plot >>> import networkx >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... spr = networkx.complete_graph(i+Integer(3)) ... k = Graph(spr) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
Compare the constructors (results will vary):
sage: # needs networkx 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
>>> from sage.all import * >>> # needs networkx >>> import networkx >>> t = cputime() >>> n = networkx.complete_graph(Integer(389)); spring389 = Graph(n) >>> cputime(t) # random 0.59203700000000126 >>> t = cputime() >>> posdict389 = graphs.CompleteGraph(Integer(389)) >>> cputime(t) # random 0.6680419999999998
We compare plotting:
sage: # needs networkx sage: import networkx sage: n = networkx.complete_graph(23) sage: spring23 = Graph(n) sage: posdict23 = graphs.CompleteGraph(23) sage: spring23.show() # long time # needs sage.plot sage: posdict23.show() # long time # needs sage.plot
>>> from sage.all import * >>> # needs networkx >>> import networkx >>> n = networkx.complete_graph(Integer(23)) >>> spring23 = Graph(n) >>> posdict23 = graphs.CompleteGraph(Integer(23)) >>> spring23.show() # long time # needs sage.plot >>> posdict23.show() # long time # needs sage.plot
- static CompleteMultipartiteGraph(L)[source]#
Return a complete multipartite graph.
INPUT:
L– a list of integers; the respective sizes of the components
PLOTTING: Produce a layout of the vertices so that vertices in the same vertex set are adjacent and clearly separated from vertices in other vertex sets.
This is done by calculating the vertices of an \(r\)-gon then calculating the slope between adjacent vertices. We then ‘walk’ around the \(r\)-gon placing graph vertices in regular intervals between adjacent vertices of the \(r\)-gon.
Makes a nicely organized graph like in this picture: https://commons.wikimedia.org/wiki/File:Turan_13-4.svg
EXAMPLES:
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
>>> from sage.all import * >>> g = graphs.CompleteMultipartiteGraph([Integer(5), Integer(6), Integer(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
>>> from sage.all import * >>> g.chromatic_number() 3
- static ConwaySmith_for_3S7()[source]#
Return the Conway-Smith graph related to \(3 Sym(7)\).
This is a distance-regular graph with intersection array \([10, 6, 4, 1; 1, 2, 6, 10]\).
EXAMPLES:
sage: G = graphs.ConwaySmith_for_3S7() # needs sage.modules sage.rings.finite_rings sage.rings.number_field sage: G.is_distance_regular(True) # needs sage.modules sage.rings.finite_rings sage.rings.number_field ([10, 6, 4, 1, None], [None, 1, 2, 6, 10])
>>> from sage.all import * >>> G = graphs.ConwaySmith_for_3S7() # needs sage.modules sage.rings.finite_rings sage.rings.number_field >>> G.is_distance_regular(True) # needs sage.modules sage.rings.finite_rings sage.rings.number_field ([10, 6, 4, 1, None], [None, 1, 2, 6, 10])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 399.
- static CorrelationGraph(seqs, alpha, include_anticorrelation)[source]#
Return a correlation graph with a node per sequence in
seqs.Edges are added between nodes where the corresponding sequences have a correlation coeffecient greater than alpha.
If
include_anticorrelationisTrue, then edges are also added between nodes with correlation coefficient less than-alpha.INPUT:
seqs– list of sequences, taht is a list of listsalpha– float; threshold on the correlation coefficient between two sequences for adding an edgeinclude_anticorrelation– boolean; whether to add edges between nodes with correlation coefficient less than-alphaor not
EXAMPLES:
sage: # needs numpy sage: from sage.graphs.generators.basic import CorrelationGraph sage: data = [[1,2,3], [4,5,6], [7,8,9999]] sage: CG1 = CorrelationGraph(data, 0.9, False) sage: CG2 = CorrelationGraph(data, 0.9, True) sage: CG3 = CorrelationGraph(data, 0.1, True) sage: CG1.edges(sort=False) [(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)] sage: CG2.edges(sort=False) [(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)] sage: CG3.edges(sort=False) [(0, 0, None), (0, 1, None), (0, 2, None), (1, 1, None), (1, 2, None), (2, 2, None)]
>>> from sage.all import * >>> # needs numpy >>> from sage.graphs.generators.basic import CorrelationGraph >>> data = [[Integer(1),Integer(2),Integer(3)], [Integer(4),Integer(5),Integer(6)], [Integer(7),Integer(8),Integer(9999)]] >>> CG1 = CorrelationGraph(data, RealNumber('0.9'), False) >>> CG2 = CorrelationGraph(data, RealNumber('0.9'), True) >>> CG3 = CorrelationGraph(data, RealNumber('0.1'), True) >>> CG1.edges(sort=False) [(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)] >>> CG2.edges(sort=False) [(0, 0, None), (0, 1, None), (1, 1, None), (2, 2, None)] >>> CG3.edges(sort=False) [(0, 0, None), (0, 1, None), (0, 2, None), (1, 1, None), (1, 2, None), (2, 2, None)]
- static CossidentePenttilaGraph(q)[source]#
Return the Cossidente-Penttila \(((q^3+1)(q+1)/2,(q^2+1)(q-1)/2,(q-3)/2,(q-1)^2/2)\)-strongly regular graph
For each odd prime power \(q\), one can partition the points of the \(O_6^-(q)\)-generalized quadrangle \(GQ(q,q^2)\) into two parts, so that on any of them the induced subgraph of the point graph of the GQ has parameters as above [CP2005].
Directly following the construction in [CP2005] is not efficient, as one then needs to construct the dual \(GQ(q^2,q)\). Thus we describe here a more efficient approach that we came up with, following a suggestion by T.Penttila. Namely, this partition is invariant under the subgroup \(H=\Omega_3(q^2)<O_6^-(q)\). We build the appropriate \(H\), which leaves the form \(B(X,Y,Z)=XY+Z^2\) invariant, and pick up two orbits of \(H\) on the \(F_q\)-points. One them is \(B\)-isotropic, and we take the representative \((1:0:0)\). The other one corresponds to the points of \(PG(2,q^2)\) that have all the lines on them either missing the conic specified by \(B\), or intersecting the conic in two points. We take \((1:1:e)\) as the representative. It suffices to pick \(e\) so that \(e^2+1\) is not a square in \(F_{q^2}\). Indeed, The conic can be viewed as the union of \(\{(0:1:0)\}\) and \(\{(1:-t^2:t) | t \in F_{q^2}\}\). The coefficients of a generic line on \((1:1:e)\) are \([1:-1-eb:b]\), for \(-1\neq eb\). Thus, to make sure the intersection with the conic is always even, we need that the discriminant of \(1+(1+eb)t^2+tb=0\) never vanishes, and this is if and only if \(e^2+1\) is not a square. Further, we need to adjust \(B\), by multiplying it by appropriately chosen \(\nu\), so that \((1:1:e)\) becomes isotropic under the relative trace norm \(\nu B(X,Y,Z)+(\nu B(X,Y,Z))^q\). The latter is used then to define the graph.
INPUT:
q– an odd prime power.
EXAMPLES:
For \(q=3\) one gets Sims-Gewirtz graph.
sage: G = graphs.CossidentePenttilaGraph(3) # optional - gap_package_grape sage: G.is_strongly_regular(parameters=True) # optional - gap_package_grape (56, 10, 0, 2)
>>> from sage.all import * >>> G = graphs.CossidentePenttilaGraph(Integer(3)) # optional - gap_package_grape >>> G.is_strongly_regular(parameters=True) # optional - gap_package_grape (56, 10, 0, 2)
For \(q>3\) one gets new graphs.
sage: G = graphs.CossidentePenttilaGraph(5) # optional - gap_package_grape sage: G.is_strongly_regular(parameters=True) # optional - gap_package_grape (378, 52, 1, 8)
>>> from sage.all import * >>> G = graphs.CossidentePenttilaGraph(Integer(5)) # optional - gap_package_grape >>> G.is_strongly_regular(parameters=True) # optional - gap_package_grape (378, 52, 1, 8)
- static CoxeterGraph()[source]#
Return the Coxeter graph.
See the Wikipedia article Coxeter_graph.
EXAMPLES:
sage: g = graphs.CoxeterGraph() sage: g.automorphism_group().cardinality() # needs sage.groups 336 sage: g.girth() 7 sage: g.chromatic_number() 3 sage: g.diameter() 4 sage: g.show(figsize=[10, 10]) # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.CoxeterGraph() >>> g.automorphism_group().cardinality() # needs sage.groups 336 >>> g.girth() 7 >>> g.chromatic_number() 3 >>> g.diameter() 4 >>> g.show(figsize=[Integer(10), Integer(10)]) # long time # needs sage.plot
- static CubeConnectedCycle(d)[source]#
Return the cube-connected cycle of dimension \(d\).
The cube-connected cycle of order \(d\) is the \(d\)-dimensional hypercube with each of its vertices replaced by a cycle of length \(d\). This graph has order \(d \times 2^d\). The construction is as follows: Construct vertex \((x,y)\) for \(0 \leq x < 2^d\), \(0 \leq y < d\). For each vertex, \((x,y)\), add an edge between it and \((x, (y-1) \mod d))\), \((x,(y+1) \mod d)\), and \((x \oplus 2^y, y)\), where \(\oplus\) is the bitwise xor operator.
For \(d=1\) and \(2\), the cube-connected cycle graph contains self-loops or multiple edges between a pair of vertices, but for all other \(d\), it is simple.
INPUT:
d– The dimension of the desired hypercube as well as the length of the cycle to be placed at each vertex of the \(d\)-dimensional hypercube. \(d\) must be a positive integer.
EXAMPLES:
The order of the graph is \(d \times 2^d\)
sage: d = 3 sage: g = graphs.CubeConnectedCycle(d) sage: len(g) == d*2**d True
>>> from sage.all import * >>> d = Integer(3) >>> g = graphs.CubeConnectedCycle(d) >>> len(g) == d*Integer(2)**d True
The diameter of cube-connected cycles for \(d > 3\) is \(2d + \lfloor \frac{d}{2} \rfloor - 2\)
sage: d = 4 sage: g = graphs.CubeConnectedCycle(d) sage: g.diameter() == 2*d+d//2-2 True
>>> from sage.all import * >>> d = Integer(4) >>> g = graphs.CubeConnectedCycle(d) >>> g.diameter() == Integer(2)*d+d//Integer(2)-Integer(2) True
All vertices have degree \(3\) when \(d > 1\)
sage: g = graphs.CubeConnectedCycle(5) sage: all(g.degree(v) == 3 for v in g) True
>>> from sage.all import * >>> g = graphs.CubeConnectedCycle(Integer(5)) >>> all(g.degree(v) == Integer(3) for v in g) True
- static CubeGraph(n, embedding=1)[source]#
Return the \(n\)-cube graph, also called the hypercube in \(n\) dimensions.
The hypercube in \(n\) dimension is build upon the binary strings on \(n\) bits, two of them being adjacent if they differ in exactly one bit. Hence, the distance between two vertices in the hypercube is the Hamming distance.
INPUT:
n– integer; the dimension of the cube graphembedding– integer (default:1); two embeddings of the \(n\)-cube are available:1: the \(n\)-cube is projected inside a regular \(2n\)-gonal polygon by a skew orthogonal projection. See the Wikipedia article Hypercube for more details.2: orthogonal projection of the \(n\)-cube. This orientation shows columns of independent vertices such that the neighbors of a vertex are located in the columns on the left and on the right. The number of vertices in each column represents rows in Pascal’s triangle. See for instance the Wikipedia article 10-cube for more details.3: oblique projection of the \(n\)-cube. Oblique projection involves aligning one face parallel to the viewer and projecting at a specified angle, maintaining equal size for edges parallel to one axis while applying fixed foreshortening to others. This method simplifies the representation of a four-dimensional hypercube onto a two-dimensional plane, offering a geometrically consistent visualization.NoneorO: no embedding is provided
EXAMPLES:
The distance between \(0100110\) and \(1011010\) is \(5\), as expected:
sage: g = graphs.CubeGraph(7) sage: g.distance('0100110','1011010') 5
>>> from sage.all import * >>> g = graphs.CubeGraph(Integer(7)) >>> g.distance('0100110','1011010') 5
Plot several \(n\)-cubes in a Sage Graphics Array:
sage: # needs sage.plot sage: g = [] sage: j = [] sage: for i in range(6): ....: k = graphs.CubeGraph(i+1) ....: g.append(k) ... sage: for i in range(2): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) ... sage: G = graphics_array(j) sage: G.show(figsize=[6,4]) # long time
>>> from sage.all import * >>> # needs sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(6)): ... k = graphs.CubeGraph(i+Integer(1)) ... g.append(k) ... >>> for i in range(Integer(2)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) ... >>> G = graphics_array(j) >>> G.show(figsize=[Integer(6),Integer(4)]) # long time
Use the plot options to display larger \(n\)-cubes:
sage: g = graphs.CubeGraph(9, embedding=1) sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20) # long time, needs sage.plot sage: g = graphs.CubeGraph(9, embedding=2) sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20) # long time, needs sage.plot sage: g = graphs.CubeGraph(9, embedding=3) sage: g.show(figsize=[12,12],vertex_labels=False, vertex_size=20) # long time, needs sage.plot
>>> from sage.all import * >>> g = graphs.CubeGraph(Integer(9), embedding=Integer(1)) >>> g.show(figsize=[Integer(12),Integer(12)],vertex_labels=False, vertex_size=Integer(20)) # long time, needs sage.plot >>> g = graphs.CubeGraph(Integer(9), embedding=Integer(2)) >>> g.show(figsize=[Integer(12),Integer(12)],vertex_labels=False, vertex_size=Integer(20)) # long time, needs sage.plot >>> g = graphs.CubeGraph(Integer(9), embedding=Integer(3)) >>> g.show(figsize=[Integer(12),Integer(12)],vertex_labels=False, vertex_size=Integer(20)) # long time, needs sage.plot
AUTHORS:
Robert Miller
David Coudert
- static CycleGraph(n)[source]#
Return a cycle graph with \(n\) nodes.
A cycle graph is a basic structure which is also typically called an \(n\)-gon.
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: # needs networkx sage.plot 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
>>> from sage.all import * >>> # needs networkx sage.plot >>> import networkx >>> n = networkx.cycle_graph(Integer(23)) >>> spring23 = Graph(n) >>> posdict23 = graphs.CycleGraph(Integer(23)) >>> spring23.show() # long time >>> posdict23.show() # long time
We next view many cycle graphs as a Sage graphics array. First we use the
CycleGraphconstructor, which fills in the position dictionary:sage: # needs networkx sage.plot 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 = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs networkx sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.CycleGraph(i+Integer(3)) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
Compare to plotting with the spring-layout algorithm:
sage: # needs networkx sage.plot sage: g = [] sage: j = [] sage: for i in range(9): ....: spr = networkx.cycle_graph(i+3) ....: k = Graph(spr) ....: g.append(k) sage: for i in range(3): ....: n = [] ....: for m in range(3): ....: n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False)) ....: j.append(n) sage: G = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs networkx sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... spr = networkx.cycle_graph(i+Integer(3)) ... k = Graph(spr) ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
- static DartGraph()[source]#
Return a dart graph with 5 nodes.
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the dart graph is drawn as a dart, with the sharp part on the bottom.
EXAMPLES:
Construct and show a dart graph:
sage: g = graphs.DartGraph() sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.DartGraph() >>> g.show() # long time # needs sage.plot
- static DegreeSequence(deg_sequence)[source]#
Return a graph with the given degree sequence.
This method 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 [CL1996].
INPUT:
deg_sequence– list of integers with each entry corresponding to the degree of a different vertex
EXAMPLES:
sage: G = graphs.DegreeSequence([3,3,3,3]) # needs networkx sage: G.edges(sort=True, labels=False) # needs networkx [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] sage: G.show() # long time # needs networkx sage.plot
>>> from sage.all import * >>> G = graphs.DegreeSequence([Integer(3),Integer(3),Integer(3),Integer(3)]) # needs networkx >>> G.edges(sort=True, labels=False) # needs networkx [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)] >>> G.show() # long time # needs networkx sage.plot
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]) # needs networkx sage: G.show() # long time # needs networkx sage.plot
>>> from sage.all import * >>> G = graphs.DegreeSequence([Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3)]) # needs networkx >>> G.show() # long time # needs networkx sage.plot
sage: G = graphs.DegreeSequence([4,4,4,4,4,4,4,4]) # needs networkx sage: G.show() # long time # needs networkx sage.plot
>>> from sage.all import * >>> G = graphs.DegreeSequence([Integer(4),Integer(4),Integer(4),Integer(4),Integer(4),Integer(4),Integer(4),Integer(4)]) # needs networkx >>> G.show() # long time # needs networkx sage.plot
sage: G = graphs.DegreeSequence([1,2,3,4,3,4,3,2,3,2,1]) # needs networkx sage: G.show() # long time # needs networkx sage.plot
>>> from sage.all import * >>> G = graphs.DegreeSequence([Integer(1),Integer(2),Integer(3),Integer(4),Integer(3),Integer(4),Integer(3),Integer(2),Integer(3),Integer(2),Integer(1)]) # needs networkx >>> G.show() # long time # needs networkx sage.plot
- static DegreeSequenceBipartite(s1, s2)[source]#
Return 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 of verticess_2– list of integers corresponding to the degree sequence of the second set of vertices
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]) # needs sage.combinat sage.modules sage: g.is_isomorphic(graphs.CompleteBipartiteGraph(5,2)) # needs sage.combinat sage.modules True
>>> from sage.all import * >>> g = graphs.DegreeSequenceBipartite([Integer(2),Integer(2),Integer(2),Integer(2),Integer(2)],[Integer(5),Integer(5)]) # needs sage.combinat sage.modules >>> g.is_isomorphic(graphs.CompleteBipartiteGraph(Integer(5),Integer(2))) # needs sage.combinat sage.modules True
Some sequences being incompatible if, for example, their sums are different, the functions raises a
ValueErrorwhen no graph corresponding to the degree sequences exists:sage: g = graphs.DegreeSequenceBipartite([2,2,2,2,1],[5,5]) # needs sage.combinat sage.modules Traceback (most recent call last): ... ValueError: there exists no bipartite graph corresponding to the given degree sequences
>>> from sage.all import * >>> g = graphs.DegreeSequenceBipartite([Integer(2),Integer(2),Integer(2),Integer(2),Integer(1)],[Integer(5),Integer(5)]) # needs sage.combinat sage.modules Traceback (most recent call last): ... ValueError: there exists no bipartite graph corresponding to the given degree sequences
- static DegreeSequenceConfigurationModel(deg_sequence, seed=None)[source]#
Return a random pseudograph with the given degree sequence.
This method 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– list of integers with each entry corresponding to the expected degree of a different vertexseed– (optional) arandom.Randomseed or a Pythonintfor the random number generator
EXAMPLES:
sage: G = graphs.DegreeSequenceConfigurationModel([1,1]) # needs networkx sage: G.adjacency_matrix() # needs networkx sage.modules [0 1] [1 0]
>>> from sage.all import * >>> G = graphs.DegreeSequenceConfigurationModel([Integer(1),Integer(1)]) # needs networkx >>> G.adjacency_matrix() # needs networkx sage.modules [0 1] [1 0]
The output is allowed to contain both loops and multiple edges:
sage: # needs networkx sage: deg_sequence = [3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3] sage: G = graphs.DegreeSequenceConfigurationModel(deg_sequence) sage: G.order(), G.size() (20, 30) sage: G.has_loops() or G.has_multiple_edges() # random True sage: G.show() # long time # needs sage.plot
>>> from sage.all import * >>> # needs networkx >>> deg_sequence = [Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3),Integer(3)] >>> G = graphs.DegreeSequenceConfigurationModel(deg_sequence) >>> G.order(), G.size() (20, 30) >>> G.has_loops() or G.has_multiple_edges() # random True >>> G.show() # long time # needs sage.plot
REFERENCE:
- static DegreeSequenceExpected(deg_sequence, seed=None)[source]#
Return a random graph with expected given degree sequence.
This method 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– list of integers with each entry corresponding to the expected degree of a different vertexseed– (optional) arandom.Randomseed or a Pythonintfor the random number generator
EXAMPLES:
sage: G = graphs.DegreeSequenceExpected([1,2,3,2,3]); G # needs networkx Looped graph on 5 vertices sage: G.show() # long time # needs networkx sage.plot
>>> from sage.all import * >>> G = graphs.DegreeSequenceExpected([Integer(1),Integer(2),Integer(3),Integer(2),Integer(3)]); G # needs networkx Looped graph on 5 vertices >>> G.show() # long time # needs networkx sage.plot
REFERENCE:
- static DegreeSequenceTree(deg_sequence)[source]#
Return a tree with the given degree sequence.
This method 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– list of integers with each entry corresponding to the expected degree of a different vertex
EXAMPLES:
sage: G = graphs.DegreeSequenceTree([3,1,3,3,1,1,1,2,1]); G # needs networkx Graph on 9 vertices sage: G.show() # long time # needs networkx sage.plot
>>> from sage.all import * >>> G = graphs.DegreeSequenceTree([Integer(3),Integer(1),Integer(3),Integer(3),Integer(1),Integer(1),Integer(1),Integer(2),Integer(1)]); G # needs networkx Graph on 9 vertices >>> G.show() # long time # needs networkx sage.plot
- static DejterGraph()[source]#
Return the Dejter graph.
The Dejter graph is obtained from the binary 7-cube by deleting a copy of the Hamming code of length 7. It is 6-regular, with 112 vertices and 336 edges. For more information, see the Wikipedia article Dejter_graph.
EXAMPLES:
sage: g = graphs.DejterGraph(); g # needs sage.rings.finite_rings Dejter Graph: Graph on 112 vertices sage: g.is_regular(k=6) # needs sage.rings.finite_rings True sage: g.girth() # needs sage.rings.finite_rings 4
>>> from sage.all import * >>> g = graphs.DejterGraph(); g # needs sage.rings.finite_rings Dejter Graph: Graph on 112 vertices >>> g.is_regular(k=Integer(6)) # needs sage.rings.finite_rings True >>> g.girth() # needs sage.rings.finite_rings 4
- static DesarguesGraph()[source]#
Return the Desargues graph.
PLOTTING: The layout chosen is the same as on the cover of [Har1994].
EXAMPLES:
sage: D = graphs.DesarguesGraph() sage: L = graphs.LCFGraph(20,[5,-5,9,-9],5) # needs networkx sage: D.is_isomorphic(L) # needs networkx True sage: D.show() # long time # needs sage.plot
>>> from sage.all import * >>> D = graphs.DesarguesGraph() >>> L = graphs.LCFGraph(Integer(20),[Integer(5),-Integer(5),Integer(9),-Integer(9)],Integer(5)) # needs networkx >>> D.is_isomorphic(L) # needs networkx True >>> D.show() # long time # needs sage.plot
- static DiamondGraph()[source]#
Return a diamond graph with 4 nodes.
A diamond graph is a square with one pair of diagonal nodes connected.
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 # needs sage.plot
>>> from sage.all import * >>> g = graphs.DiamondGraph() >>> g.show() # long time # needs sage.plot
- static DipoleGraph(n)[source]#
Returns a dipole graph with n edges.
A dipole graph is a multigraph consisting of 2 vertices connected with n parallel edges.
EXAMPLES:
Construct and show a dipole graph with 13 edges:
sage: g = graphs.DipoleGraph(13); g Dipole graph: Multi-graph on 2 vertices sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.DipoleGraph(Integer(13)); g Dipole graph: Multi-graph on 2 vertices >>> g.show() # long time # needs sage.plot
- static DodecahedralGraph()[source]#
Return 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 choose to use a planar embedding of the graph. We hope to add rotatable, 3-dimensional viewing in the future. In such a case, a argument will be added to select the desired layout.
EXAMPLES:
Construct and show a Dodecahedral graph:
sage: g = graphs.DodecahedralGraph() sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.DodecahedralGraph() >>> g.show() # long time # needs sage.plot
Create several dodecahedral graphs in a Sage graphics array They will be drawn differently due to the use of the spring-layout algorithm:
sage: # needs sage.plot 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 = graphics_array(j) sage: G.show() # long time
>>> from sage.all import * >>> # needs sage.plot >>> g = [] >>> j = [] >>> for i in range(Integer(9)): ... k = graphs.DodecahedralGraph() ... g.append(k) >>> for i in range(Integer(3)): ... n = [] ... for m in range(Integer(3)): ... n.append(g[Integer(3)*i + m].plot(vertex_size=Integer(50), vertex_labels=False)) ... j.append(n) >>> G = graphics_array(j) >>> G.show() # long time
- static DorogovtsevGoltsevMendesGraph(n)[source]#
Construct the n-th generation of the Dorogovtsev-Goltsev-Mendes graph.
EXAMPLES:
sage: G = graphs.DorogovtsevGoltsevMendesGraph(8) # needs networkx sage: G.size() # needs networkx 6561
>>> from sage.all import * >>> G = graphs.DorogovtsevGoltsevMendesGraph(Integer(8)) # needs networkx >>> G.size() # needs networkx 6561
REFERENCE:
[1] Dorogovtsev, S. N., Goltsev, A. V., and Mendes, J. F. F., Pseudofractal scale-free web, Phys. Rev. E 066122 (2002).
- static DoubleGeneralizedPetersenGraph(n, k)[source]#
Return a double generalized Petersen graph with \(4n\) nodes.
The double generalized Petersen graphs is a family of graphs proposed in [ZF2012] as a variant of generalized Petersen graphs. The variables \(n\), \(k\) are integers such that \(n > 2\) and \(0 < k \leq \lfloor (n-1) / 2 \rfloor\).
INPUT:
n– the number of nodes is \(4 * n\)k– integer such that \(0 < k \leq \lfloor (n-1) / 2 \rfloor\) determining how vertices on second and third inner rims are connected
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the double generalized Petersen graphs are displayed as 4 cocentric cycles, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outer-circle, moving counterclockwise after that. The second circle is drawn with the (n)th node at the top, then counterclockwise as well. The tird cycle is drawn with the (2n)th node at the top, then counterclockwise. And the fourth cycle is drawn with the (3n)th node at the top, then again counterclockwise.
EXAMPLES:
When \(n\) is even the resulting graph will be isomorphic to a double generalized Petersen graph with \(k' = n / 2 - k\):
sage: g = graphs.DoubleGeneralizedPetersenGraph(10, 2) sage: g2 = graphs.DoubleGeneralizedPetersenGraph(10, 3) sage: g.is_isomorphic(g2) True
>>> from sage.all import * >>> g = graphs.DoubleGeneralizedPetersenGraph(Integer(10), Integer(2)) >>> g2 = graphs.DoubleGeneralizedPetersenGraph(Integer(10), Integer(3)) >>> g.is_isomorphic(g2) True
- static DoubleGrassmannGraph(q, e)[source]#
Return the bipartite double of the distance-\(e\) graph of the Grassmann graph \(J_q(n,e)\).
This graph can also be descirbed as follows: Let \(V\) be the vector space of dimension \(n\) over \(GF(q)\). The vertex set is the set of \(e+1\) or \(e\) subspaces of \(V\). Two vertices are adjacent if one subspace is contained in the other.
This graph is distance-transitive.
INPUT:
q– a prime powere– integer
EXAMPLES:
sage: G = graphs.DoubleGrassmannGraph(2,1) # needs sage.modules sage: G.diameter() # needs sage.modules 3 sage: G.is_distance_regular(True) # needs sage.modules ([3, 2, 2, None], [None, 1, 1, 3])
>>> from sage.all import * >>> G = graphs.DoubleGrassmannGraph(Integer(2),Integer(1)) # needs sage.modules >>> G.diameter() # needs sage.modules 3 >>> G.is_distance_regular(True) # needs sage.modules ([3, 2, 2, None], [None, 1, 1, 3])
REFERENCES:
See [BCN1989] pp. 272, 273 or [VDKT2016] p. 25.
- static DoubleOddGraph(n)[source]#
Return the double odd graph on \(2n+1\) points.
The graph is obtained using the subsets of size \(n\) and \(n+1\) of \({1, 2, ..., 2n+1}\) as vertices. Two vertices are adjacent if one is included in the other.
The graph is distance-transitive.
INPUT:
n– integer; must be greater than 0
EXAMPLES:
sage: G = graphs.DoubleOddGraph(5) sage: G.is_distance_regular(True) ([6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, None], [None, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]) sage: G = graphs.DoubleOddGraph(3) sage: G.diameter() 7 sage: G.is_distance_regular(True) ([4, 3, 3, 2, 2, 1, 1, None], [None, 1, 1, 2, 2, 3, 3, 4])
>>> from sage.all import * >>> G = graphs.DoubleOddGraph(Integer(5)) >>> G.is_distance_regular(True) ([6, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1, None], [None, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6]) >>> G = graphs.DoubleOddGraph(Integer(3)) >>> G.diameter() 7 >>> G.is_distance_regular(True) ([4, 3, 3, 2, 2, 1, 1, None], [None, 1, 1, 2, 2, 3, 3, 4])
REFERENCES:
See [BCN1989] pp. 259-261 or [VDKT2016] p. 25.
- static DoubleStarSnark()[source]#
Return the double star snark.
The double star snark is a 3-regular graph on 30 vertices. See the Wikipedia article Double-star_snark.
EXAMPLES:
sage: g = graphs.DoubleStarSnark() sage: g.order() 30 sage: g.size() 45 sage: g.chromatic_number() 3 sage: g.is_hamiltonian() # needs sage.numerical.mip False sage: g.automorphism_group().cardinality() # needs sage.groups 80 sage: g.show() # needs sage.plot
>>> from sage.all import * >>> g = graphs.DoubleStarSnark() >>> g.order() 30 >>> g.size() 45 >>> g.chromatic_number() 3 >>> g.is_hamiltonian() # needs sage.numerical.mip False >>> g.automorphism_group().cardinality() # needs sage.groups 80 >>> g.show() # needs sage.plot
- static DoublyTruncatedWittGraph()[source]#
Return the doubly truncated Witt graph.
This builds the truncated Witt graph, then removes all vertices whose codeword start with a 1.
The graph is distance-regular with intersection array \([7,6,4,4;1,1,1,6]\).
EXAMPLES:
sage: G = graphs.DoublyTruncatedWittGraph() # needs sage.libs.pari sage.modules sage: G.is_distance_regular(True) # needs sage.libs.pari sage.modules ([7, 6, 4, 4, None], [None, 1, 1, 1, 6])
>>> from sage.all import * >>> G = graphs.DoublyTruncatedWittGraph() # needs sage.libs.pari sage.modules >>> G.is_distance_regular(True) # needs sage.libs.pari sage.modules ([7, 6, 4, 4, None], [None, 1, 1, 1, 6])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 368.
- static DurerGraph()[source]#
Return the Dürer graph.
For more information, see the Wikipedia article D%C3%BCrer_graph.
EXAMPLES:
The Dürer graph is named after Albrecht Dürer. It is a planar graph with 12 vertices and 18 edges:
sage: G = graphs.DurerGraph(); G Durer graph: Graph on 12 vertices sage: G.is_planar() True sage: G.order() 12 sage: G.size() 18
>>> from sage.all import * >>> G = graphs.DurerGraph(); G Durer graph: Graph on 12 vertices >>> G.is_planar() True >>> G.order() 12 >>> G.size() 18
The Dürer graph has chromatic number 3, diameter 4, and girth 3:
sage: G.chromatic_number() 3 sage: G.diameter() 4 sage: G.girth() 3
>>> from sage.all import * >>> G.chromatic_number() 3 >>> G.diameter() 4 >>> G.girth() 3
Its automorphism group is isomorphic to \(D_6\):
sage: ag = G.automorphism_group() # needs sage.groups sage: ag.is_isomorphic(DihedralGroup(6)) # needs sage.groups True
>>> from sage.all import * >>> ag = G.automorphism_group() # needs sage.groups >>> ag.is_isomorphic(DihedralGroup(Integer(6))) # needs sage.groups True
- static DyckGraph()[source]#
Return the Dyck graph.
For more information, see the MathWorld article on the Dyck graph or the Wikipedia article Dyck_graph.
EXAMPLES:
The Dyck graph was defined by Walther von Dyck in 1881. It has \(32\) vertices and \(48\) edges, and is a cubic graph (regular of degree \(3\)):
sage: G = graphs.DyckGraph(); G Dyck graph: Graph on 32 vertices sage: G.order() 32 sage: G.size() 48 sage: G.is_regular() True sage: G.is_regular(3) True
>>> from sage.all import * >>> G = graphs.DyckGraph(); G Dyck graph: Graph on 32 vertices >>> G.order() 32 >>> G.size() 48 >>> G.is_regular() True >>> G.is_regular(Integer(3)) True
It is non-planar and Hamiltonian, as well as bipartite (making it a bicubic graph):
sage: G.is_planar() False sage: G.is_hamiltonian() # needs sage.numerical.mip True sage: G.is_bipartite() True
>>> from sage.all import * >>> G.is_planar() False >>> G.is_hamiltonian() # needs sage.numerical.mip True >>> G.is_bipartite() True
It has radius \(5\), diameter \(5\), and girth \(6\):
sage: G.radius() 5 sage: G.diameter() 5 sage: G.girth() 6
>>> from sage.all import * >>> G.radius() 5 >>> G.diameter() 5 >>> G.girth() 6
Its chromatic number is \(2\) and its automorphism group is of order \(192\):
sage: G.chromatic_number() 2 sage: G.automorphism_group().cardinality() # needs sage.groups 192
>>> from sage.all import * >>> G.chromatic_number() 2 >>> G.automorphism_group().cardinality() # needs sage.groups 192
It is a non-integral graph as it has irrational eigenvalues:
sage: G.characteristic_polynomial().factor() # needs sage.libs.pari sage.modules (x - 3) * (x + 3) * (x - 1)^9 * (x + 1)^9 * (x^2 - 5)^6
>>> from sage.all import * >>> G.characteristic_polynomial().factor() # needs sage.libs.pari sage.modules (x - 3) * (x + 3) * (x - 1)^9 * (x + 1)^9 * (x^2 - 5)^6
It is a toroidal graph, and its embedding on a torus is dual to an embedding of the Shrikhande graph (
ShrikhandeGraph).
- static EgawaGraph(p, s)[source]#
Return the Egawa graph with parameters \(p\), \(s\).
Egawa graphs are a peculiar family of graphs devised by Yoshimi Egawa in [Ega1981] . The Shrikhande graph is a special case of this family of graphs, with parameters \((1,0)\). All the graphs in this family are not recognizable by 1-WL (Weisfeiler Lehamn algorithm of the first order) and 2-WL, that is their orbits are not correctly returned by k-WL for k lower than 3.
Furthermore, all the graphs in this family are distance-regular, but they are not distance-transitive if \(p \neq 0\).
The Egawa graph with parameters \((0, s)\) is isomorphic to the Hamming graph with parameters \((s, 4)\), when the underlying set of the Hamming graph is \([0,1,2,3]\)
INPUT:
p– power to which the graph named \(Y\) in the referenceprovided above will be raised
s– power to which the graph named \(X\) in the referenceprovided above will be raised
OUTPUT:
G– The Egawa graph with parameters (p,s)
EXAMPLES:
Every Egawa graph is distance regular.
sage: g = graphs.EgawaGraph(1, 2) sage: g.is_distance_regular() True
>>> from sage.all import * >>> g = graphs.EgawaGraph(Integer(1), Integer(2)) >>> g.is_distance_regular() True
An Egawa graph with parameters (0,s) is isomorphic to the Hamming graph with parameters (s, 4).
sage: g = graphs.EgawaGraph(0, 4) sage: g.is_isomorphic(graphs.HammingGraph(4,4)) True
>>> from sage.all import * >>> g = graphs.EgawaGraph(Integer(0), Integer(4)) >>> g.is_isomorphic(graphs.HammingGraph(Integer(4),Integer(4))) True
- static EllinghamHorton54Graph()[source]#
Return the Ellingham-Horton 54-graph.
For more information, see the Wikipedia article Ellingham-Horton_graph.
EXAMPLES:
This graph is 3-regular:
sage: g = graphs.EllinghamHorton54Graph() sage: g.is_regular(k=3) True
>>> from sage.all import * >>> g = graphs.EllinghamHorton54Graph() >>> g.is_regular(k=Integer(3)) True
It is 3-connected and bipartite:
sage: g.vertex_connectivity() # not tested - too long 3 sage: g.is_bipartite() True
>>> from sage.all import * >>> g.vertex_connectivity() # not tested - too long 3 >>> g.is_bipartite() True
It is not Hamiltonian:
sage: g.is_hamiltonian() # not tested # needs sage.numerical.mip False
>>> from sage.all import * >>> g.is_hamiltonian() # not tested # needs sage.numerical.mip False
… and it has a nice drawing
sage: g.show(figsize=[10, 10]) # not tested - too long
>>> from sage.all import * >>> g.show(figsize=[Integer(10), Integer(10)]) # not tested - too long
- static EllinghamHorton78Graph()[source]#
Return the Ellingham-Horton 78-graph.
For more information, see the Wikipedia article Ellingham%E2%80%93Horton_graph
EXAMPLES:
This graph is 3-regular:
sage: g = graphs.EllinghamHorton78Graph() sage: g.is_regular(k=3) True
>>> from sage.all import * >>> g = graphs.EllinghamHorton78Graph() >>> g.is_regular(k=Integer(3)) True
It is 3-connected and bipartite:
sage: g.vertex_connectivity() # not tested (too long) 3 sage: g.is_bipartite() True
>>> from sage.all import * >>> g.vertex_connectivity() # not tested (too long) 3 >>> g.is_bipartite() True
It is not Hamiltonian:
sage: g.is_hamiltonian() # not tested # needs sage.numerical.mip False
>>> from sage.all import * >>> g.is_hamiltonian() # not tested # needs sage.numerical.mip False
… and it has a nice drawing
sage: g.show(figsize=[10,10]) # not tested (too long)
>>> from sage.all import * >>> g.show(figsize=[Integer(10),Integer(10)]) # not tested (too long)
- static EmptyGraph()[source]#
Return 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() 0 sage: empty1.show() # long time # needs sage.plot
>>> from sage.all import * >>> empty1 = graphs.EmptyGraph() >>> empty1.add_vertex() 0 >>> empty1.show() # long time # needs sage.plot
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 0 1 2 3 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(1, 4): ....: empty2.add_edge(4,i) # add edges {[1:4],[2:4],[3:4]} sage: empty2.show() # long time # needs sage.plot
>>> from sage.all import * >>> empty2 = graphs.EmptyGraph() >>> for i in range(Integer(5)): ... empty2.add_vertex() # add 5 nodes, labeled 0-4 0 1 2 3 4 >>> for i in range(Integer(3)): ... empty2.add_edge(i,i+Integer(1)) # add edges {[0:1],[1:2],[2:3]} >>> for i in range(Integer(1), Integer(4)): ... empty2.add_edge(Integer(4),i) # add edges {[1:4],[2:4],[3:4]} >>> empty2.show() # long time # needs sage.plot
- static ErreraGraph()[source]#
Return the Errera graph.
For more information, see the Wikipedia article Errera_graph.
EXAMPLES:
The Errera graph is named after Alfred Errera. It is a planar graph on 17 vertices and having 45 edges:
sage: G = graphs.ErreraGraph(); G Errera graph: Graph on 17 vertices sage: G.is_planar() True sage: G.order() 17 sage: G.size() 45
>>> from sage.all import * >>> G = graphs.ErreraGraph(); G Errera graph: Graph on 17 vertices >>> G.is_planar() True >>> G.order() 17 >>> G.size() 45
The Errera graph is Hamiltonian with radius 3, diameter 4, girth 3, and chromatic number 4:
sage: G.is_hamiltonian() # needs sage.numerical.mip True sage: G.radius() 3 sage: G.diameter() 4 sage: G.girth() 3 sage: G.chromatic_number() 4
>>> from sage.all import * >>> G.is_hamiltonian() # needs sage.numerical.mip True >>> G.radius() 3 >>> G.diameter() 4 >>> G.girth() 3 >>> G.chromatic_number() 4
Each vertex degree is either 5 or 6. That is, if \(f\) counts the number of vertices of degree 5 and \(s\) counts the number of vertices of degree 6, then \(f + s\) is equal to the order of the Errera graph:
sage: D = G.degree_sequence() sage: D.count(5) + D.count(6) == G.order() True
>>> from sage.all import * >>> D = G.degree_sequence() >>> D.count(Integer(5)) + D.count(Integer(6)) == G.order() True
The automorphism group of the Errera graph is isomorphic to the dihedral group of order 20:
sage: ag = G.automorphism_group() # needs sage.groups sage: ag.is_isomorphic(DihedralGroup(10)) # needs sage.groups True
>>> from sage.all import * >>> ag = G.automorphism_group() # needs sage.groups >>> ag.is_isomorphic(DihedralGroup(Integer(10))) # needs sage.groups True
- static EuropeMap(continental=False, year=2018)[source]#
Return European states as a graph of common border.
“European state” here is defined as an independent state having the capital city in Europe. The graph has an edge between those countries that have common land border.
INPUT:
continental– boolean (default:False); whether to only return states in the continental Europe or all European statesyear– integer (default:2018); reserved for future use
EXAMPLES:
sage: Europe = graphs.EuropeMap(); Europe Europe Map: Graph on 44 vertices sage: Europe.neighbors('Ireland') ['United Kingdom'] sage: cont_Europe = graphs.EuropeMap(continental=True) sage: cont_Europe.order() 40 sage: 'Iceland' in cont_Europe False
>>> from sage.all import * >>> Europe = graphs.EuropeMap(); Europe Europe Map: Graph on 44 vertices >>> Europe.neighbors('Ireland') ['United Kingdom'] >>> cont_Europe = graphs.EuropeMap(continental=True) >>> cont_Europe.order() 40 >>> 'Iceland' in cont_Europe False
- static F26AGraph()[source]#
Return the F26A graph.
The F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges. For more information, see the Wikipedia article F26A_graph.
EXAMPLES:
sage: # needs networkx sage: g = graphs.F26AGraph(); g F26A Graph: Graph on 26 vertices sage: g.order(), g.size() (26, 39) sage: g.automorphism_group().cardinality() 78 sage: g.girth() 6 sage: g.is_bipartite() True sage: g.characteristic_polynomial().factor() (x - 3) * (x + 3) * (x^4 - 5*x^2 + 3)^6
>>> from sage.all import * >>> # needs networkx >>> g = graphs.F26AGraph(); g F26A Graph: Graph on 26 vertices >>> g.order(), g.size() (26, 39) >>> g.automorphism_group().cardinality() 78 >>> g.girth() 6 >>> g.is_bipartite() True >>> g.characteristic_polynomial().factor() (x - 3) * (x + 3) * (x^4 - 5*x^2 + 3)^6
- static FibonacciTree(n)[source]#
Return the graph of the Fibonacci Tree \(F_{i}\) of order \(n\).
The Fibonacci tree \(F_{i}\) is recursively defined as the tree with a root vertex and two attached child trees \(F_{i-1}\) and \(F_{i-2}\), where \(F_{1}\) is just one vertex and \(F_{0}\) is empty.
INPUT:
n– the recursion depth of the Fibonacci Tree
EXAMPLES:
sage: g = graphs.FibonacciTree(3) # needs sage.libs.pari sage: g.is_tree() # needs sage.libs.pari True
>>> from sage.all import * >>> g = graphs.FibonacciTree(Integer(3)) # needs sage.libs.pari >>> g.is_tree() # needs sage.libs.pari True
sage: l1 = [ len(graphs.FibonacciTree(_)) + 1 for _ in range(6) ] # needs sage.libs.pari sage: l2 = list(fibonacci_sequence(2,8)) # needs sage.libs.pari sage: l1 == l2 # needs sage.libs.pari True
>>> from sage.all import * >>> l1 = [ len(graphs.FibonacciTree(_)) + Integer(1) for _ in range(Integer(6)) ] # needs sage.libs.pari >>> l2 = list(fibonacci_sequence(Integer(2),Integer(8))) # needs sage.libs.pari >>> l1 == l2 # needs sage.libs.pari True
AUTHORS:
Harald Schilly and Yann Laigle-Chapuy (2010-03-25)
- static FlowerSnark()[source]#
Return 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. See the Wikipedia article Flower_snark.
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.
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'
>>> from sage.all import * >>> F = graphs.FlowerSnark() >>> F Flower Snark: Graph on 20 vertices >>> F.graph6_string() 'ShCGHC@?GGg@?@?Gp?K??C?CA?G?_G?Cc'
Now show it:
sage: F.show() # long time # needs sage.plot
>>> from sage.all import * >>> F.show() # long time # needs sage.plot
- static FoldedCubeGraph(n)[source]#
Returns the folded cube graph of order \(2^{n-1}\).
The folded cube graph on \(2^{n-1}\) vertices can be obtained from a cube graph on \(2^n\) vertices by merging together opposed vertices. Alternatively, it can be obtained from a cube graph on \(2^{n-1}\) vertices by adding an edge between opposed vertices. This second construction is the one produced by this method.
See the Wikipedia article Folded_cube_graph for more information.
EXAMPLES:
The folded cube graph of order five is the Clebsch graph:
sage: fc = graphs.FoldedCubeGraph(5) sage: clebsch = graphs.ClebschGraph() sage: fc.is_isomorphic(clebsch) True
>>> from sage.all import * >>> fc = graphs.FoldedCubeGraph(Integer(5)) >>> clebsch = graphs.ClebschGraph() >>> fc.is_isomorphic(clebsch) True
- static FolkmanGraph()[source]#
Return the Folkman graph.
See the Wikipedia article Folkman_graph.
EXAMPLES:
sage: # needs networkx sage: g = graphs.FolkmanGraph() sage: g.order() 20 sage: g.size() 40 sage: g.diameter() 4 sage: g.girth() 4 sage: g.charpoly().factor() (x - 4) * (x + 4) * x^10 * (x^2 - 6)^4 sage: g.chromatic_number() 2 sage: g.is_eulerian() True sage: g.is_hamiltonian() # needs sage.numerical_mip True sage: g.is_vertex_transitive() False sage: g.is_bipartite() True
>>> from sage.all import * >>> # needs networkx >>> g = graphs.FolkmanGraph() >>> g.order() 20 >>> g.size() 40 >>> g.diameter() 4 >>> g.girth() 4 >>> g.charpoly().factor() (x - 4) * (x + 4) * x^10 * (x^2 - 6)^4 >>> g.chromatic_number() 2 >>> g.is_eulerian() True >>> g.is_hamiltonian() # needs sage.numerical_mip True >>> g.is_vertex_transitive() False >>> g.is_bipartite() True
- static ForkGraph()[source]#
Return a fork graph with 5 nodes.
A fork graph, sometimes also called chair graph, is 5 vertex tree.
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the fork graph is drawn as a fork, with the sharp part on the bottom.
EXAMPLES:
Construct and show a fork graph:
sage: g = graphs.ForkGraph() sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.ForkGraph() >>> g.show() # long time # needs sage.plot
- static FosterGraph()[source]#
Return the Foster graph.
See the Wikipedia article Foster_graph.
EXAMPLES:
sage: # needs networkx sage: g = graphs.FosterGraph() sage: g.order() 90 sage: g.size() 135 sage: g.diameter() 8 sage: g.girth() 10 sage: g.automorphism_group().cardinality() 4320 sage: g.is_hamiltonian() # needs sage.numerical_mip True
>>> from sage.all import * >>> # needs networkx >>> g = graphs.FosterGraph() >>> g.order() 90 >>> g.size() 135 >>> g.diameter() 8 >>> g.girth() 10 >>> g.automorphism_group().cardinality() 4320 >>> g.is_hamiltonian() # needs sage.numerical_mip True
- static FosterGraph3S6()[source]#
Return the Foster graph for \(3.Sym(6)\).
This graph is distance-regular with intersection array \([6, 4, 2, 1; 1, 1, 4, 6]\).
The graph is also distance transitive.
EXAMPLES:
sage: G = graphs.FosterGraph3S6() # needs sage.libs.gap sage: G.is_distance_regular(True) # needs sage.libs.gap ([6, 4, 2, 1, None], [None, 1, 1, 4, 6])
>>> from sage.all import * >>> G = graphs.FosterGraph3S6() # needs sage.libs.gap >>> G.is_distance_regular(True) # needs sage.libs.gap ([6, 4, 2, 1, None], [None, 1, 1, 4, 6])
REFERENCES:
A description and construction of this graph can be found in [BCN1989] p. 397.
- static FranklinGraph()[source]#
Return the Franklin graph.
For more information, see the Wikipedia article Franklin_graph.
EXAMPLES:
The Franklin graph is named after Philip Franklin. It is a 3-regular graph on 12 vertices and having 18 edges:
sage: G = graphs.FranklinGraph(); G Franklin graph: Graph on 12 vertices sage: G.is_regular(3) True sage: G.order() 12 sage: G.size() 18
>>> from sage.all import * >>> G = graphs.FranklinGraph(); G Franklin graph: Graph on 12 vertices >>> G.is_regular(Integer(3)) True >>> G.order() 12 >>> G.size() 18
The Franklin graph is a Hamiltonian, bipartite graph with radius 3, diameter 3, and girth 4:
sage: G.is_hamiltonian() # needs sage.numerical_mip True sage: G.is_bipartite() True sage: G.radius() 3 sage: G.diameter() 3 sage: G.girth() 4
>>> from sage.all import * >>> G.is_hamiltonian() # needs sage.numerical_mip True >>> G.is_bipartite() True >>> G.radius() 3 >>> G.diameter() 3 >>> G.girth() 4
It is a perfect, triangle-free graph having chromatic number 2:
sage: G.is_perfect() True sage: G.is_triangle_free() True sage: G.chromatic_number() 2
>>> from sage.all import * >>> G.is_perfect() True >>> G.is_triangle_free() True >>> G.chromatic_number() 2
- static FriendshipGraph(n)[source]#
Return the friendship graph \(F_n\).
The friendship graph is also known as the Dutch windmill graph. Let \(C_3\) be the cycle graph on 3 vertices. Then \(F_n\) is constructed by joining \(n \geq 1\) copies of \(C_3\) at a common vertex. If \(n = 1\), then \(F_1\) is isomorphic to \(C_3\) (the triangle graph). If \(n = 2\), then \(F_2\) is the butterfly graph, otherwise known as the bowtie graph. For more information, see the Wikipedia article Friendship_graph.
INPUT:
n– positive integer; the number of copies of \(C_3\) to use in constructing \(F_n\).
OUTPUT:
The friendship graph \(F_n\) obtained from \(n\) copies of the cycle graph \(C_3\).
See also
EXAMPLES:
The first few friendship graphs.
sage: # needs sage.plot sage: A = []; B = [] sage: for i in range(9): ....: g = graphs.FriendshipGraph(i + 1) ....: A.append(g) sage: for i in range(3): ....: n = [] ....: for j in range(3): ....: n.append(A[3*i + j].plot(vertex_size=20, vertex_labels=False)) ....: B.append(n) sage: G = graphics_array(B) sage: G.show() # long time
>>> from sage.all import * >>> # needs sage.plot >>> A = []; B = [] >>> for i in range(Integer(9)): ... g = graphs.FriendshipGraph(i + Integer(1)) ... A.append(g) >>> for i in range(Integer(3)): ... n = [] ... for j in range(Integer(3)): ... n.append(A[Integer(3)*i + j].plot(vertex_size=Integer(20), vertex_labels=False)) ... B.append(n) >>> G = graphics_array(B) >>> G.show() # long time
For \(n = 1\), the friendship graph \(F_1\) is isomorphic to the cycle graph \(C_3\), whose visual representation is a triangle.
sage: G = graphs.FriendshipGraph(1); G Friendship graph: Graph on 3 vertices sage: G.show() # long time # needs sage.plot sage: G.is_isomorphic(graphs.CycleGraph(3)) True
>>> from sage.all import * >>> G = graphs.FriendshipGraph(Integer(1)); G Friendship graph: Graph on 3 vertices >>> G.show() # long time # needs sage.plot >>> G.is_isomorphic(graphs.CycleGraph(Integer(3))) True
For \(n = 2\), the friendship graph \(F_2\) is isomorphic to the butterfly graph, otherwise known as the bowtie graph.
sage: G = graphs.FriendshipGraph(2); G Friendship graph: Graph on 5 vertices sage: G.is_isomorphic(graphs.ButterflyGraph()) True
>>> from sage.all import * >>> G = graphs.FriendshipGraph(Integer(2)); G Friendship graph: Graph on 5 vertices >>> G.is_isomorphic(graphs.ButterflyGraph()) True
If \(n \geq 2\), then the friendship graph \(F_n\) has \(2n + 1\) vertices and \(3n\) edges. It has radius 1, diameter 2, girth 3, and chromatic number 3. Furthermore, \(F_n\) is planar and Eulerian.
sage: n = randint(2, 10^3) sage: G = graphs.FriendshipGraph(n) sage: G.order() == 2*n + 1 True sage: G.size() == 3*n True sage: G.radius() 1 sage: G.diameter() 2 sage: G.girth() 3 sage: G.chromatic_number() 3 sage: G.is_planar() True sage: G.is_eulerian() True
>>> from sage.all import * >>> n = randint(Integer(2), Integer(10)**Integer(3)) >>> G = graphs.FriendshipGraph(n) >>> G.order() == Integer(2)*n + Integer(1) True >>> G.size() == Integer(3)*n True >>> G.radius() 1 >>> G.diameter() 2 >>> G.girth() 3 >>> G.chromatic_number() 3 >>> G.is_planar() True >>> G.is_eulerian() True
- static FruchtGraph()[source]#
Return a Frucht Graph.
A Frucht graph has 12 nodes and 18 edges. It is the smallest cubic identity graph. It is planar and Hamiltonian. See the Wikipedia article Frucht_graph.
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.
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 # needs networkx
>>> from sage.all import * >>> FRUCHT = graphs.FruchtGraph() >>> FRUCHT Frucht graph: Graph on 12 vertices >>> FRUCHT.graph6_string() 'KhCKM?_EGK?L' >>> (graphs.FruchtGraph()).show() # long time # needs networkx
- static FurerGadget(k, prefix=None)[source]#
Return a Furer gadget of order
kand their coloring.Construct the Furer gadget described in [CFI1992], a graph composed by a middle layer of \(2^(k-1)\) nodes and two sets of nodes \((a_0, ... , a_{k-1})\) and \((b_0, ... , b_{k-1})\). Each node in the middle is connected to either \(a_i\) or \(b_i\), for each i in [0,k[. To read about the complete construction, see [CFI1992]. The returned coloring colors the middle section with one color, and then each pair \((a_i, b_i)\) with another color. Since this method is mainly used to create Furer gadgets for the Cai-Furer-Immerman construction, returning gadgets that don’t always have the same vertex labels is important, that’s why there is a parameter to manually set a prefix to be appended to each vertex label.
INPUT:
k– The order of the returned Furer gadget, greater than 0.prefix– Prefix of to be appended to each vertex label,so as to individualise the returned Furer gadget. Must be comparable for equality and hashable.
OUTPUT:
G– The Furer gadget of orderkcoloring– A list of list of vertices, representing thepartition induced by the coloring of
G’s vertices
EXAMPLES:
Furer gadget of order 3, without any prefix.
sage: G, p = graphs.FurerGadget(3) sage: sorted(G, key=str) [(), (0, 'a'), (0, 'b'), (0, 1), (0, 2), (1, 'a'), (1, 'b'), (1, 2), (2, 'a'), (2, 'b')] sage: sorted(G.edge_iterator(), key=str) [((), (0, 'b'), None), ((), (1, 'b'), None), ((), (2, 'b'), None), ((0, 'b'), (1, 2), None), ((0, 1), (0, 'a'), None), ((0, 1), (1, 'a'), None), ((0, 1), (2, 'b'), None), ((0, 2), (0, 'a'), None), ((0, 2), (1, 'b'), None), ((0, 2), (2, 'a'), None), ((1, 2), (1, 'a'), None), ((1, 2), (2, 'a'), None)]
>>> from sage.all import * >>> G, p = graphs.FurerGadget(Integer(3)) >>> sorted(G, key=str) [(), (0, 'a'), (0, 'b'), (0, 1), (0, 2), (1, 'a'), (1, 'b'), (1, 2), (2, 'a'), (2, 'b')] >>> sorted(G.edge_iterator(), key=str) [((), (0, 'b'), None), ((), (1, 'b'), None), ((), (2, 'b'), None), ((0, 'b'), (1, 2), None), ((0, 1), (0, 'a'), None), ((0, 1), (1, 'a'), None), ((0, 1), (2, 'b'), None), ((0, 2), (0, 'a'), None), ((0, 2), (1, 'b'), None), ((0, 2), (2, 'a'), None), ((1, 2), (1, 'a'), None), ((1, 2), (2, 'a'), None)]
Furer gadget of order 3, with a prefix.
sage: G, p = graphs.FurerGadget(3, 'Prefix') sage: sorted(G, key=str) [('Prefix', ()), ('Prefix', (0, 'a')), ('Prefix', (0, 'b')), ('Prefix', (0, 1)), ('Prefix', (0, 2)), ('Prefix', (1, 'a')), ('Prefix', (1, 'b')), ('Prefix', (1, 2)), ('Prefix', (2, 'a')), ('Prefix', (2, 'b'))] sage: sorted(G.edge_iterator(), key=str) [(('Prefix', ()), ('Prefix', (0, 'b')), None), (('Prefix', ()), ('Prefix', (1, 'b')), None), (('Prefix', ()), ('Prefix', (2, 'b')), None), (('Prefix', (0, 'b')), ('Prefix', (1, 2)), None), (('Prefix', (0, 1)), ('Prefix', (0, 'a')), None), (('Prefix', (0, 1)), ('Prefix', (1, 'a')), None), (('Prefix', (0, 1)), ('Prefix', (2, 'b')), None), (('Prefix', (0, 2)), ('Prefix', (0, 'a')), None), (('Prefix', (0, 2)), ('Prefix', (1, 'b')), None), (('Prefix', (0, 2)), ('Prefix', (2, 'a')), None), (('Prefix', (1, 2)), ('Prefix', (1, 'a')), None), (('Prefix', (1, 2)), ('Prefix', (2, 'a')), None)]
>>> from sage.all import * >>> G, p = graphs.FurerGadget(Integer(3), 'Prefix') >>> sorted(G, key=str) [('Prefix', ()), ('Prefix', (0, 'a')), ('Prefix', (0, 'b')), ('Prefix', (0, 1)), ('Prefix', (0, 2)), ('Prefix', (1, 'a')), ('Prefix', (1, 'b')), ('Prefix', (1, 2)), ('Prefix', (2, 'a')), ('Prefix', (2, 'b'))] >>> sorted(G.edge_iterator(), key=str) [(('Prefix', ()), ('Prefix', (0, 'b')), None), (('Prefix', ()), ('Prefix', (1, 'b')), None), (('Prefix', ()), ('Prefix', (2, 'b')), None), (('Prefix', (0, 'b')), ('Prefix', (1, 2)), None), (('Prefix', (0, 1)), ('Prefix', (0, 'a')), None), (('Prefix', (0, 1)), ('Prefix', (1, 'a')), None), (('Prefix', (0, 1)), ('Prefix', (2, 'b')), None), (('Prefix', (0, 2)), ('Prefix', (0, 'a')), None), (('Prefix', (0, 2)), ('Prefix', (1, 'b')), None), (('Prefix', (0, 2)), ('Prefix', (2, 'a')), None), (('Prefix', (1, 2)), ('Prefix', (1, 'a')), None), (('Prefix', (1, 2)), ('Prefix', (2, 'a')), None)]
- static FuzzyBallGraph(partition, q)[source]#
Construct a Fuzzy Ball graph with the integer partition
partitionandqextra vertices.Let \(q\) be an integer and let \(m_1,m_2,...,m_k\) be a set of positive integers. Let \(n=q+m_1+...+m_k\). The Fuzzy Ball graph with partition \(m_1,m_2,...,m_k\) and \(q\) extra vertices is the graph constructed from the graph \(G=K_n\) by attaching, for each \(i=1,2,...,k\), a new vertex \(a_i\) to \(m_i\) distinct vertices of \(G\).
For given positive integers \(k\) and \(m\) and nonnegative integer \(q\), the set of graphs
FuzzyBallGraph(p, q)for all partitions \(p\) of \(m\) with \(k\) parts are cospectral with respect to the normalized Laplacian.EXAMPLES:
sage: F = graphs.FuzzyBallGraph([3,1],2) sage: F.adjacency_matrix(vertices=list(F)) # needs sage.modules [0 0 1 1 1 0 0 0] [0 0 0 0 0 1 0 0] [1 0 0 1 1 1 1 1] [1 0 1 0 1 1 1 1] [1 0 1 1 0 1 1 1] [0 1 1 1 1 0 1 1] [0 0 1 1 1 1 0 1] [0 0 1 1 1 1 1 0]
>>> from sage.all import * >>> F = graphs.FuzzyBallGraph([Integer(3),Integer(1)],Integer(2)) >>> F.adjacency_matrix(vertices=list(F)) # needs sage.modules [0 0 1 1 1 0 0 0] [0 0 0 0 0 1 0 0] [1 0 0 1 1 1 1 1] [1 0 1 0 1 1 1 1] [1 0 1 1 0 1 1 1] [0 1 1 1 1 0 1 1] [0 0 1 1 1 1 0 1] [0 0 1 1 1 1 1 0]
Pick positive integers \(m\) and \(k\) and a nonnegative integer \(q\). All the FuzzyBallGraphs constructed from partitions of \(m\) with \(k\) parts should be cospectral with respect to the normalized Laplacian:
sage: m = 4; q = 2; k = 2 sage: g_list = [graphs.FuzzyBallGraph(p,q) # needs sage.combinat sage.modules ....: for p in Partitions(m, length=k)] sage: set(g.laplacian_matrix(normalized=True, # long time (7s on sage.math, 2011), needs sage.combinat sage.modules ....: vertices=list(g)).charpoly() ....: for g in g_list) {x^8 - 8*x^7 + 4079/150*x^6 - 68689/1350*x^5 + 610783/10800*x^4 - 120877/3240*x^3 + 1351/100*x^2 - 931/450*x}
>>> from sage.all import * >>> m = Integer(4); q = Integer(2); k = Integer(2) >>> g_list = [graphs.FuzzyBallGraph(p,q) # needs sage.combinat sage.modules ... for p in Partitions(m, length=k)] >>> set(g.laplacian_matrix(normalized=True, # long time (7s on sage.math, 2011), needs sage.combinat sage.modules ... vertices=list(g)).charpoly() ... for g in g_list) {x^8 - 8*x^7 + 4079/150*x^6 - 68689/1350*x^5 + 610783/10800*x^4 - 120877/3240*x^3 + 1351/100*x^2 - 931/450*x}
- static GemGraph()[source]#
Return a gem graph with 5 nodes.
A gem graph is a fan graph (4,1).
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the gem graph is drawn as a gem, with the sharp part on the bottom.
EXAMPLES:
Construct and show a gem graph:
sage: g = graphs.GemGraph() sage: g.show() # long time # needs sage.plot
>>> from sage.all import * >>> g = graphs.GemGraph() >>> g.show() # long time # needs sage.plot
- static GeneralisedDodecagonGraph(s, t)[source]#
Return the point-graph of a generalised dodecagon of order \((s,t)\).
INPUT:
s,t– integers; order of the generalised dodecagon
EXAMPLES:
sage: # optional - gap_package_atlasrep internet sage: G = graphs.GeneralisedDodecagonGraph(1, 5) sage: G.is_distance_regular(True) ([6, 5, 5, 5, 5, 5, None], [None, 1, 1, 1, 1, 1, 6]) sage: H = graphs.GeneralisedDodecagonGraph(5, 1) sage: H.order() 23436 sage: H.is_distance_regular(True) # not tested (6 min) ([10, 5, 5, 5, 5, 5, None], [None, 1, 1, 1, 1, 1, 2])
>>> from sage.all import * >>> # optional - gap_package_atlasrep internet >>> G = graphs.GeneralisedDodecagonGraph(Integer(1), Integer(5)) >>> G.is_distance_regular(True) ([6, 5, 5, 5, 5, 5, None], [None, 1, 1, 1, 1, 1, 6]) >>> H = graphs.GeneralisedDodecagonGraph(Integer(5), Integer(1)) >>> H.order() 23436 >>> H.is_distance_regular(True) # not tested (6 min) ([10, 5, 5, 5, 5, 5, None], [None, 1, 1, 1, 1, 1, 2])
Note
This function indirectly uses the GAP’s AtlasRep package. Thus you may need an internet connection and the optional Sage’s package
gap_packages.REFERENCES:
See [BCN1989] pp. 200-205 for a discussion of distance-regular graphs from generalised polygons.
- static GeneralisedHexagonGraph(s, t)[source]#
Return the point-graph of a generalised hexagon of order \((s,t)\).
INPUT:
s,t– integers; order of the generalised hexagon
EXAMPLES:
sage: # needs sage.libs.gap sage: G = graphs.GeneralisedHexagonGraph(5, 5) # optional - gap_package_atlasrep internet sage: G.is_distance_regular(True) # optional - gap_package_atlasrep internet ([30, 25, 25, None], [None, 1, 1, 6]) sage: G = graphs.GeneralisedHexagonGraph(7, 1) sage: G.is_distance_regular(True) ([14, 7, 7, None], [None, 1, 1, 2]) sage: graphs.GeneralisedHexagonGraph(1, 1) Cycle graph: Graph on 6 vertices
>>> from sage.all import * >>> # needs sage.libs.gap >>> G = graphs.GeneralisedHexagonGraph(Integer(5), Integer(5)) # optional - gap_package_atlasrep internet >>> G.is_distance_regular(True) # optional - gap_package_atlasrep internet ([30, 25, 25, None], [None, 1, 1, 6]) >>> G = graphs.GeneralisedHexagonGraph(Integer(7), Integer(1)) >>> G.is_distance_regular(True) ([14, 7, 7, None], [None, 1, 1, 2]) >>> graphs.GeneralisedHexagonGraph(Integer(1), Integer(1)) Cycle graph: Graph on 6 vertices
Note
This function uses the GAP’s AtlasRep package to build GHs of order \((q, q)\), \((q, q^3)\) or \((q^3, q)\). For those graphs you need an internet connection and Sage’s optional package
gap_packages.REFERENCES:
See [BCN1989] pp. 200-205 for a discussion of distance-regular graphs from generalised polygons.
- static GeneralisedOctagonGraph(s, t)[source]#
Return the point-graph of a generalised octagon of order \((s,t)\).
INPUT:
s,t– integers; order of the generalised octagon
EXAMPLES:
sage: # needs sage.libs.gap sage: G = graphs.GeneralisedOctagonGraph(1, 4) sage: G.is_distance_regular(True) ([5, 4, 4, 4, None], [None, 1, 1, 1, 5]) sage: G = graphs.GeneralisedOctagonGraph(2, 4) # optional - gap_package_atlasrep internet sage: G.is_distance_regular(True) # optional - gap_package_atlasrep internet ([10, 8, 8, 8, None], [None, 1, 1, 1, 5]) sage: G = graphs.GeneralisedOctagonGraph(5, 1) sage: G.is_distance_regular(True) ([10, 5, 5, 5, None], [None, 1, 1, 1, 2])
>>> from sage.all import * >>> # needs sage.libs.gap >>> G = graphs.GeneralisedOctagonGraph(Integer(1), Integer(4)) >>> G.is_distance_regular(True) ([5, 4, 4, 4, None], [None, 1, 1, 1, 5]) >>> G = graphs.GeneralisedOctagonGraph(Integer(2), Integer(4)) # optional - gap_package_atlasrep internet >>> G.is_distance_regular(True) # optional - gap_package_atlasrep internet ([10, 8, 8, 8, None], [None, 1, 1, 1, 5]) >>> G = graphs.GeneralisedOctagonGraph(Integer(5), Integer(1)) >>> G.is_distance_regular(True) ([10, 5, 5, 5, None], [None, 1, 1, 1, 2])
Note
This function uses the GAP’s AtlasRep package to build the graphs of order \((2, 4)\) or \((4, 2)\). For those graphs you need an internet connection and Sage’s optional package
gap_packages.REFERENCES:
See [BCN1989] pp. 200-205 for a discussion of distance-regular graphs from generalised polygons.
- static GeneralizedPetersenGraph(n, k)[source]#
Returns a generalized Petersen graph with \(2n\) nodes. The variables \(n\), \(k\) are integers such that \(n>2\) and \(0<k\leq\lfloor(n-1)\)/\(2\rfloor\)
For \(k=1\) the result is a graph isomorphic to the circular ladder graph with the same \(n\). The regular Petersen Graph has \(n=5\) and \(k=2\). Other named graphs that can be described using this notation include the Desargues graph and the Möbius-Kantor graph.
INPUT:
n– the number of nodes is \(2*n\).k– integer \(0<k\leq\lfloor(n-1)\)/\(2\rfloor\). Decides how inner vertices are connected.
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the generalized Petersen graphs are displayed as an inner and outer cycle pair, with the first n nodes drawn on the outer circle. The first (0) node is drawn at the top of the outer-circle, moving counterclockwise after that. The inner circle is drawn with the (n)th node at the top, then counterclockwise as well.
EXAMPLES: For \(k=1\) the resulting graph will be isomorphic to a circular ladder graph.
sage: g = graphs.GeneralizedPetersenGraph(13,1) sage: g2 = graphs.CircularLadderGraph(13) sage: g.is_isomorphic(g2) True
>>> from sage.all import * >>> g = graphs.GeneralizedPetersenGraph(Integer(13),Integer(1)) >>> g2 = graphs.CircularLadderGraph(Integer(13)) >>> g.is_isomorphic(g2) True
The Desargues graph:
sage: g = graphs.GeneralizedPetersenGraph(10,3) sage: g.girth() 6 sage: g.is_bipartite() True
>>> from sage.all import * >>> g = graphs.GeneralizedPetersenGraph(Integer(10),Integer(3)) >>> g.girth() 6 >>> g.is_bipartite() True
AUTHORS:
Anders Jonsson (2009-10-15)
- static GeneralizedSierpinskiGraph(G, k, stretch=None)[source]#
Return the generalized Sierpinski graph of \(G\) of dimension \(k\).
Generalized Sierpinski graphs have been introduced in [GKP2011] to generalize the notion of Sierpinski graphs [KM1997].
Given a graph \(G = (V, E)\) of order \(n\) and a parameter \(k\), the generalized Sierpinski graph of \(G\) of dimension \(k\), denoted by \(S(G, k)\), can be constructed recursively from \(G\) as follows. \(S(G, 1)\) is isomorphic to \(G\). To construct \(S(G, k)\) for \(k > 1\), copy \(n\) times \(S(G, k - 1)\), once per vertex \(u \in V\), and add \(u\) at the beginning of the labels of each vertex in the copy of \(S(G, k - 1)\) corresponding to vertex \(u\). Then for any edge \(\{u, v\} \in E\), add an edge between vertex \((u, v, \ldots, v)\) and vertex \((v, u, \ldots, u)\).
INPUT:
G– a sage Graphk– integer; the dimensionstretch– integer (default:None); stretching factor used to determine the positions of the vertices of the output graph. By default (None), this value is set to twice the maximum Euclidean distance between the vertices of \(G\). This parameter is used only when the vertices of \(G\) have positions.
See also
EXAMPLES:
The generalized Sierpinski graph of dimension 1 of any graph \(G\) is isomorphic to \(G\):
sage: G = graphs.RandomGNP(10, .5) sage: S = graphs.GeneralizedSierpinskiGraph(G, 1) sage: S.is_isomorphic(G) True
>>> from sage.all import * >>> G = graphs.RandomGNP(Integer(10), RealNumber('.5')) >>> S = graphs.GeneralizedSierpinskiGraph(G, Integer(1)) >>> S.is_isomorphic(G) True
When \(G\) is a clique of order 3, the generalized Sierpinski graphs of \(G\) are isomorphic to Hanoi Tower graphs:
sage: k = randint(1, 5) sage: S = graphs.GeneralizedSierpinskiGraph(graphs.CompleteGraph(3), k) # needs sage.modules sage: H = graphs.HanoiTowerGraph(3, k) sage: S.is_isomorphic(H) # needs sage.modules True
>>> from sage.all import * >>> k = randint(Integer(1), Integer(5)) >>> S = graphs.GeneralizedSierpinskiGraph(graphs.CompleteGraph(Integer(3)), k) # needs sage.modules >>> H = graphs.HanoiTowerGraph(Integer(3), k) >>> S.is_isomorphic(H) # needs sage.modules True
The generalized Sierpinski graph of dimension \(k\) of any graph \(G\) with \(n\) vertices and \(m\) edges has \(n^k\) vertices and \(m\sum_{i=0}^{k-1}n^i\) edges:
sage: # needs sage.modules sage: n = randint(2, 6) sage: k = randint(1, 5) sage: G = graphs.RandomGNP(n, .5) sage: m = G.size() sage: S = graphs.GeneralizedSierpinskiGraph(G, k) sage: S.order() == n**k True sage: S.size() == m*sum([n**i for i in range(k)]) True sage: G = graphs.CompleteGraph(n) sage: S = graphs.GeneralizedSierpinskiGraph(G, k) sage: S.order() == n**k True sage: S.size() == (n*(n - 1)/2)*sum([n**i for i in range(k)]) True
>>> from sage.all import * >>> # needs sage.modules >>> n = randint(Integer(2), Integer(6)) >>> k = randint(Integer(1), Integer(5)) >>> G = graphs.RandomGNP(n, RealNumber('.5')) >>> m = G.size() >>> S = graphs.GeneralizedSierpinskiGraph(G, k) >>> S.order() == n**k True >>> S.size() == m*sum([n**i for i in range(k)]) True >>> G = graphs.CompleteGraph(n) >>> S = graphs.GeneralizedSierpinskiGraph(G, k) >>> S.order() == n**k True >>> S.size() == (n*(n - Integer(1))/Integer(2))*sum([n**i for i in range(k)]) True
The positions of the vertices of the output graph are determined from the positions of the vertices of \(G\), if any:
sage: G = graphs.HouseGraph() sage: G.get_pos() is not None True sage: H = graphs.GeneralizedSierpinskiGraph(G, 2) # needs sage.symbolic sage: H.get_pos() is not None # needs sage.symbolic True sage: G = Graph([(0, 1)]) sage: G.get_pos() is not None False sage: H = graphs.GeneralizedSierpinskiGraph(G, 2) # needs sage.symbolic sage: H.get_pos() is not None # needs sage.symbolic False
>>> from sage.all import * >>> G = graphs.HouseGraph() >>> G.get_pos() is not None True >>> H = graphs.GeneralizedSierpinskiGraph(G, Integer(2)) # needs sage.symbolic >>> H.get_pos() is not None # needs sage.symbolic True >>> G = Graph([(Integer(0), Integer(1))]) >>> G.get_pos() is not None False >>> H = graphs.GeneralizedSierpinskiGraph(G, Integer(2)) # needs sage.symbolic >>> H.get_pos() is not None # needs sage.symbolic False
- static GoethalsSeidelGraph(k, r)[source]#
Returns the graph \(\text{Goethals-Seidel}(k,r)\).
The graph \(\text{Goethals-Seidel}(k,r)\) comes from a construction presented in Theorem 2.4 of [GS1970]. It relies on a
(v,k)-BIBDwith \(r\) blocks and ahadamard_matrix()of order \(r+1\). The result is asage.graphs.strongly_regular_db.strongly_regular_graph()on \(v(r+1)\) vertices with degree \(k=(n+r-1)/2\).It appears under this name in Andries Brouwer’s database of strongly regular graphs.
INPUT:
k,r– integers
See also
EXAMPLES:
sage: graphs.GoethalsSeidelGraph(3,3) # needs sage.combinat sage.modules Graph on 28 vertices sage: graphs.GoethalsSeidelGraph(3,3).is_strongly_regular(parameters=True) # needs sage.combinat sage.modules (28, 15, 6, 10)
>>> from sage.all import * >>> graphs.GoethalsSeidelGraph(Integer(3),Integer(3)) # needs sage.combinat sage.modules Graph on 28 vertices >>> graphs.GoethalsSeidelGraph(Integer(3),Integer(3)).is_strongly_regular(parameters=True) # needs sage.combinat sage.modules (28, 15, 6, 10)
- static GoldnerHararyGraph()[source]#
Return the Goldner-Harary graph.
For more information, see the Wikipedia article Goldner%E2%80%93Harary_graph.
EXAMPLES:
The Goldner-Harary graph is named after A. Goldner and Frank Harary. It is a planar graph having 11 vertices and 27 edges:
sage: G = graphs.GoldnerHararyGraph(); G Goldner-Harary graph: Graph on 11 vertices sage: G.is_planar() True sage: G.order() 11 sage: G.size() 27
>>> from sage.all import * >>> G = graphs.GoldnerHararyGraph(); G Goldner-Harary graph: Graph on 11 vertices >>> G.is_planar() True >>> G.order() 11 >>> G.size() 27
The Goldner-Harary graph is chordal with radius 2, diameter 2, and girth 3:
sage: G.is_chordal() True sage: G.radius() 2 sage: G.diameter() 2 sage: G.girth() 3
>>> from sage.all import * >>> G.is_chordal() True >>> G.radius() 2 >>> G.diameter() 2 >>> G.girth() 3
Its chromatic number is 4 and its automorphism group is isomorphic to the dihedral group \(D_6\):
sage: G.chromatic_number() 4 sage: ag = G.automorphism_group() # needs sage.groups sage: ag.is_isomorphic(DihedralGroup(6)) # needs sage.groups True
>>> from sage.all import * >>> G.chromatic_number() 4 >>> ag = G.automorphism_group() # needs sage.groups >>> ag.is_isomorphic(DihedralGroup(Integer(6))) # needs sage.groups True
- static GolombGraph()[source]#
Return the Golomb graph.
See the Wikipedia article Golomb_graph for more information.
EXAMPLES:
The Golomb graph is a planar and Hamiltonian graph with 10 vertices and 18 edges. It has chromatic number 4, diameter 3, radius 2 and girth 3. It can be drawn in the plane as a unit distance graph:
sage: G = graphs.GolombGraph(); G # needs sage.symbolic Golomb graph: Graph on 10 vertices sage: pos = G.get_pos() # needs sage.symbolic sage: def dist2(u, v): ....: return (u[0]-v[0])**2 + (u[1]-v[1])**2 sage: all(dist2(pos[u], pos[v]) == 1 for u, v in G.edge_iterator(labels=None)) # needs sage.symbolic True
>>> from sage.all import * >>> G = graphs.GolombGraph(); G # needs sage.symbolic Golomb graph: Graph on 10 vertices >>> pos = G.get_pos() # needs sage.symbolic >>> def dist2(u, v): ... return (u[Integer(0)]-v[Integer(0)])**Integer(2) + (u[Integer(1)]-v[Integer(1)])**Integer(2) >>> all(dist2(pos[u], pos[v]) == Integer(1) for u, v in G.edge_iterator(labels=None)) # needs sage.symbolic True
- static GossetGraph()[source]#
Return the Gosset graph.
The Gosset graph is the skeleton of the
Gosset_3_21()polytope. It has with 56 vertices and degree 27. For more information, see the Wikipedia article Gosset_graph.EXAMPLES:
sage: g = graphs.GossetGraph(); g Gosset Graph: Graph on 56 vertices sage: g.order(), g.size() (56, 756)
>>> from sage.all import * >>> g = graphs.GossetGraph(); g Gosset Graph: Graph on 56 vertices >>> g.order(), g.size() (56, 756)
- static GrassmannGraph(q, n, input_e)[source]#
Return the Grassmann graph with parameters \((q, n, e)\).
This builds the Grassmann graph \(J_q(n,e)\). That is, for a vector space \(V = \mathbb F(q)^n\) the output is the graph on the subspaces of dimension \(e\) where two subspaces are adjacent if their intersection has dimension \(e-1\).
This graph is distance-regular with classical parameters \((\min(e, n-e), q, q, \genfrac {[}{]} {0pt} {} {n-e+1} 1 _q -1)\)
INPUT:
q– a prime powern,e– integers with \(n > e+1\)
EXAMPLES:
sage: G = graphs.GrassmannGraph(2, 4, 2) # needs sage.modules sage.rings.finite_rings sage: G.is_distance_regular(True) # needs sage.modules sage.rings.finite_rings ([18, 8, None], [None, 1, 9])
>>> from sage.all import * >>> G = graphs.GrassmannGraph(Integer(2), Integer(4), Integer(2)) # needs sage.modules sage.rings.finite_rings >>> G.is_distance_regular(True) # needs sage.modules sage.rings.finite_rings ([18, 8, None], [None, 1, 9])
REFERENCES:
See [BCN1989] pp. 268-272 or [VDKT2016] p. 21.
- static GrayGraph(embedding=1)[source]#
Return the Gray graph.
See the Wikipedia article Gray_graph.
INPUT:
embedding– integer (default:1); two embeddings are available, and can be selected by settingembeddingto 1 or 2
EXAMPLES:
sage: # needs networkx sage: g = graphs.GrayGraph() sage: g.order() 54 sage: g.size() 81 sage: g.girth() 8 sage: g.diameter() 6 sage: g.show(figsize=[10, 10]) # long time # needs sage.plot sage: graphs.GrayGraph(embedding=2).show(figsize=[10, 10]) # long time, needs sage.plot
>>> from sage.all import * >>> # needs networkx >>> g = graphs.GrayGraph() >>> g.order() 54 >>> g.size() 81 >>> g.girth() 8 >>> g.diameter() 6 >>> g.show(figsize=[Integer(10), Integer(10)]) # long time # needs sage.plot >>> graphs.GrayGraph(embedding=Integer(2)).show(figsize=[Integer(10), Integer(10)]) # long time, needs sage.plot
- static Grid2dGraph(p, q, set_positions=True)[source]#
Return a \(2\)-dimensional grid graph with \(p \times q\) nodes (\(p\) rows and \(q\) 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.
INPUT:
pandq– two positive integersset_positions– boolean (default:True); whether to set the position of the nodes
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 # needs sage.plot
>>> from sage.all import * >>> g = graphs.Grid2dGraph(Integer(5),Integer(7)) >>> g.show() # long time # needs sage.plot
- static GridGraph(dim_list)[source]#
Return an \(n\)-dimensional grid graph.
INPUT:
dim_list– a list of integers representing the number of nodes toextend 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 # needs sage.plot
>>> from sage.all import * >>> G = graphs.GridGraph([Integer(2),Integer(3),Integer(4)]) >>> G.show() # long time # needs sage.plot
sage: C = graphs.CubeGraph(4) sage: G = graphs.GridGraph([2,2,2,2]) sage: C.show() # long time # needs sage.plot sage: G.show() # long time # needs sage.plot
>>> from sage.all import * >>> C = graphs.CubeGraph(Integer(4)) >>> G = graphs.GridGraph([Integer(2),Integer(2),Integer(2),Integer(2)]) >>> C.show() # long time # needs sage.plot >>> G.show() # long time # needs sage.plot
- static GritsenkoGraph()[source]#
Return SRG(65, 32, 15, 16) constructed by Gritsenko.
We took the adjacency matrix from O. Gritsenko’s [Gri2021] and extracted orbits of the automorphism group on the edges.
EXAMPLES:
sage: H = graphs.GritsenkoGraph(); H # needs sage.groups Gritsenko strongly regular graph: Graph on 65 vertices sage: H.is_strongly_regular(parameters=True) # needs sage.groups (65, 32, 15, 16)
>>> from sage.all import * >>> H = graphs.GritsenkoGraph(); H # needs sage.groups Gritsenko strongly regular graph: Graph on 65 vertices >>> H.is_strongly_regular(parameters=True) # needs sage.groups (65, 32, 15, 16)
- static GrotzschGraph()[source]#
Return the Grötzsch graph.
The Grötzsch graph is an example of a triangle-free graph with chromatic number equal to 4. For more information, see the Wikipedia article Gr%C3%B6tzsch_graph.
EXAMPLES:
The Grötzsch graph is named after Herbert Grötzsch. It is a Hamiltonian graph with 11 vertices and 20 edges:
sage: G = graphs.GrotzschGraph(); G Grotzsch graph: Graph on 11 vertices sage: G.is_hamiltonian() # needs sage.numerical.mip True sage: G.order() 11 sage: G.size() 20
>>> from sage.all import * >>> G = graphs.GrotzschGraph(); G Grotzsch graph: Graph on 11 vertices >>> G.is_hamiltonian() # needs sage.numerical.mip True >>> G.order() 11 >>> G.size() 20
The Grötzsch graph is triangle-free and having radius 2, diameter 2, and girth 4:
sage: G.is_triangle_free() True sage: G.radius() 2 sage: G.diameter() 2 sage: G.girth() 4
>>> from sage.all import * >>> G.is_triangle_free() True >>> G.radius() 2 >>> G.diameter() 2 >>> G.girth() 4
Its chromatic number is 4 and its automorphism group is isomorphic to the dihedral group \(D_5\):
sage: G.chromatic_number() 4 sage: ag = G.automorphism_group() # needs sage.groups sage: ag.is_isomorphic(DihedralGroup(5)) # needs sage.groups True
>>> from sage.all import * >>> G.chromatic_number() 4 >>> ag = G.automorphism_group() # needs sage.groups >>> ag.is_isomorphic(DihedralGroup(Integer(5))) # needs sage.groups True
- static HaemersGraph(q, hyperoval=None, hyperoval_matching=None, field=None, check_hyperoval=True)[source]#
Return the Haemers graph obtained from \(T_2^*(q)^*\)
Let \(q\) be a power of 2. In Sect. 8.A of [BL1984] one finds a construction of a strongly regular graph with parameters \((q^2(q+2),q^2+q-1,q-2,q)\) from the graph of \(T_2^*(q)^*\), constructed by
T2starGeneralizedQuadrangleGraph(), by redefining adjacencies in the way specified by an arbitraryhyperoval_matchingof the points (i.e. partitioning into size two parts) ofhyperovaldefining \(T_2^*(q)^*\).While [BL1984] gives the construction in geometric terms, it can be formulated, and is implemented, in graph-theoretic ones, of re-adjusting the edges. Namely, \(G=T_2^*(q)^*\) has a partition into \(q+2\) independent sets \(I_k\) of size \(q^2\) each. Each vertex in \(I_j\) is adjacent to \(q\) vertices from \(I_k\). Each \(I_k\) is paired to some \(I_{k'}\), according to
hyperoval_matching. One adds edges \((s,t)\) for \(s,t \in I_k\) whenever \(s\) and \(t\) are adjacent to some \(u \in I_{k'}\), and removes all the edges between \(I_k\) and \(I_{k'}\).INPUT:
q– a power of twohyperoval_matching– ifNone(default), pair each \(i\)-th point ofhyperovalwith \((i+1)\)-th. Otherwise, specifies the pairing in the format \(((i_1,i'_1),(i_2,i'_2),...)\).hyperoval– a hyperoval defining \(T_2^*(q)^*\). IfNone(default), the classical hyperoval obtained from a conic is used. See the documentation ofT2starGeneralizedQuadrangleGraph(), for more information.field– an instance of a finite field of order \(q\), must be provided ifhyperovalis providedcheck_hyperoval– boolean (default:True); whether to checkhyperovalfor correctness or not
EXAMPLES:
using the built-in constructions:
sage: # needs sage.combinat sage.rings.finite_rings sage: g = graphs.HaemersGraph(4); g Haemers(4): Graph on 96 vertices sage: g.is_strongly_regular(parameters=True) (96, 19, 2, 4)
>>> from sage.all import * >>> # needs sage.combinat sage.rings.finite_rings >>> g = graphs.HaemersGraph(Integer(4)); g Haemers(4): Graph on 96 vertices >>> g.is_strongly_regular(parameters=True) (96, 19, 2, 4)
supplying your own hyperoval_matching:
sage: # needs sage.combinat sage.rings.finite_rings sage: g = graphs.HaemersGraph(4, hyperoval_matching=((0,5),(1,4),(2,3))); g Haemers(4): Graph on 96 vertices sage: g.is_strongly_regular(parameters=True) (96, 19, 2, 4)
>>> from sage.all import * >>> # needs sage.combinat sage.rings.finite_rings >>> g = graphs.HaemersGraph(Integer(4), hyperoval_matching=((Integer(0),Integer(5)),(Integer(1),Integer(4)),(Integer(2),Integer(3)))); g Haemers(4): Graph on 96 vertices >>> g.is_strongly_regular(parameters=True) (96, 19, 2, 4)
- static HalfCube(n)[source]#
Return the halved cube in \(n\) dimensions.
The graph is distance-regular with classical parameters \((\lfloor \frac n 2 \rfloor, 1, 2, 2 \lceil \frac n 2 \rceil -1)\).
INPUT:
n– integer; must be greater than 2
EXAMPLES:
sage: G = graphs.HalfCube(8) sage: G.is_distance_regular(True) ([28, 15, 6, 1, None], [None, 1, 6, 15, 28]) sage: G = graphs.HalfCube(4) sage: G.is_distance_regular(True) ([6, 1, None], [None, 1, 6])
>>> from sage.all import * >>> G = graphs.HalfCube(Integer(8)) >>> G.is_distance_regular(True) ([28, 15, 6, 1, None], [None, 1, 6, 15, 28]) >>> G = graphs.HalfCube(Integer(4)) >>> G.is_distance_regular(True) ([6, 1, None], [None, 1, 6])
REFERENCES:
See [BCN1989] pp. 264, 265 or [VDKT2016] p. 21. This construction can be found on Wikipedia article Halved_cube_graph#Equivalent_constructions
- static HallJankoGraph(from_string=True)[source]#
Return the Hall-Janko graph.
For more information on the Hall-Janko graph, see the Wikipedia article Hall-Janko_graph.
The construction used to generate this graph in Sage is by a 100-point permutation representation of the Janko group \(J_2\), as described in version 3 of the ATLAS of Finite Group representations, in particular on the page ATLAS: J2 – Permutation representation on 100 points.
INPUT:
from_string– boolean (default:True); whether to build the graph from its sparse6 string or through GAP. The two methods return the same graph though doing it through GAP takes more time.
EXAMPLES:
sage: g = graphs.HallJankoGraph() sage: g.is_regular(36) True sage: g.is_vertex_transitive() # needs sage.groups True
>>> from sage.all import * >>> g = graphs.HallJankoGraph() >>> g.is_regular(Integer(36)) True >>> g.is_vertex_transitive() # needs sage.groups True
Is it really strongly regular with parameters 14, 12?
sage: nu = set(g.neighbors(0)) sage: for v in range(1, 100): ....: if v in nu: ....: expected = 14 ....: else: ....: expected = 12 ....: nv = set(g.neighbors(v)) ....: nv.discard(0) ....: if len(nu & nv) != expected: ....: print("Something is wrong here!!!") ....: break
>>> from sage.all import * >>> nu = set(g.neighbors(Integer(0))) >>> for v in range(Integer(1), Integer(100)): ... if v in nu: ... expected = Integer(14) ... else: ... expected = Integer(12) ... nv = set(g.neighbors(v)) ... nv.discard(Integer(0)) ... if len(nu & nv) != expected: ... print("Something is wrong here!!!") ... break
Some other properties that we know how to check:
sage: g.diameter() 2 sage: g.girth() 3 sage: factor(g.characteristic_polynomial()) # needs sage.libs.pari sage.modules (x - 36) * (x - 6)^36 * (x + 4)^63
>>> from sage.all import * >>> g.diameter() 2 >>> g.girth() 3 >>> factor(g.characteristic_polynomial()) # needs sage.libs.pari sage.modules (x - 36) * (x - 6)^36 * (x + 4)^63
- static HammingGraph(n, q, X=None)[source]#
Return the Hamming graph with parameters \(n\), \(q\) over \(X\).
Hamming graphs are graphs over the cartesian product of n copies of \(X\), where \(q = |X|\), where the vertices, labelled with the corresponding tuple in \(X^n\), are connected if the Hamming distance between their labels is 1. All Hamming graphs are regular, vertex-transitive and distance-regular.
Hamming graphs with parameters \((1,q)\) represent the complete graph with q vertices over the set \(X\).
INPUT:
n– power to whichXwill be raised to provide verticesfor the Hamming graph
q– cardinality ofXX– list of labels representing the vertices of theunderlying graph the Hamming graph will be based on; if
None(or left unused), the list \([0, ... , q-1]\) will be used
OUTPUT:
G– The Hamming graph with parameters \((n,q,X)\)
EXAMPLES:
Every Hamming graph is distance-regular, regular and vertex-transitive:
sage: g = graphs.HammingGraph(3, 7) sage: g.is_distance_regular() True sage: g.is_regular() True sage: g.is_vertex_transitive() # needs sage.groups True
>>> from sage.all import * >>> g = graphs.HammingGraph(Integer(3), Integer(7)) >>> g.is_distance_regular() True >>> g.is_regular() True >>> g.is_vertex_transitive() # needs sage.groups True
A Hamming graph with parameters \((1,q)\) is isomorphic to the Complete graph with parameter \(q\):
sage: g = graphs.HammingGraph(1, 23) sage: g.is_isomorphic(graphs.CompleteGraph(23)) True
>>> from sage.all import * >>> g = graphs.HammingGraph(Integer(1), Integer(23)) >>> g.is_isomorphic(graphs.CompleteGraph(Integer(23))) True
If a parameter \(q\) is provided which is not equal to \(X\)’s cardinality, an exception is raised:
sage: X = ['a','b','c','d','e'] sage: g = graphs.HammingGraph(2, 3, X) Traceback (most recent call last): ... ValueError: q must be the cardinality of X
>>> from sage.all import * >>> X = ['a','b','c','d','e'] >>> g = graphs.HammingGraph(Integer(2), Integer(3), X) Traceback (most recent call last): ... ValueError: q must be the cardinality of X
REFERENCES:
For a more accurate description, see the following wikipedia page: Wikipedia article Hamming_graph
- static HanoiTowerGraph(pegs, disks, labels=True, positions=True)[source]#
Returns the graph whose vertices are the states of the Tower of Hanoi puzzle, with edges representing legal moves between states.
INPUT:
pegs– the number of pegs in the puzzle, 2 or greaterdisks– the number of disks in the puzzle, 1 or greaterlabels– default:True, ifTruethe graph contains more meaningful labels, see explanation below. For large instances, turn off labels for much faster creation of the graph.positions– default:True, ifTruethe graph contains layout information. This creates a planar layout for the case of three pegs. For large instances, turn off layout information for much faster creation of the graph.
OUTPUT:
The Tower of Hanoi puzzle has a certain number of identical pegs and a certain number of disks, each of a different radius. Initially the disks are all on a single peg, arranged in order of their radii, with the largest on the bottom.
The goal of the puzzle is to move the disks to any other peg, arranged in the same order. The one constraint is that the disks resident on any one peg must always be arranged with larger radii lower down.
The vertices of this graph represent all the possible states of this puzzle. Each state of the puzzle is a tuple with length equal to the number of disks, ordered by largest disk first. The entry of the tuple is the peg where that disk resides. Since disks on a given peg must go down in size as we go up the peg, this totally describes the state of the puzzle.
For example
(2,0,0)means the large disk is on peg 2, the medium disk is on peg 0, and the small disk is on peg 0 (and we know the small disk must be above the medium disk). We encode these tuples as integers with a base equal to the number of pegs, and low-order digits to the right.Two vertices are adjacent if we can change the puzzle from one state to the other by moving a single disk. For example,
(2,0,0)is adjacent to(2,0,1)since we can move the small disk off peg 0 and onto (the empty) peg 1. So the solution to a 3-disk puzzle (with at least two pegs) can be expressed by the shortest path between(0,0,0)and(1,1,1). For more on this representation of the graph, or its properties, see [AD2010].For greatest speed we create graphs with integer vertices, where we encode the tuples as integers with a base equal to the number of pegs, and low-order digits to the right. So for example, in a 3-peg puzzle with 5 disks, the state
(1,2,0,1,1)is encoded as \(1\ast 3^4 + 2\ast 3^3 + 0\ast 3^2 + 1\ast 3^1 + 1\ast 3^0 = 139\).For smaller graphs, the labels that are the tuples are informative, but slow down creation of the graph. Likewise computing layout information also incurs a significant speed penalty. For maximum speed, turn off labels and layout and decode the vertices explicitly as needed. The
sage.rings.integer.Integer.digits()with thepadstooption is a quick way to do this, though you may want to reverse the list that is output.See also
PLOTTING:
The layout computed when
positions = Truewill look especially good for the three-peg case, when the graph is known to be planar. Except for two small cases on 4 pegs, the graph is otherwise not planar, and likely there is a better way to layout the vertices.EXAMPLES:
A classic puzzle uses 3 pegs. We solve the 5 disk puzzle using integer labels and report the minimum number of moves required. Note that \(3^5-1\) is the state where all 5 disks are on peg 2.
sage: H = graphs.HanoiTowerGraph(3, 5, labels=False, positions=False) sage: H.distance(0, 3^5-1) 31
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(3), Integer(5), labels=False, positions=False) >>> H.distance(Integer(0), Integer(3)**Integer(5)-Integer(1)) 31
A slightly larger instance.
sage: H = graphs.HanoiTowerGraph(4, 6, labels=False, positions=False) sage: H.num_verts() 4096 sage: H.distance(0, 4^6-1) 17
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(4), Integer(6), labels=False, positions=False) >>> H.num_verts() 4096 >>> H.distance(Integer(0), Integer(4)**Integer(6)-Integer(1)) 17
For a small graph, labels and layout information can be useful. Here we explicitly list a solution as a list of states.
sage: H = graphs.HanoiTowerGraph(3, 3, labels=True, positions=True) sage: H.shortest_path((0,0,0), (1,1,1)) [(0, 0, 0), (0, 0, 1), (0, 2, 1), (0, 2, 2), (1, 2, 2), (1, 2, 0), (1, 1, 0), (1, 1, 1)]
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(3), Integer(3), labels=True, positions=True) >>> H.shortest_path((Integer(0),Integer(0),Integer(0)), (Integer(1),Integer(1),Integer(1))) [(0, 0, 0), (0, 0, 1), (0, 2, 1), (0, 2, 2), (1, 2, 2), (1, 2, 0), (1, 1, 0), (1, 1, 1)]
Some facts about this graph with \(p\) pegs and \(d\) disks:
only automorphisms are the “obvious” ones – renumber the pegs.
chromatic number is less than or equal to \(p\)
independence number is \(p^{d-1}\)
sage: H = graphs.HanoiTowerGraph(3, 4, labels=False, positions=False) sage: H.automorphism_group().is_isomorphic(SymmetricGroup(3)) # needs sage.groups True sage: H.chromatic_number() 3 sage: len(H.independent_set()) == 3^(4-1) True
>>> from sage.all import * >>> H = graphs.HanoiTowerGraph(Integer(3), Integer(4), labels=False, positions=False) >>> H.automorphism_group().is_isomorphic(SymmetricGroup(Integer(3))) # needs sage.groups True >>> H.chromatic_number() 3 >>> len(H.independent_set()) == Integer(3)**(Integer(4)-Integer(1)) True
AUTHOR:
Rob Beezer, (2009-12-26), with assistance from Su Doree
- static HararyGraph(k, n)[source]#
Returns the Harary graph on \(n\) vertices and connectivity \(k\), where \(2 \leq k < n\).
A \(k\)-connected graph \(G\) on \(n\) vertices requires the minimum degree \(\delta(G)\geq k\), so the minimum number of edges \(G\) should have is \(\lceil kn/2\rceil\). Harary graphs achieve this lower bound, that is, Harary graphs are minimal \(k\)-connected graphs on \(n\) vertices.
The construction provided uses the method CirculantGraph. For more details, see the book [West2001] or the MathWorld article on Harary graphs.
EXAMPLES:
Harary graphs \(H_{k,n}\):
sage: h = graphs.HararyGraph(5,9); h Harary graph 5, 9: Graph on 9 vertices sage: h.order() 9 sage: h.size() 23 sage: h.vertex_connectivity() # needs sage.numerical.mip 5
>>> from sage.all import * >>> h = graphs.HararyGraph(Integer(5),Integer(9)); h Harary graph 5, 9: Graph on 9 vertices >>> h.order() 9 >>> h.size() 23 >>> h.vertex_connectivity() # needs sage.numerical.mip 5
- static HarborthGraph()[source]#
Return the Harborth Graph.
The Harborth graph has 104 edges and 52 vertices, and is the smallest known example of a 4-regular matchstick graph. For more information, see the Wikipedia article Harborth_graph.
EXAMPLES:
sage: g = graphs.HarborthGraph(); g Harborth Graph: Graph on 52 vertices sage: g.is_regular(4) True
>>> from sage.all import * >>> g = graphs.HarborthGraph(); g Harborth Graph: Graph on 52 vertices >>> g.is_regular(Integer(4)) True
- static HarriesGraph(embedding=1)[source]#
Return the Harries Graph.
The Harries graph is a Hamiltonian 3-regular graph on 70 vertices. See the Wikipedia article Harries_graph.
The default embedding here is to emphasize the graph’s 4 orbits. This graph actually has a funny construction. The following procedure gives an idea of it, though not all the adjacencies are being properly defined.
Take two disjoint copies of a
Petersen graph. Their vertices will form an orbit of the final graph.Subdivide all the edges once, to create 15+15=30 new vertices, which together form another orbit.
Create 15 vertices, each of them linked to 2 corresponding vertices of the previous orbit, one in each of the two subdivided Petersen graphs. At the end of this step all vertices from the previous orbit have degree 3, and the only vertices of degree 2 in the graph are those that were just created.
Create 5 vertices connected only to the ones from the previous orbit so that the graph becomes 3-regular.
INPUT:
embedding– integer (default:1); two embeddings are available, and can be selected by settingembeddingto 1 or 2
EXAMPLES:
sage: # needs networkx sage: g = graphs.HarriesGraph() sage: g.order() 70 sage: g.size() 105 sage: g.girth() 10 sage: g.diameter() 6 sage: g.show(figsize=[10, 10]) # long time # needs sage.plot sage: graphs.HarriesGraph(embedding=2).show(figsize=[10, 10]) # long time, needs sage.plot
>>> from sage.all import * >>> # needs networkx >>> g = graphs.HarriesGraph() >>> g.order() 70 >>> g.size() 105 >>> g.girth() 10 >>> g.diameter() 6 >>> g.show(figsize=[Integer(10), Integer(10)]) # long time # needs sage.plot >>> graphs.HarriesGraph(embedding=Integer(2)).show(figsize=[Integer(10), Integer(10)]) # long time, needs sage.plot
- static HarriesWongGraph(embedding=1)[source]#
Return the Harries-Wong Graph.
See the Wikipedia article Harries-Wong_graph.
About the default embedding:
The default embedding is an attempt to emphasize the graph’s 8 (!!!) different orbits. In order to understand this better, one can picture the graph as being built in the following way.
One first creates a 3-dimensional cube (8 vertices, 12 edges), whose vertices define the first orbit of the final graph.
The edges of this graph are subdivided once, to create 12 new vertices which define a second orbit.
The edges of the graph are subdivided once more, to create 24 new vertices giving a third orbit.
4 vertices are created and made adjacent to the vertices of the second orbit so that they have degree 3. These 4 vertices also define a new orbit.
In order to make the vertices from the third orbit 3-regular (they all miss one edge), one creates a binary tree on 1 + 3 + 6 + 12 vertices. The leaves of this new tree are made adjacent to the 12 vertices of the third orbit, and the graph is now 3-regular. This binary tree contributes 4 new orbits to the Harries-Wong graph.
INPUT:
embedding– integer (default:1); two embeddings are available, and can be selected by settingembeddingto 1 or 2
EXAMPLES:
sage: # needs networkx sage: g = graphs.HarriesWongGraph() sage: g.order() 70 sage: g.size() 105 sage: g.girth() 10 sage: g.diameter() 6 sage: orbits = g.automorphism_group(orbits=True)[-1] # long time # needs sage.groups sage: g.show(figsize=[15, 15], partition=orbits) # long time # needs sage.groups sage.plot
>>> from sage.all import * >>> # needs networkx >>> g = graphs.HarriesWongGraph() >>> g.order() 70 >>> g.size() 105 >>> g.girth() 10 >>> g.diameter() 6 >>> orbits = g.automorphism_group(orbits=True)[-Integer(1)] # long time # needs sage.groups >>> g.show(figsize=[Integer(15), Integer(15)], partition=orbits) # long time # needs sage.groups sage.plot
Alternative embedding:
sage: graphs.HarriesWongGraph(embedding=2).show() # long time # needs networkx sage.plot
>>> from sage.all import * >>> graphs.HarriesWongGraph(embedding=Integer(2)).show() # long time # needs networkx sage.plot
- static HeawoodGraph()[source]#
Return a Heawood graph.
The Heawood graph is a cage graph that has 14 nodes. It is a cubic symmetric graph. (See also the Möbius-Kantor graph,
MobiusKantorGraph()). It is nonplanar and Hamiltonian. It has diameter 3, radius 3, girth 6, and chromatic number 2. It is 4-transitive but not 5-transitive. See the Wikipedia article Heawood_graph.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.
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 # needs sage.plot
>>> from sage.all import * >>> H = graphs.HeawoodGraph() >>> H Heawood graph: Graph on 14 vertices >>> H.graph6_string() 'MhEGHC@AI?_PC@_G_' >>> (graphs.HeawoodGraph()).show() # long time # needs sage.plot <
