Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*- Small graphs
The methods defined here appear in :mod:`sage.graphs.graph_generators`. """ #***************************************************************************** # Copyright (C) 2006 Robert L. Miller <rlmillster@gmail.com> # and Emily A. Kirkman # Copyright (C) 2009 Michael C. Yurko <myurko@gmail.com> # # Distributed under the terms of the GNU General Public License (GPL) # as published by the Free Software Foundation; either version 2 of # the License, or (at your option) any later version. # http://www.gnu.org/licenses/ #***************************************************************************** # import from Sage library
####################################################################### # Named Graphs #######################################################################
r""" 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:`Harborth_graph`.
EXAMPLES::
sage: g = graphs.HarborthGraph(); g Harborth Graph: Graph on 52 vertices sage: g.is_regular(4) True
""" 'pZkfJPuo[lfZHys^mFcDs}`pG{UNNgoHC}DIgrI[qjMhTyDQrQlVydrBYmWkn', loops=False, multiedges=False)
3: (129.8, 216.0), 4: (129.8, 584.0), 5: (150.7, 387.9), 6: (150.7, 412.1), 7: (169.0, 124.0), 8: (169.0, 676.0), 9: (189.9, 295.9), 10: (189.9, 504.1), 11: (229.1, 203.9), 12: (229.1, 596.1), 13: (250.0, 400.0), 14: (251.4, 180.6), 15: (251.4, 619.4), 16: (256.1, 300.2), 17: (256.1, 499.8), 18: (259.3, 080.9), 19: (259.3, 719.1), 20: (333.8, 237.2), 21: (333.8, 562.8), 22: (341.7, 137.5), 23: (341.7, 662.5), 24: (350.0, 037.9), 25: (350.0, 336.0), 26: (350.0, 464.0), 27: (350.0, 762.1), 28: (358.3, 137.5), 29: (358.3, 662.5), 30: (366.2, 237.2), 31: (366.2, 562.8), 32: (440.7, 080.9), 33: (440.7, 719.1), 34: (443.9, 300.2), 35: (443.9, 499.8), 36: (448.6, 180.6), 37: (448.6, 619.4), 38: (450.0, 400.0), 39: (470.9, 203.9), 40: (470.9, 596.1), 41: (510.1, 295.9), 42: (510.1, 504.1), 43: (531.0, 124.0), 44: (531.0, 676.0), 45: (549.3, 387.9), 46: (549.3, 412.1), 47: (570.2, 216.0), 48: (570.2, 584.0), 49: (609.4, 308.0), 50: (609.4, 492.0), 51: (648.5, 400.0)})
r""" Returns the Harries Graph.
The Harries graph is a Hamiltonian 3-regular graph on 70 vertices. See the :wikipedia:`Wikipedia page on the Harries graph <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 :meth:`Petersen graph <PetersenGraph>`. 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`` -- two embeddings are available, and can be selected by setting ``embedding`` to 1 or 2.
EXAMPLES::
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 sage: graphs.HarriesGraph(embedding=2).show(figsize=[10, 10]) # long time
TESTS::
sage: graphs.HarriesGraph(embedding=3) Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2.
""" 19, -21, -33, 29], 5)
# The graph's four orbits 56, 58, 62, 64] 37, 41, 43, 45, 47, 49, 51, 55, 57, 59, 61, 63, 65, 69]
# Correspondence between the vertices of one of the two Petersen # graphs on o[0] and the vertices of a standard Petersen graph # object 28: 4, 30: 3}
# Correspondence between the vertices of the other Petersen graph # on o[0] and the vertices of the first one 20: 14, 22: 56, 62: 42}
# Position for the vertices from the first copy
# Position for the vertices in the second copy. Moves the first, # too.
# Vertices from o[1]. These are actually the "edges" of the # copies of Petersen.
# 15 vertices from o[2]
# 5 vertices from o[3]
return g else:
r""" Returns the Harries-Wong Graph.
See the :wikipedia:`Wikipedia page on the Harries-Wong graph <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`` -- two embeddings are available, and can be selected by setting ``embedding`` to 1 or 2.
EXAMPLES::
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] sage: g.show(figsize=[15, 15], partition=orbits) # long time
Alternative embedding::
sage: graphs.HarriesWongGraph(embedding=2).show()
TESTS::
sage: graphs.HarriesWongGraph(embedding=3) Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2. """
9, -27, 35, -9, 9, -17, 21, 27, -29, -9, -25, 13, 19, -9, -33, -17, 19, -31, 27, 11, -25, 29, -33, 13, -13, 21, -29, -21, 25, 9, -11, -19, 29, 9, -27, -19, -13, -35, -9, 9, 17, 25, -9, 9, 27, -27, -21, 15, -9, 29, -29, 33, -9, -25]
# Binary tree (left side) last=(-8, -2.25)) last=(-7, -3)) first=(-6, 3.5), last=(-6, -3.5))
# Cube, corners: [9, 15, 21, 27, 45, 51, 57, 61] radius=4) radius=4*.707) radius=4) radius=4*.707)
# Cube, subdivision
# Top vertices
else:
r""" Returns the Wells graph.
For more information on the Wells graph (also called Armanios-Wells graph), see `this page <http://www.win.tue.nl/~aeb/graphs/Wells.html>`_.
The implementation follows the construction given on page 266 of [BCN89]_. This requires to create intermediate graphs and run a small isomorphism test, while everything could be replaced by a pre-computed list of edges : I believe that it is better to keep "the recipe" in the code, however, as it is quite unlikely that this could become the most time-consuming operation in any sensible algorithm, and .... "preserves knowledge", which is what open-source software is meant to do.
EXAMPLES::
sage: g = graphs.WellsGraph(); g Wells graph: Graph on 32 vertices sage: g.order() 32 sage: g.size() 80 sage: g.girth() 5 sage: g.diameter() 4 sage: g.chromatic_number() 4 sage: g.is_regular(k=5) True
REFERENCES:
.. [BCN89] \A. E. Brouwer, A. M. Cohen, A. Neumaier, Distance-Regular Graphs, Springer, 1989. """
# Following the construction from the book "Distance-regular graphs"
# Vertices at distance 3 in the Dodecahedron
# Building the graph whose line graph is the dodecahedron.
# Computing the isomorphism between the two
# The relabeling that the books claims to exist.
# Checking that the above computations indeed produces a good labeling.
raise ValueError("There is something wrong going on !")
# The graph we will return, starting from the dodecahedron
# Good ! Now adding 12 new vertices
# Giving our graph a "not-so-bad" layout (1, 3): 8, (3, 0): 18, (3, '+'): 22, (2, 1): 13, (1, '+'): 10, (0, 3): 2, (2, '+'): 16, ('inf', '-'): 31, (4, 0): 24, (1, 2): 7, (4, '+'): 28, (0, '-'): 5, (0, 4): 3, (4, 1): 25, (2, '-'): 17, (3, 2): 20, (3, '-'): 23, (1, '-'): 11, (1, 4): 9, (2, 3): 14, ('inf', '+'): 30, (4, 2): 26, (1, 0): 6, (0, 1): 0, (3, 1): 19, (0, 2): 1, (2, 0): 12, (4, '-'): 29, (0, '+'): 4, (4, 3): 27, (3, 4): 21, (2, 4): 15})
(2, 5, 30, 23, 18, 4, 31, 22), (3, 17, 21, 9, 24, 16, 27, 25), (6, 10, 8, 15, 0, 11, 19, 26)]
r""" Returns 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:`600-cell`.
INPUT:
- ``embedding`` (1 (default) or 2) -- two different embeddings for a plot.
EXAMPLES::
sage: g = graphs.Cell600() # long time sage: g.size() # long time 720 sage: g.is_regular(12) # long time True sage: g.is_vertex_transitive() # long time True """ from sage.rings.rational_field import QQ from sage.rings.polynomial.polynomial_ring import polygen from sage.rings.number_field.number_field import NumberField from sage.modules.free_module import VectorSpace from sage.groups.perm_gps.permgroup_named import AlternatingGroup
x = polygen(QQ, 'x') K = NumberField(x ** 2 - x - 1, 'f') f = K.gen() K4 = VectorSpace(K, 4)
# first 96 vertices step = [[a * f / 2, b * K(1) / 2, c * (f - 1) / 2, 0] for a in [-1, 1] for b in [-1, 1] for c in [-1, 1]] vert96 = [K4([v[s(1) - 1], v[s(2) - 1], v[s(3) - 1], v[s(4) - 1]]) for v in step for s in AlternatingGroup(4)]
# 16 more vertices vert16 = [K4([K(a) / 2, K(b) / 2, K(c) / 2, K(d) / 2]) for a in [-1, 1] for b in [-1, 1] for c in [-1, 1] for d in [-1, 1]]
# 8 last vertices vert8 = [K4([1, 0, 0, 0]), K4([-1, 0, 0, 0]), K4([0, 1, 0, 0]), K4([0, -1, 0, 0]), K4([0, 0, 1, 0]), K4([0, 0, -1, 0]), K4([0, 0, 0, 1]), K4([0, 0, 0, -1])]
# all vertices together U = vert96 + vert16 + vert8
g = Graph([list(range(120)), lambda i, j: U[i].inner_product(U[j]) == f / 2])
# Embedding from sage.graphs.graph_plot import _circle_embedding if embedding == 1: pos = [0, 1, 3, 13, 78, 90, 93, 110, 29, 104, 11, 48, 107, 83, 92, 55, 32, 16, 117, 24, 26, 56, 52, 47, 75, 72, 66, 112, 27, 115, 21, 33, 118, 79, 91, 37, 2, 5, 96, 31, 82, 88, 94, 74, 50, 28, 20, 105, 45, 99, 70, 25, 101, 54, 46, 51, 17, 35, 98, 41, 84, 85, 87, 73, 18, 6, 9, 97, 65, 103, 95, 36, 100, 23, 8, 43, 68, 76, 116, 60, 62, 44, 40, 59, 15, 12, 30, 113, 63, 114, 81, 69, 119, 19, 7, 49, 86, 89, 111, 67, 22, 4, 10, 14, 38, 64, 80, 102, 57, 108, 34, 61, 106, 42, 58, 39, 77, 71, 109, 53] else: pos = [0, 1, 2, 3, 4, 6, 7, 8, 10, 13, 14, 21, 37, 103, 36, 65, 113, 25, 80, 26, 12, 78, 24, 83, 54, 66, 114, 46, 63, 101, 109, 93, 79, 75, 51, 44, 31, 119, 43, 5, 57, 100, 11, 108, 34, 41, 69, 96, 82, 116, 68, 64, 47, 102, 52, 35, 17, 76, 110, 38, 84, 85, 86, 87, 88, 90, 91, 92, 94, 73, 74, 81, 49, 104, 48, 29, 112, 61, 20, 62, 72, 18, 60, 23, 42, 30, 115, 58, 27, 106, 98, 9, 19, 15, 39, 56, 67, 118, 55, 89, 45, 107, 95, 99, 70, 53, 33, 111, 22, 117, 32, 28, 59, 105, 40, 71, 77, 16, 97, 50]
_circle_embedding(g, pos)
return g
r""" Returns 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:`120-cell`.
EXAMPLES::
sage: g = graphs.Cell120() # long time sage: g.size() # long time 1200 sage: g.is_regular(4) # long time True sage: g.is_vertex_transitive() # long time True """ from sage.rings.rational_field import QQ from sage.rings.polynomial.polynomial_ring import polygen from sage.rings.number_field.number_field import NumberField from sage.modules.free_module import VectorSpace from sage.groups.perm_gps.permgroup_named import AlternatingGroup from sage.combinat.permutation import Permutations
x = polygen(QQ, 'x') K = NumberField(x ** 2 - x - 1, 'f') f = K.gen() K4 = VectorSpace(K, 4)
# first 216 vertices step = [(0, 0, K(a) * 2, K(b) * 2) for a in [-1, 1] for b in [-1, 1]] step += [(a * K(1), b * K(1), c * K(1), d * (2 * f - 1)) for a in [-1, 1] for b in [-1, 1] for c in [-1, 1] for d in [-1, 1]] step += [(a * (2 - f), b * f, c * f, d * f) for a in [-1, 1] for b in [-1, 1] for c in [-1, 1] for d in [-1, 1]] step += [(a * (f - 1), b * (f - 1), c * (f - 1), d * (f + 1)) for a in [-1, 1] for b in [-1, 1] for c in [-1, 1] for d in [-1, 1]] ens1 = frozenset([(v[s(1) - 1], v[s(2) - 1], v[s(3) - 1], v[s(4) - 1]) for v in step for s in Permutations(4)]) vert1 = [K4(w) for w in ens1]
# 384 more vertices step = [(0, a * (2 - f), b * K(1), c * (f + 1)) for a in [-1, 1] for b in [-1, 1] for c in [-1, 1]] step += [(0, a * (f - 1), b * f, c * (2 * f - 1)) for a in [-1, 1] for b in [-1, 1] for c in [-1, 1]] step += [(a * (f - 1), b * K(1), c * f, d * K(2)) for a in [-1, 1] for b in [-1, 1] for c in [-1, 1] for d in [-1, 1]] vert2 = [K4([v[s(1) - 1], v[s(2) - 1], v[s(3) - 1], v[s(4) - 1]]) for v in step for s in AlternatingGroup(4)]
# all vertices together U = vert1 + vert2
g = Graph([list(range(600)), lambda i, j: U[i].inner_product(U[j]) == 6*f-2])
from sage.graphs.graph_plot import _circle_embedding pos = [0, 1, 3, 5, 6, 7, 8, 9, 11, 12, 14, 15, 16, 17, 20, 21, 23, 24, 25, 27, 33, 40, 47, 49, 76, 77, 216, 217, 218, 219, 220, 222, 224, 225, 226, 230, 231, 232, 233, 235, 238, 241, 242, 245, 247, 249, 251, 253, 260, 261, 211, 66, 26, 307, 598, 305, 187, 374, 311, 205, 296, 108, 366, 172, 255, 89, 229, 81, 529, 548, 439, 382, 166, 496, 313, 484, 402, 234, 530, 256, 358, 406, 553, 577, 583, 401, 334, 417, 257, 438, 373, 544, 509, 365, 378, 487, 377, 390, 349, 325, 65, 78, 184, 13, 185, 18, 210, 84, 145, 83, 180, 158, 118, 109, 103, 130, 105, 51, 178, 155, 110, 85, 206, 95, 204, 190, 514, 513, 515, 466, 467, 441, 442, 587, 585, 576, 565, 564, 566, 540, 506, 436, 435, 424, 507, 543, 545, 547, 582, 440, 169, 63, 29, 575, 237, 549, 37, 375, 430, 159, 457, 61, 331, 208, 498, 39, 578, 48, 244, 486, 411, 364, 73, 455, 321, 240, 381, 542, 243, 500, 343, 333, 271, 518, 552, 357, 314, 299, 499, 412, 376, 596, 561, 319, 400, 264, 388, 362, 355, 386, 87, 186, 52, 99, 125, 113, 36, 121, 41, 127, 149, 100, 31, 137, 177, 43, 32, 45, 62, 191, 188, 106, 195, 141, 142, 96, 489, 491, 490, 475, 474, 447, 448, 589, 588, 517, 472, 473, 471, 450, 419, 519, 521, 468, 562, 594, 595, 488, 554, 413, 167, 116, 4, 557, 504, 536, 170, 389, 410, 128, 559, 203, 348, 147, 477, 22, 516, 162, 423, 266, 274, 320, 144, 246, 395, 437, 363, 452, 425, 478, 315, 312, 428, 288, 270, 344, 323, 493, 479, 275, 387, 286, 284, 347, 359, 462, 336, 368, 392, 324, 44, 75, 69, 46, 57, 138, 35, 80, 88, 199, 70, 152, 161, 181, 34, 207, 164, 71, 115, 55, 163, 72, 171, 93, 165, 124, 300, 301, 302, 303, 304, 306, 308, 309, 310, 290, 291, 292, 293, 295, 298, 277, 278, 281, 283, 285, 287, 265, 272, 273, 19, 10, 107, 223, 418, 221, 67, 338, 227, 196, 236, 91, 354, 154, 267, 30, 289, 215, 469, 464, 571, 346, 151, 508, 397, 520, 318, 294, 470, 268, 370, 322, 445, 421, 427, 317, 394, 597, 269, 570, 337, 460, 497, 353, 342, 523, 341, 330, 361, 385, 126, 92, 94, 176, 135, 117, 114, 197, 214, 179, 60, 42, 198, 202, 102, 101, 174, 104, 146, 90, 38, 111, 122, 157, 153, 133, 502, 501, 503, 550, 551, 573, 574, 431, 429, 420, 433, 432, 434, 456, 494, 568, 567, 580, 495, 459, 461, 463, 426, 572, 182, 58, 82, 443, 297, 465, 86, 339, 586, 209, 541, 140, 391, 143, 510, 28, 422, 213, 280, 522, 591, 352, 120, 563, 405, 276, 345, 458, 279, 512, 379, 393, 259, 482, 444, 369, 398, 239, 511, 592, 340, 416, 453, 403, 316, 252, 328, 350, 367, 326, 2, 175, 97, 139, 74, 131, 173, 134, 193, 192, 132, 79, 50, 200, 64, 150, 201, 194, 212, 183, 54, 56, 98, 123, 112, 156, 525, 527, 526, 535, 534, 555, 556, 409, 408, 481, 532, 533, 531, 558, 599, 483, 485, 528, 454, 414, 415, 524, 446, 593, 160, 59, 68, 449, 492, 476, 148, 329, 590, 119, 451, 189, 360, 53, 537, 129, 480, 136, 579, 254, 262, 404, 168, 282, 335, 569, 351, 560, 581, 538, 399, 396, 584, 228, 258, 380, 407, 505, 539, 263, 327, 250, 248, 383, 371, 546, 372, 356, 332, 384] _circle_embedding(g, pos)
return g
r""" Return the Suzuki Graph.
The Suzuki graph has 1782 vertices, and is strongly regular with parameters `(1782,416,100,96)`. Known as S.15 in [Hu75]_.
.. NOTE::
It takes approximately 50 seconds to build this graph. Do not be too impatient.
EXAMPLES::
sage: g = graphs.SuzukiGraph(); g # optional database_gap internet # not tested Suzuki graph: Graph on 1782 vertices sage: g.is_strongly_regular(parameters=True) # optional database_gap internet # not tested (1782, 416, 100, 96) """ from sage.groups.perm_gps.permgroup_named import SuzukiSporadicGroup g = Graph() g.add_edges(SuzukiSporadicGroup().orbit((1,2),"OnSets")) g.relabel() g.name("Suzuki graph") return g
r""" Returns the Hall-Janko graph.
For more information on the Hall-Janko graph, see its :wikipedia:`Wikipedia page <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 <http://brauer.maths.qmul.ac.uk/Atlas/v3/permrep/J2G1-p100B0>`_.
INPUT:
- ``from_string`` (boolean) -- 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. It is set to ``True`` by default.
EXAMPLES::
sage: g = graphs.HallJankoGraph() sage: g.is_regular(36) True sage: g.is_vertex_transitive() 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
Some other properties that we know how to check::
sage: g.diameter() 2 sage: g.girth() 3 sage: factor(g.characteristic_polynomial()) (x - 36) * (x - 6)^36 * (x + 4)^63
TESTS::
sage: gg = graphs.HallJankoGraph(from_string=False) # long time sage: g == gg # long time True """
"wCE@o_K_?GB@?WGAouC@OsN_?GB@O[GB`A@@_e?@OgLB_{Q_?GC@O[GAOs" "OCWGBA?kKBPA@?_[KB_{OCPKT`o_RD`]A?o[HBOwODW?DA?cIB?wRDP[X`" "ogKB_{QD@]B@o_KBPWXE`mC@o_JB?{PDPq@?oWGA_{OCPKTDp_YEwCA@_c" "IBOwOC`OX_OGB@?WPDPcYFg?C@_gKBp?SE@cYF`{_`?SGAOoOC`_\\FwCE" "A?gKBO{QD@k[FqI??_OFA_oQE@k\\Fq?`GgCB@pGRD@_XFP{a_?SE@ocIA" "ooNCPOUEqU@?oODA?cJB_{UEqYC@_kLC@CREPk]GAGbHgCA@?SMBpCSD`[" "YFq?`Ga]BA?gPC`KSD`_\\Fa?cHWGB@?[IAooPD`[WF@s^HASeIg?@@OcP" "C`KYF@w^GQ[h`O[HAooMC@CQCpSVEPk\\GaSeIG?FA?kLB_{OC`OVE@cYG" "QUA@?WLBp?PC`KVEqKgJg?DA?sMBpCSDP[WEQKfIay@?_KD@_[GC`SUE@k" "[FaKdHa[k_?OLC@CRD@WVEpo^HAWfIAciIqoo_?CB@?kMCpOUE`o\\GAKg" "IQgq_?GD@_[GB?{OCpWVE@cYFACaHAWhJR?q_?CC@_kKBpC\\GACdHa[kJ" "a{o_?CA?oOFBpGRD@o\\GaKdIQonKrOt_?WHA`?PC`KTD`k]FqSeIaolJr" "CqLWCA@OkKCPGRDpcYGAKdIAgjJAsmJr?t__OE@ogJB_{XEps`HA[gIQwn" "KWKGAOoMBpGUE`k[Fa?aHqckJbSuLw?@?_SHA_kLC@OTFPw^GaOkLg?B@?" "[HA_{PDP_XFaCbHa[gIqooKRWx_?CFBpOTE@cZFPw^GACcHQgoKrSvMwWG" "BOwQCp_YFP{`HASfJAwnKRSx_OSSDP[WEq?aGqSfIQsoKR_zNWCE@o_HA_" "sREPg^GAGcHQWfIAciKbOxNg?A@__IAooMC`KTD`g\\GAKcIasoKrOtLb[" "wMbyCA?cKBp?TD`[WE`s^GQGbHqcjJrK{NRw~_oODA?sNC@CQCpOZF@s]G" "QOfIaolJrGsLbk}_?OFA_sRD@SVE`k[HQcjJa{qLb[xMb|?_OOFA?cIAos" "RDP_ZFa?aGqOfIAsuMbk{Ns@@OsQAA_sPDPWXE`o\\FqKdIQkkJrCuLr_x" "Mro}NsDAPG?@@OWFApKUE@o`IQolKRKsLrc|NsQC@OWGAOgJCpOWE`o_GQ" "KiIqwnKr_~OcLCPS]A?oWHA_oMBpKSDP[\\FagjKBWxMbk{OSQ@@O_IAoo" "LBpCSD`g\\FaGbHQWgIQgmKRKwMRl?PgGC@OWHB@KSE@c[FqCaGqSeIAkk" "KBCqLBSuMBpGQWCA@?cKBOwRDPWVE@k^GqOfJr?pKbKtLrs}OSHDQwKIBO" "wPD@WWEQ?`HQWfIQglKBOtLbo}Ns@@OsTE_?kLCpWWHA[gIqomKBGwMRgz" "NBw~OSPDPc\\H_?CFAOoLCPSVE`o\\GAOeJAwpKbKtMrx?Qcq??OKFA?gJ" "B`?QDpcYEpo]FqKfIAgjJB?qKr_{NS@A__SE@o_HBO{PC`OTD`{_HaciIq" "{vMbt?OcPFQCeB@?SKBOwRD@SXE`k[FPw`HQ_lKRKxNRxBPC\\HQclK_?K" "EB?sOC`OTDa?`GqWgJRCrNBw~OSHFQStMRtDQ_?KC@OoQE`k_GaOdHa[gI" "q{tMBg|Nb|?OcPMSDDQSwCB@_cJB_{OCpOVFP{dHa[jJQwqKrk}NsHBQCd" "MRtMA?oSEA_wPDp_YEpo]GAOeIq{pLBk}NsLEQCtNTDU??OKEA_oLC@[[G" "aKnKBOtLbk~OCPFQStNSDLSTgGKC@GSD`[WEpw_GQGcIAciJAwpKb_xMbk" "~QShJRc|R`_wNCPcZF@s^GAGbHA_hJR?qKrOvMRg|NsDEPsxTTgCB@?gJB" "?sMC@CUDp_]FqCaHQcjJQwtLrhCPS\\IRCtQTw?B@?SHA_wPC`_aGqOiJa" "{oKRKvMRpFQChKRtXVUTi??ocNC@KUE@cYFaGdHa_mJrKsLb[yMro|OcXI" "RdPTTddZaOgJB@?UEPk[FQCfIaolJrSvMBczNR|AOsXFQCtOTtaB@?WGAP" "?TEPo\\GAGdHqgmKBCqLR[xMb|?PC`HQs|TTt`XUtu@?o[HB?sNCPGXF@{" "_GQKcIqolJb_yNCLDPs`MRtDRTTdYUwSEA?kLB`CWF@s]FqGgIqooLRgzN" "RxFQSlMSDDQTDXVUTi@?_KDAOoLBpKUEQOfIa{oLB_xMrt?Os\\HQcpMST" "HSTtl[VT}A@ocJBOwSD`_XEpo_Ha_mJrKtLbgzNSTGQspLRtDUUDp\\WG[" "HB`CQCp[WFQGgIQgkJQ{rLbc{Nc@APsdLRt@PSt\\WUtt_Wn")
else:
# The following construction is due to version 3 of the ATLAS of # Finite Group Representations, specifically the page at # http://brauer.maths.qmul.ac.uk/Atlas/v3/permrep/J2G1-p100B0 .
from sage.interfaces.gap import gap gap.eval("g1 := (1,84)(2,20)(3,48)(4,56)(5,82)(6,67)(7,55)(8,41)" "(9,35)(10,40)(11,78)(12,100)(13,49)(14,37)(15,94)(16,76)" "(17,19)(18,44)(21,34)(22,85)(23,92)(24,57)(25,75)(26,28)" "(27,64)(29,90)(30,97)(31,38)(32,68)(33,69)(36,53)(39,61)" "(42,73)(43,91)(45,86)(46,81)(47,89)(50,93)(51,96)(52,72)" "(54,74)(58,99)(59,95)(60,63)(62,83)(65,70)(66,88)(71,87)" "(77,98)(79,80);")
gap.eval("g2 := (1,80,22)(2,9,11)(3,53,87)(4,23,78)(5,51,18)" "(6,37,24)(8,27,60)(10,62,47)(12,65,31)(13,64,19)" "(14,61,52)(15,98,25)(16,73,32)(17,39,33)(20,97,58)" "(21,96,67)(26,93,99)(28,57,35)(29,71,55)(30,69,45)" "(34,86,82)(38,59,94)(40,43,91)(42,68,44)(46,85,89)" "(48,76,90)(49,92,77)(50,66,88)(54,95,56)(63,74,72)" "(70,81,75)(79,100,83);")
gap.eval("G := Group([g1,g2]);") edges = gap('Orbit(G,[1,5],OnSets)').sage() g = Graph([(int(u), int(v)) for u,v in edges]) g.relabel()
r""" Returns the Balaban 10-cage.
The Balaban 10-cage is a 3-regular graph with 70 vertices and 105 edges. See its :wikipedia:`Wikipedia page <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`` -- two embeddings are available, and can be selected by setting ``embedding`` to be either 1 or 2.
EXAMPLES::
sage: g = graphs.Balaban10Cage() sage: g.girth() 10 sage: g.chromatic_number() 2 sage: g.diameter() 6 sage: g.is_hamiltonian() True sage: g.show(figsize=[10,10]) # long time
TESTS::
sage: graphs.Balaban10Cage(embedding='foo') Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2. """
21, 9,-13, -31, -9, 25, 17, 9, -31, 27, -9, 17, -19, -29, 27, -17, -9, -29, 33, -25,25, -21, 17, -17, 29, 35, -29, 17, -17, 21, -25, 25, -33, 29, 9, 17, -27, 29, 19, -17, 9, -27, 31, -9, -17, -25, 9, 31, 13, -9, -21, -33, -17, -29, 29]
return g
20, 55, 57]
r""" Returns the Balaban 11-cage.
For more information, see this :wikipedia:`Wikipedia article on the Balaban 11-cage <Balaban_11-cage>`.
INPUT:
- ``embedding`` -- three embeddings are available, and can be selected by setting ``embedding`` to be 1, 2, or 3.
- The first embedding is the one appearing on page 9 of the Fifth Annual Graph Drawing Contest report [FAGDC]_. It separates vertices based on their eccentricity (see :meth:`eccentricity() <sage.graphs.generic_graph.GenericGraph.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 :meth:`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() 64
Our many embeddings::
sage: g1 = graphs.Balaban11Cage(embedding=1) sage: g2 = graphs.Balaban11Cage(embedding=2) sage: g3 = graphs.Balaban11Cage(embedding=3) sage: g1.show(figsize=[10,10]) # long time sage: g2.show(figsize=[10,10]) # long time sage: g3.show(figsize=[10,10]) # long time
Proof that the embeddings are the same graph::
sage: g1.is_isomorphic(g2) # g2 and g3 are obviously isomorphic True
TESTS::
sage: graphs.Balaban11Cage(embedding='xyzzy') Traceback (most recent call last): ... ValueError: The value of embedding must be 1, 2, or 3.
REFERENCES:
.. [FAGDC] Fifth Annual Graph Drawing Contest P. Eaded, J. Marks, P.Mutzel, S. North http://www.merl.com/papers/docs/TR98-16.pdf """ 0.8 * float(cos(2*((8*j + i)*pi/64 + pi/128))), 0.8 * float(sin(2*((8*j + i)*pi/64 + pi/128))) ] 1.1 * float(cos(2*((4*j + i)*pi/32 + pi/64))), 1.1 * float(sin(2*((4*j + i)*pi/32 + pi/64))) ] 1.4 * float(cos(2*((2*j + i)*pi/16 + pi/32))), 1.4 * float(sin(2*((2*j + i)*pi/16 + pi/32))) ]
"00": ["11"], "01": ["10"], "02": ["53"], "03": ["52"], "11": ["20"], "10": ["21"], "53": ["22"], "52": ["23"], "20": ["31"], "21": ["30"], "22": ["33"], "23": ["32"], "31": ["40"], "30": ["41"], "33": ["43"], "32": ["42"], "40": ["50"], "41": ["51"], "43": ["12"], "42": ["13"], "50": ["61"], "51": ["60"], "12": ["63"], "13": ["62"], "61": ["70"], "60": ["71"], "63": ["72"], "62": ["73"], "70": ["01"], "71": ["00"], "72": ["03"], "73": ["02"],
"04": ["35"], "05": ["34"], "06": ["37"], "07": ["36"], "35": ["64"], "34": ["65"], "37": ["66"], "36": ["67"], "64": ["55"], "65": ["54"], "66": ["17"], "67": ["16"], "55": ["45"], "54": ["44"], "17": ["46"], "16": ["47"], "45": ["74"], "44": ["75"], "46": ["76"], "47": ["77"], "74": ["25"], "75": ["24"], "76": ["27"], "77": ["26"], "25": ["14"], "24": ["15"], "27": ["56"], "26": ["57"], "14": ["05"], "15": ["04"], "56": ["07"], "57": ["06"],
"100": ["03", "04"], "110": ["10", "12"], "101": ["01", "06"], "111": ["11", "13"], "102": ["00", "07"], "112": ["14", "16"], "103": ["02", "05"], "113": ["15", "17"],
"120": ["22", "24"], "130": ["33", "36"], "121": ["20", "26"], "131": ["32", "37"], "122": ["21", "27"], "132": ["31", "34"], "123": ["23", "25"], "133": ["30", "35"],
"140": ["43", "45"], "150": ["50", "52"], "141": ["40", "46"], "151": ["51", "53"], "142": ["41", "47"], "152": ["54", "56"], "143": ["42", "44"], "153": ["55", "57"],
"160": ["60", "66"], "170": ["73", "76"], "161": ["63", "65"], "171": ["72", "77"], "162": ["62", "64"], "172": ["71", "74"], "163": ["61", "67"], "173": ["70", "75"],
"104": ["100", "102", "105"], "114": ["110", "111", "115"], "105": ["101", "103", "104"], "115": ["112", "113", "114"],
"124": ["120", "121", "125"], "134": ["130", "131", "135"], "125": ["122", "123", "124"], "135": ["132", "133", "134"],
"144": ["140", "141", "145"], "154": ["150", "151", "155"], "145": ["142", "143", "144"], "155": ["152", "153", "154"],
"164": ["160", "161", "165"], "174": ["170", "171", "175"], "165": ["162", "163", "164"], "175": ["172", "173", "174"] }
-29, -16, 41, -11, -26, 15, 22, -51, -35, 36, 52, -14, -33, -26, -46, 52, 26, 16, 43, 33, -15, 17, -53, 23, -42, -35, -28, 30, -22, 45, -44, 16, -38, -16, 50, -55, 20, 28, -17, -43, 47, 34, -26, -41, 11, -36, -23, -16, 41, 17, -51, 26, -33, 47, 17, -11, -20, -30, 21, 29, 36, -43, -52, 10, 39, -28, -17, -52, 51, 26, 37, -17, 10, -10, -45, -34, 17, -26, 27, -21, 46, 53, -10, 29, -50, 35, 15, -47, -29, -41, 26, 33, 55, -17, 42, -26, -36, 16]
70, 36, 94, 27, 25, 10, 8, 45, 60, 14, 64, 80, 82, 109, 107, 49, 98] 75, 11, 61, 28, 9, 37, 26, 46, 95, 13, 63, 81, 83, 108, 106, 48, 97] 99] 96]
else:
r""" Returns the Bidiakis cube.
For more information, see this `Wikipedia article on the Bidiakis cube <http://en.wikipedia.org/wiki/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 sage: g.order() 12 sage: g.size() 18 sage: g.is_regular(3) True
It is a Hamiltonian graph with diameter 3 and girth 4::
sage: g.is_hamiltonian() True sage: g.diameter() 3 sage: 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: bool(g.characteristic_polynomial() == expand((x - 3) * (x - 2) * (x^4) * (x + 1) * (x + 2) * (x^2 + x - 4)^2)) True sage: g.chromatic_number() 3 """ 0:[1,6,11], 1:[2,5], 2:[3,10], 3:[4,9], 4:[5,8], 5:[6], 6:[7], 7:[8,11], 8:[9], 9:[10], 10:[11]} 0: [0, 1], 1: [0.5, 0.866025403784439], 2: [0.866025403784439, 0.500000000000000], 3: [1, 0], 4: [0.866025403784439, -0.5], 5: [0.5, -0.866025403784439], 6: [0, -1], 7: [-0.5, -0.866025403784439], 8: [-0.866025403784439, -0.5], 9: [-1, 0], 10: [-0.866025403784439, 0.5], 11: [-0.5, 0.866025403784439]}
r""" Returns the Biggs-Smith graph.
For more information, see this :wikipedia:`Wikipedia article on the Biggs-Smith graph <Biggs-Smith_graph>`.
INPUT:
- ``embedding`` -- two embeddings are available, and can be selected by setting ``embedding`` to be 1 or 2.
EXAMPLES:
Basic properties::
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() 2448 sage: g.show(figsize=[10, 10]) # long time
The other embedding::
sage: graphs.BiggsSmithGraph(embedding=2).show()
TESTS::
sage: graphs.BiggsSmithGraph(embedding='xyzzy') Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2.
""" 21, 14, 48, -16, -36, -43, 28, -17, 21, 29, -43, 46, -24, 28, -38, -14, -50, -45, 21, 8, 27, -21, 20, -37, 39, -34, -44, -8, 38, -21, 25, 15, -34, 18, -28, -41, 36, 8, -29, -21, -48, -28, -20, -47, 14, -8, -15, -27, 38, 24, -48, -18, 25, 38, 31, -25, 24, -46, -14, 28, 11, 21, 35, -39, 43, 36, -38, 14, 50, 43, 36, -11, -36, -24, 45, 8, 19, -25, 38, 20, -24, -14, -21, -8, 44, -31, -38, -28, 37]
[17, 101, 25, 66, 20, 38, 53, 89, 48, 75, 56, 92, 45, 78, 34, 28, 63], [18, 36, 26, 65, 19, 37, 54, 90, 47, 76, 55, 91, 46, 77, 35, 27, 64], [21, 39, 52, 88, 49, 74, 57, 93, 44, 79, 33, 29, 62, 83, 100, 24, 67], [22, 97, 51, 96, 50, 95, 58, 94, 59, 80, 60, 81, 61, 82, 99, 23, 98], [30, 86, 84, 72, 70, 68, 42, 40, 31, 87, 85, 73, 71, 69, 43, 41, 32]]
# central orbits
# lower orbits shift=2)
# upper orbits
else:
r""" Returns 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:`Blanusa_snarks`.
.. SEEALSO::
* :meth:`~sage.graphs.graph_generators.GraphGenerators.BlanusaSecondSnarkGraph`.
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() 8 """ 3:[8],13:[9],12:[16], 10:[15],11:[6],14:[2]}, name="Blanusa First Snark Graph")
r""" Returns 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:`Blanusa_snarks`.
.. SEEALSO::
* :meth:`~sage.graphs.graph_generators.GraphGenerators.BlanusaFirstSnarkGraph`.
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() 4 """ (0,6):[(0,4)],(0,7):[(0,1)],(1,7):[(1,2)], (1,0):[(1,6)],(1,3):[(1,5)]}, name="Blanusa Second Snark Graph")
[(0,(2*i)%5) for i in range(5)], center = (-1.5,0), shift = .5) [(1,(2*i)%5) for i in range(5)], center = (1.5,0))
[(0,i) for i in range(5,8)]+[0]*4, center = (-1.2,0), shift = 2.5, radius = 2.2) [(1,i) for i in range(5,8)]+[0]*4, center = (1.2,0), shift = -1, radius = 2.2)
r""" Returns the Brinkmann graph.
For more information, see the `Wikipedia article on the Brinkmann graph <http://en.wikipedia.org/wiki/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 sage: G.order() 21 sage: G.size() 42 sage: G.is_regular(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
The Brinkmann graph is also Hamiltonian with chromatic number 4::
sage: G.is_hamiltonian() True sage: G.chromatic_number() 4
Its automorphism group is isomorphic to `D_7`::
sage: ag = G.automorphism_group() sage: ag.is_isomorphic(DihedralGroup(7)) True """ 0: [2,5,7,13], 1: [3,6,7,8], 2: [4,8,9], 3: [5,9,10], 4: [6,10,11], 5: [11,12], 6: [12,13], 7: [15,20], 8: [14,16], 9: [15,17], 10: [16,18], 11: [17,19], 12: [18,20], 13: [14,19], 14: [17,18], 15: [18,19], 16: [19,20], 17: [20]} 0: [0, 4], 1: [3.12732592987212, 2.49395920743493], 2: [3.89971164872729, -0.890083735825258], 3: [1.73553495647023, -3.60387547160968], 4: [-1.73553495647023, -3.60387547160968], 5: [-3.89971164872729, -0.890083735825258], 6: [-3.12732592987212, 2.49395920743493], 7: [0.867767478235116, 1.80193773580484], 8: [1.94985582436365, 0.445041867912629], 9: [1.56366296493606, -1.24697960371747], 10: [0, -2], 11: [-1.56366296493606, -1.24697960371747], 12: [-1.94985582436365, 0.445041867912629], 13: [-0.867767478235116, 1.80193773580484], 14: [0.433883739117558, 0.900968867902419], 15: [0.974927912181824, 0.222520933956314], 16: [0.781831482468030, -0.623489801858733], 17: [0, -1], 18: [-0.781831482468030, -0.623489801858733], 19: [-0.974927912181824, 0.222520933956315], 20: [-0.433883739117558, 0.900968867902419]}
r""" Returns 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 <http://www.win.tue.nl/~aeb/graphs/Brouwer-Haemers.html>`_.
EXAMPLES::
sage: g = graphs.BrouwerHaemersGraph() sage: g 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 (81, 20, 1, 6)
Its has as eigenvalues `20,2` and `-7`::
sage: set(g.spectrum()) == {20,2,-7} True """
18, 19, 20, 21, 22, 23, 24, 25, 26, 48, 49, 50, 51, 52, 53, 45, 46, 47, 30, 31, 32, 33, 34, 35, 27, 28, 29, 39, 40, 41, 42, 43, 44, 36, 37, 38, 69, 70, 71, 63, 64, 65, 66, 67, 68, 78, 79, 80, 72, 73, 74, 75, 76, 77, 60, 61, 62, 54, 55, 56, 57, 58, 59]
r""" Create 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
The Bucky Ball can also be created by extracting the 1-skeleton of the Bucky Ball polyhedron, but this is much slower. ::
sage: g = polytopes.buckyball().vertex_graph() sage: g.remove_loops() sage: h = graphs.BuckyBall() sage: g.is_isomorphic(h) True
The graph is returned along with an attractive embedding. ::
sage: g = graphs.BuckyBall() sage: g.plot(vertex_labels=False, vertex_size=10).show() # long time """ (2, 3), (2, 36), (3, 17), (4, 6), (4, 8), (4, 12), (5, 7), (5, 9), (5, 16), (6, 7), (6, 20), (7, 21), (8, 9), (8, 56), (10, 11), (10, 12), (10, 20), (11, 27), (11, 47), (12, 13), (13, 46), (13, 54), (14, 15), (14, 16), (14, 21), (15, 25), (15, 41), (16, 17), (17, 40), (18, 19), (18, 20), (18, 26), (19, 21), (19, 24), (22, 23), (22, 31), (22, 34), (23, 25), (23, 38), (24, 25), (24, 30), (26, 27), (26, 30), (27, 29), (28, 29), (28, 31), (28, 35), (29, 44), (30, 31), (32, 34), (32, 39), (32, 50), (33, 35), (33, 45), (33, 51), (34, 35), (36, 37), (36, 40), (37, 39), (37, 52), (38, 39), (38, 41), (40, 41), (42, 43), (42, 46), (42, 55), (43, 45), (43, 53), (44, 45), (44, 47), (46, 47), (48, 49), (48, 52), (49, 53), (49, 57), (50, 51), (50, 52), (51, 53), (54, 55), (54, 56), (55, 57), (56, 58), (57, 59), (58, 59) ]
0 : (1.00000000000000, 0.000000000000000), 1 : (-1.00000000000000, 0.000000000000000), 2 : (0.500000000000000, 0.866025403784439), 3 : (-0.500000000000000, 0.866025403784439), 4 : (-0.252886764483159, -0.146004241548845), 5 : (-0.368953972399043, 0.0928336233191176), 6 : (-0.217853192651371, -0.0480798425451855), 7 : (-0.255589950938772, 0.0495517623332213), 8 : (-0.390242139418333, -0.225306404242310), 9 : (-0.586398703939125, -0.0441575936410641), 10: (-0.113926229169631, -0.101751920396670), 11: (-0.0461308635969359, -0.0928422349110366), 12: (-0.150564961379772, -0.164626477859040), 13: (-0.0848818904865275, -0.246123271631605), 14: (-0.170708060452244, 0.196571509298384), 15: (-0.0672882312715990, 0.212706320404226), 16: (-0.264873262319233, 0.273106701265196), 17: (-0.254957754106411, 0.529914971178085), 18: (-0.103469165775548, 0.00647061768205703), 19: (-0.113590051906687, 0.0655812470455896), 20: (-0.145082862532183, -0.0477870484199328), 21: (-0.179962687765901, 0.103901506225732), 22: (0.0573383021786124, 0.0863716172289798), 23: (0.0311566333625530, 0.149538968816603), 24: (-0.0573383021786121, 0.0863716172289799), 25: (-0.0311566333625527, 0.149538968816603), 26: (-0.0517345828877740, 0.00161765442051429), 27: (-0.0244663616211774, -0.0456122902452611), 28: (0.0517345828877743, 0.00161765442051431), 29: (0.0244663616211777, -0.0456122902452611), 30: (-0.0272682212665964, 0.0439946358247470), 31: (0.0272682212665968, 0.0439946358247470), 32: (0.179962687765901, 0.103901506225732), 33: (0.145082862532184, -0.0477870484199329), 34: (0.113590051906687, 0.0655812470455895), 35: (0.103469165775548, 0.00647061768205698), 36: (0.254957754106411, 0.529914971178085), 37: (0.264873262319233, 0.273106701265196), 38: (0.0672882312715993, 0.212706320404226), 39: (0.170708060452245, 0.196571509298384), 40: (1.59594559789866e-16, 0.450612808484620), 41: (2.01227923213310e-16, 0.292008483097691), 42: (0.0848818904865278, -0.246123271631605), 43: (0.150564961379773, -0.164626477859040), 44: (0.0461308635969362, -0.0928422349110366), 45: (0.113926229169631, -0.101751920396670), 46: (1.66533453693773e-16, -0.207803012451463), 47: (1.80411241501588e-16, -0.131162494091179), 48: (0.586398703939126, -0.0441575936410641), 49: (0.390242139418333, -0.225306404242310), 50: (0.255589950938772, 0.0495517623332212), 51: (0.217853192651372, -0.0480798425451855), 52: (0.368953972399044, 0.0928336233191175), 53: (0.252886764483159, -0.146004241548845), 54: (-0.104080710079810, -0.365940324584313), 55: (0.104080710079811, -0.365940324584313), 56: (-0.331440949832714, -0.485757377537020), 57: (0.331440949832715, -0.485757377537021), 58: (-0.500000000000000, -0.866025403784438), 59: (0.500000000000000, -0.866025403784439) }
r""" Return the Gosset graph.
The Gosset graph is the skeleton of the :meth:`~sage.geometry.polyhedron.library.Polytopes.Gosset_3_21` polytope. It has with 56 vertices and degree 27. For more information, see the :wikipedia:`Gosset_graph`.
EXAMPLES::
sage: g = graphs.GossetGraph(); g Gosset Graph: Graph on 56 vertices
sage: g.order(), g.size() (56, 756)
TESTS::
sage: g.is_isomorphic(polytopes.Gosset_3_21().graph()) # not tested (~16s) True """ '?N~o^}?A`}F_Kbbm_[QZ\\_]Cj\\oN_dm{BzB{?]WIMM@tPQRYBYRPIuAyJgQv?'+ '|Bxb_M[kWIR@jTQcciDjShXCkFMgpwqBKxeKoS`TYqdTCcKtkdKwWQXrbEZ@OdU'+ 'mITZ@_e[{KXn?YPABzvY?IcO`zvYg@caC\\zlf?BaGR]zb{?@wOjv`~w??N_n_~'+ '~w???^_^~~{')
33, 15, 54, 30, 17, 21, 10, 13, 36, 31, 55, 53, 51, 49, 12, 32, 5, 37, 27, 46, 47, 48, 11, 52, 29, 20, 39, 41, 22, 40, 1, 25, 38, 34, 45, 42, 19, 24]
r""" Returns the double star snark.
The double star snark is a 3-regular graph on 30 vertices. See the :wikipedia:`Wikipedia page on the double star snark <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() False sage: g.automorphism_group().cardinality() 80 sage: g.show() """
, 1: [0, 2, 11] , 2: [1, 3, 7] , 3: [2, 4, 18] , 4: [3, 5, 14] , 5: [10, 4, 6] , 6: [5, 21, 7] , 7: [8, 2, 6] , 8: [9, 13, 7] , 9: [24, 8, 10] , 10: [9, 11, 5] , 11: [1, 10, 12] , 12: [11, 27, 13] , 13: [8, 12, 14] , 14: [0, 4, 13] , 15: [0, 16, 29] , 16: [15, 20, 23] , 17: [25, 18, 28] , 18: [3, 17, 19] , 19: [18, 26, 23] , 20: [16, 28, 21] , 21: [20, 6, 22] , 22: [26, 21, 29] , 23: [16, 24, 19] , 24: [25, 9, 23] , 25: [24, 17, 29] , 26: [27, 19, 22] , 27: [12, 26, 28] , 28: [17, 27, 20] , 29: [25, 22, 15] }
r""" Returns the Meredith Graph.
The Meredith Graph is a 4-regular 4-connected non-hamiltonian graph. For more information on the Meredith Graph, see the :wikipedia:`Meredith_graph`.
EXAMPLES::
sage: g = graphs.MeredithGraph() sage: g.is_regular(4) True sage: g.order() 70 sage: g.size() 140 sage: g.radius() 7 sage: g.diameter() 8 sage: g.girth() 4 sage: g.chromatic_number() 3 sage: g.is_hamiltonian() # long time False """
# Edges between copies of K_{4,3}
# Edges inside of the K_{4,3}s.
r""" Returns the Kittell Graph.
For more information, see the `Wolfram page about the Kittel Graph <http://mathworld.wolfram.com/KittellGraph.html>`_.
EXAMPLES::
sage: g = graphs.KittellGraph() sage: g.order() 23 sage: g.size() 63 sage: g.radius() 3 sage: g.diameter() 4 sage: g.girth() 3 sage: g.chromatic_number() 4 """ 2: [0, 1, 11, 4, 14], 3: [16, 12, 4, 5, 14], 4: [0, 2, 3, 5, 14], 5: [0, 16, 3, 4, 6], 6: [0, 5, 7, 15, 16, 17, 18], 7: [0, 1, 6, 8, 13, 18], 8: [9, 18, 19, 13, 7], 9: [8, 10, 19, 20, 13], 10: [1, 9, 11, 13, 20, 21], 11: [1, 2, 10, 12, 14, 15, 21], 12: [11, 16, 3, 14, 15], 13: [8, 1, 10, 9, 7], 14: [11, 12, 2, 3, 4], 15: [6, 11, 12, 16, 17, 21, 22], 16: [3, 12, 5, 6, 15], 17: [18, 19, 22, 6, 15], 18: [8, 17, 19, 6, 7], 19: [8, 9, 17, 18, 20, 22], 20: [9, 10, 19, 21, 22], 21: [10, 11, 20, 22, 15], 22: [17, 19, 20, 21, 15]}, name = "Kittell Graph")
r""" Returns 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 `<http://www.win.tue.nl/~aeb/graphs/Cameron.html>`_.
EXAMPLES::
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)
"""
21, 24, 25, 26, 27, 29, 31, 34, 35, 38, 39, 96, 97, 101, 105, 51, 117, 198, 32, 196, 201, 131, 167, 199, 197, 86, 102, 195, 200, 186, 144, 202, 177, 44, 53, 58, 45, 48, 54, 43, 57, 50, 46, 59, 133, 169, 104, 188, 118, 208, 157, 52, 207, 209, 132, 204, 13, 187, 33, 203, 70, 145, 103, 168, 178, 87, 124, 123, 125, 111, 120, 116, 119, 112, 95, 114, 115, 137, 218, 213, 108, 76, 77, 74, 62, 64, 67, 63, 68, 69, 61, 41, 75, 73, 66, 71, 72, 60, 22, 230, 151, 184, 138, 193, 109, 228, 174, 214, 219, 93, 126, 143, 150, 146, 224, 181, 16, 223, 171, 90, 135, 106, 205, 211, 121, 148, 160, 216, 222, 190, 36, 55, 185, 175, 94, 139, 110, 215, 152, 220, 229, 194, 40, 128, 99, 141, 173, 154, 82, 156, 164, 159, 28, 127, 158, 65, 162, 163, 153, 161, 155, 140, 98, 47, 113, 84, 180, 30, 129, 179, 183, 165, 176, 142, 100, 49, 134, 210, 170, 147, 91, 37, 206, 182, 191, 56, 136, 225, 221, 149, 227, 217, 17, 107, 172, 212, 122, 226, 23, 85, 42, 80, 92, 81, 89, 78, 83, 88, 79, 130, 192, 189, 166]
r""" Returns 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 this `Wikipedia article on the Chvatal graph <http://en.wikipedia.org/wiki/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
TESTS::
sage: import networkx sage: G = graphs.ChvatalGraph() sage: G.is_isomorphic(Graph(networkx.chvatal_graph())) True """ 5:[10, 11], 6:[10, 11], 7:[8, 11], 8:[10], 9:[10, 11]}
r""" Return the Clebsch graph.
EXAMPLES::
sage: g = graphs.ClebschGraph() sage: g.automorphism_group().cardinality() 1920 sage: g.girth() 4 sage: g.chromatic_number() 4 sage: g.diameter() 2 sage: g.show(figsize=[10, 10]) # long time """
r""" Return the Coxeter graph.
See the :wikipedia:`Wikipedia page on the Coxeter graph <Coxeter_graph>`.
EXAMPLES::
sage: g = graphs.CoxeterGraph() sage: g.automorphism_group().cardinality() 336 sage: g.girth() 7 sage: g.chromatic_number() 3 sage: g.diameter() 4 sage: g.show(figsize=[10, 10]) # long time """ 27: [6, 22, 14], 24: [0, 7, 18], 25: [8, 15, 2], 26: [10, 16, 23], }, pos={})
r""" 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:`Dejter_graph`.
EXAMPLES::
sage: g = graphs.DejterGraph(); g Dejter Graph: Graph on 112 vertices sage: g.is_regular(k=6) True sage: g.girth() 4 """
for x in HammingCode(FiniteField(2), 3)])
""" Returns the Desargues graph.
PLOTTING: The layout chosen is the same as on the cover of [1].
EXAMPLES::
sage: D = graphs.DesarguesGraph() sage: L = graphs.LCFGraph(20,[5,-5,9,-9],5) sage: D.is_isomorphic(L) True sage: D.show() # long time
REFERENCE:
- [1] Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994. """
r""" Returns the Dürer graph.
For more information, see this `Wikipedia article on the Dürer graph <http://en.wikipedia.org/wiki/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
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
Its automorphism group is isomorphic to `D_6`. ::
sage: ag = G.automorphism_group() sage: ag.is_isomorphic(DihedralGroup(6)) True """ 0: [1,5,6], 1: [2,7], 2: [3,8], 3: [4,9], 4: [5,10], 5: [11], 6: [8,10], 7: [9,11], 8: [10], 9: [11]} 0: [2, 0], 1: [1, 1.73205080756888], 2: [-1, 1.73205080756888], 3: [-2, 0], 4: [-1, -1.73205080756888], 5: [1, -1.73205080756888], 6: [1, 0], 7: [0.5, 0.866025403784439], 8: [-0.5, 0.866025403784439], 9: [-1, 0], 10: [-0.5, -0.866025403784439], 11: [0.5, -0.866025403784439]}
""" Returns the Dyck graph.
For more information, see the `MathWorld article on the Dyck graph <http://mathworld.wolfram.com/DyckGraph.html>`_ or the `Wikipedia article on the Dyck graph <http://en.wikipedia.org/wiki/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
It is non-planar and Hamiltonian, as well as bipartite (making it a bicubic graph)::
sage: G.is_planar() False sage: G.is_hamiltonian() True sage: 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
Its chromatic number is `2` and its automorphism group is of order `192`::
sage: G.chromatic_number() 2 sage: G.automorphism_group().cardinality() 192
It is a non-integral graph as it has irrational eigenvalues::
sage: G.characteristic_polynomial().factor() (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 (:meth:`ShrikhandeGraph <GraphGenerators.ShrikhandeGraph>`). """ float(sin((2*i) * pi/8))] 0.75 * pos_dict[i][1]] 0.50 * pos_dict[i][1]] 0.25 * pos_dict[i][1]]
0O00: [0O07, 0O01, 0O10], 0O10: [0O00, 0O27, 0O21], 0O01: [0O00, 0O02, 0O11], 0O11: [0O01, 0O20, 0O22], 0O02: [0O01, 0O03, 0O12], 0O12: [0O02, 0O21, 0O23], 0O03: [0O02, 0O04, 0O13], 0O13: [0O03, 0O22, 0O24], 0O04: [0O03, 0O05, 0O14], 0O14: [0O04, 0O23, 0O25], 0O05: [0O04, 0O06, 0O15], 0O15: [0O05, 0O24, 0O26], 0O06: [0O05, 0O07, 0O16], 0O16: [0O06, 0O25, 0O27], 0O07: [0O06, 0O00, 0O17], 0O17: [0O07, 0O26, 0O20],
0O20: [0O17, 0O11, 0O30], 0O30: [0O20, 0O35, 0O33], 0O21: [0O10, 0O12, 0O31], 0O31: [0O21, 0O36, 0O34], 0O22: [0O11, 0O13, 0O32], 0O32: [0O22, 0O37, 0O35], 0O23: [0O12, 0O14, 0O33], 0O33: [0O23, 0O30, 0O36], 0O24: [0O13, 0O15, 0O34], 0O34: [0O24, 0O31, 0O37], 0O25: [0O14, 0O16, 0O35], 0O35: [0O25, 0O32, 0O30], 0O26: [0O15, 0O17, 0O36], 0O36: [0O26, 0O33, 0O31], 0O27: [0O16, 0O10, 0O37], 0O37: [0O27, 0O34, 0O32], }
r""" Returns the Horton Graph.
The Horton graph is a cubic 3-connected non-hamiltonian graph. For more information, see the :wikipedia:`Horton_graph`.
EXAMPLES::
sage: g = graphs.HortonGraph() sage: g.order() 96 sage: g.size() 144 sage: g.radius() 10 sage: g.diameter() 10 sage: g.girth() 6 sage: g.automorphism_group().cardinality() 96 sage: g.chromatic_number() 2 sage: g.is_hamiltonian() # not tested -- veeeery long False """
# Each group of the 6 groups of vertices is based on the same 3-regular # graph.
# Modifying the groups and linking them together
# Embedding
r""" Returns the Ellingham-Horton 54-graph.
For more information, see the :wikipedia:`Wikipedia page on the Ellingham-Horton graphs <Ellingham-Horton_graph>`
EXAMPLES:
This graph is 3-regular::
sage: g = graphs.EllinghamHorton54Graph() sage: g.is_regular(k=3) True
It is 3-connected and bipartite::
sage: g.vertex_connectivity() # not tested - too long 3 sage: g.is_bipartite() True
It is not Hamiltonian::
sage: g.is_hamiltonian() # not tested - too long False
... and it has a nice drawing ::
sage: g.show(figsize=[10, 10]) # not tested - too long
TESTS::
sage: g.show() # long time """
# The set of vertices on top is 0..15 # Bottom left is 16..33 # Bottom right is 34..52 # The two other vertices are 53, 54
# Top
# Bottom-left
# Bottom right
r""" Returns the Ellingham-Horton 78-graph.
For more information, see the :wikipedia:`Wikipedia page on the Ellingham-Horton graphs <http://en.wikipedia.org/wiki/Ellingham%E2%80%93Horton_graph>`
EXAMPLES:
This graph is 3-regular::
sage: g = graphs.EllinghamHorton78Graph() sage: g.is_regular(k=3) True
It is 3-connected and bipartite::
sage: g.vertex_connectivity() # not tested - too long 3 sage: g.is_bipartite() True
It is not Hamiltonian::
sage: g.is_hamiltonian() # not tested - too long False
... and it has a nice drawing ::
sage: g.show(figsize=[10,10]) # not tested - too long
TESTS::
sage: g.show(figsize=[10, 10]) # not tested - too long """ 0: [1, 5, 60], 1: [2, 12], 2: [3, 7], 3: [4, 14], 4: [5, 9], 5: [6], 6: [7, 11], 7: [15], 8: [9, 13, 22], 9: [10], 10: [11, 72], 11: [12], 12: [13], 13: [14], 14: [72], 15: [16, 20], 16: [17, 27], 17: [18, 22], 18: [19, 29], 19: [20, 24], 20: [21], 21: [22, 26], 23: [24, 28, 72], 24: [25], 25: [26, 71], 26: [27], 27: [28], 28: [29], 29: [69], 30: [31, 35, 52], 31: [32, 42], 32: [33, 37], 33: [34, 43], 34: [35, 39], 35: [36], 36: [41, 63], 37: [65, 66], 38: [39, 59, 74], 39: [40], 40: [41, 44], 41: [42], 42: [74], 43: [44, 74], 44: [45], 45: [46, 50], 46: [47, 57], 47: [48, 52], 48: [49, 75], 49: [50, 54], 50: [51], 51: [52, 56], 53: [54, 58, 73], 54: [55], 55: [56, 59], 56: [57], 57: [58], 58: [75], 59: [75], 60: [61, 64], 61: [62, 71], 62: [63, 77], 63: [67], 64: [65, 69], 65: [77], 66: [70, 73], 67: [68, 73], 68: [69, 76], 70: [71, 76], 76: [77]}, pos={})
42, 74, 43, 44], center=(2.5, 1.5)) 57, 58, 75, 59], center=(2.5, -1.5))
last=(-.8, -2))
r""" Returns the Errera graph.
For more information, see this `Wikipedia article on the Errera graph <http://en.wikipedia.org/wiki/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
The Errera graph is Hamiltonian with radius 3, diameter 4, girth 3, and chromatic number 4. ::
sage: G.is_hamiltonian() True sage: G.radius() 3 sage: G.diameter() 4 sage: G.girth() 3 sage: 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
The automorphism group of the Errera graph is isomorphic to the dihedral group of order 20. ::
sage: ag = G.automorphism_group() sage: ag.is_isomorphic(DihedralGroup(10)) True """ 0: [1,7,14,15,16], 1: [2,9,14,15], 2: [3,8,9,10,14], 3: [4,9,10,11], 4: [5,10,11,12], 5: [6,11,12,13], 6: [7,8,12,13,16], 7: [13,15,16], 8: [10,12,14,16], 9: [11,13,15], 10: [12], 11: [13], 13: [15], 14: [16]}
r""" 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:`F26A_graph`.
EXAMPLES::
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 """
""" Returns a Flower Snark.
A flower snark has 20 vertices. It is part of the class of biconnected cubic graphs with edge chromatic number = 4, known as snarks. (i.e.: the Petersen graph). All snarks are not Hamiltonian, non-planar and have Petersen graph graph minors.
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the nodes are drawn 0-14 on the outer circle, and 15-19 in an inner pentagon.
REFERENCES:
- [1] Weisstein, E. (1999). "Flower Snark - from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/FlowerSnark.html [2007, February 17]
EXAMPLES: Inspect a flower snark::
sage: F = graphs.FlowerSnark() sage: F Flower Snark: Graph on 20 vertices sage: F.graph6_string() 'ShCGHC@?GGg@?@?Gp?K??C?CA?G?_G?Cc'
Now show it::
sage: F.show() # long time """ 5:[6,10],6:[5,7,17],8:[7,9,13],9:[10,18],11:[10,12], \ 12:[13,19],13:[14],15:[19],16:[15,17],18:[17,19]}, \ pos=pos_dict, name="Flower Snark")
""" Returns the Folkman graph.
See the :wikipedia:`Wikipedia page on the Folkman Graph <Folkman_graph>`.
EXAMPLES::
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() True sage: g.is_vertex_transitive() False sage: g.is_bipartite() True """
""" Returns the Foster graph.
See the :wikipedia:`Wikipedia page on the Foster Graph <Foster_graph>`.
EXAMPLES::
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() True """
r""" Returns the Franklin graph.
For more information, see this `Wikipedia article on the Franklin graph <http://en.wikipedia.org/wiki/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
The Franklin graph is a Hamiltonian, bipartite graph with radius 3, diameter 3, and girth 4. ::
sage: G.is_hamiltonian() True sage: G.is_bipartite() True sage: G.radius() 3 sage: G.diameter() 3 sage: 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 """ 0: [1,5,6], 1: [2,7], 2: [3,8], 3: [4,9], 4: [5,10], 5: [11], 6: [7,9], 7: [10], 8: [9,11], 10: [11]} 0: [2, 0], 1: [1, 1.73205080756888], 2: [-1, 1.73205080756888], 3: [-2, 0], 4: [-1, -1.73205080756888], 5: [1, -1.73205080756888], 6: [1, 0], 7: [0.5, 0.866025403784439], 8: [-0.5, 0.866025403784439], 9: [-1, 0], 10: [-0.5, -0.866025403784439], 11: [0.5, -0.866025403784439]}
""" Returns a Frucht Graph.
A Frucht graph has 12 nodes and 18 edges. It is the smallest cubic identity graph. It is planar and it is Hamiltonian.
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the first seven nodes are on the outer circle, with the next four on an inner circle and the last in the center.
REFERENCES:
- [1] Weisstein, E. (1999). "Frucht Graph - from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/FruchtGraph.html [2007, February 17]
EXAMPLES::
sage: FRUCHT = graphs.FruchtGraph() sage: FRUCHT Frucht graph: Graph on 12 vertices sage: FRUCHT.graph6_string() 'KhCKM?_EGK?L' sage: (graphs.FruchtGraph()).show() # long time
TESTS::
sage: import networkx sage: G = graphs.FruchtGraph() sage: G.is_isomorphic(Graph(networkx.frucht_graph())) True """ 5:[6, 10], 6:[10], 7:[11], 8:[9, 11], 10:[11]}
r""" Return the Goldner-Harary graph.
For more information, see this `Wikipedia article on the Goldner-Harary graph <http://en.wikipedia.org/wiki/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
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
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() sage: ag.is_isomorphic(DihedralGroup(6)) True """ 0: [1,3,4], 1: [2,3,4,5,6,7,10], 2: [3,7], 3: [7,8,9,10], 4: [3,5,9,10], 5: [10], 6: [7,10], 7: [8,10], 8: [10], 9: [10]}
0: (-2, 0), 1: (0, 1.5), 2: (2, 0), 3: (0, -1.5), 4: (-1.5, 0), 5: (-0.5, 0.5), 6: (0.5, 0.5), 7: (1.5, 0), 8: (0.5, -0.5), 9: (-0.5, -0.5), 10: (0, 0)}
r""" Returns the Gray graph.
See the :wikipedia:`Wikipedia page on the Gray Graph <Gray_graph>`.
INPUT:
- ``embedding`` -- two embeddings are available, and can be selected by setting ``embedding`` to 1 or 2.
EXAMPLES::
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 sage: graphs.GrayGraph(embedding = 2).show(figsize=[10, 10]) # long time
TESTS::
sage: graphs.GrayGraph(embedding = 3) Traceback (most recent call last): ... ValueError: The value of embedding must be 1, 2, or 3. """
r""" Returns 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 this `Wikipedia article on Grötzsch graph <http://en.wikipedia.org/wiki/Gr%C3%B6tzsch_graph>`_.
REFERENCE:
- [1] Weisstein, Eric W. "Grotzsch Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GroetzschGraph.html
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() True sage: G.order() 11 sage: 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
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() sage: ag.is_isomorphic(DihedralGroup(5)) True """
""" Returns 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). It is nonplanar and Hamiltonian. It has diameter = 3, radius = 3, girth = 6, chromatic number = 2. It is 4-transitive but not 5-transitive.
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the nodes are positioned in a circular layout with the first node appearing at the top, and then continuing counterclockwise.
REFERENCES:
- [1] Weisstein, E. (1999). "Heawood Graph - from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/HeawoodGraph.html [2007, February 17]
EXAMPLES::
sage: H = graphs.HeawoodGraph() sage: H Heawood graph: Graph on 14 vertices sage: H.graph6_string() 'MhEGHC@AI?_PC@_G_' sage: (graphs.HeawoodGraph()).show() # long time
TESTS::
sage: import networkx sage: G = graphs.HeawoodGraph() sage: G.is_isomorphic(Graph(networkx.heawood_graph())) True """ 6:[7, 11], 7:[8], 8:[9, 13], 9:[10], 10:[11], 11:[12], 12:[13]}
r""" Returns the Herschel graph.
For more information, see this `Wikipedia article on the Herschel graph <http://en.wikipedia.org/wiki/Herschel_graph>`_.
EXAMPLES:
The Herschel graph is named after Alexander Stewart Herschel. It is a planar, bipartite graph with 11 vertices and 18 edges. ::
sage: G = graphs.HerschelGraph(); G Herschel graph: Graph on 11 vertices sage: G.is_planar() True sage: G.is_bipartite() True sage: G.order() 11 sage: G.size() 18
The Herschel graph is a perfect graph with radius 3, diameter 4, and girth 4. ::
sage: G.is_perfect() True sage: G.radius() 3 sage: G.diameter() 4 sage: G.girth() 4
Its chromatic number is 2 and its automorphism group is isomorphic to the dihedral group `D_6`. ::
sage: G.chromatic_number() 2 sage: ag = G.automorphism_group() sage: ag.is_isomorphic(DihedralGroup(6)) True """ 0: [1,3,4], 1: [2,5,6], 2: [3,7], 3: [8,9], 4: [5,9], 5: [10], 6: [7,10], 7: [8], 8: [10], 9: [10]} 0: [2, 0], 1: [0, 2], 2: [-2, 0], 3: [0, -2], 4: [1, 0], 5: [0.5, 0.866025403784439], 6: [-0.5, 0.866025403784439], 7: [-1, 0], 8: [-0.5, -0.866025403784439], 9: [0.5, -0.866025403784439], 10: [0, 0]}
r""" Returns the Higman-Sims graph.
The Higman-Sims graph is a remarkable strongly regular graph of degree 22 on 100 vertices. For example, it can be split into two sets of 50 vertices each, so that each half induces a subgraph isomorphic to the Hoffman-Singleton graph (:meth:`~HoffmanSingletonGraph`). This can be done in 352 ways (see [BROUWER-HS-2009]_).
Its most famous property is that the automorphism group has an index 2 subgroup which is one of the 26 sporadic groups. [HIGMAN1968]_
The construction used here follows [HAFNER2004]_.
INPUT:
- ``relabel`` - default: ``True``. If ``True`` the vertices will be labeled with consecutive integers. If ``False`` the labels are strings that are three digits long. "xyz" means the vertex is in group x (zero through three), pentagon or pentagram y (zero through four), and is vertex z (zero through four) of that pentagon or pentagram. See [HAFNER2004]_ for more.
OUTPUT:
The Higman-Sims graph.
EXAMPLES:
A split into the first 50 and last 50 vertices will induce two copies of the Hoffman-Singleton graph, and we illustrate another such split, which is obvious based on the construction used. ::
sage: H = graphs.HigmanSimsGraph() sage: A = H.subgraph(range(0,50)) sage: B = H.subgraph(range(50,100)) sage: K = graphs.HoffmanSingletonGraph() sage: K.is_isomorphic(A) and K.is_isomorphic(B) True sage: C = H.subgraph(range(25,75)) sage: D = H.subgraph(list(range(0,25))+list(range(75,100))) sage: K.is_isomorphic(C) and K.is_isomorphic(D) True
The automorphism group contains only one nontrivial proper normal subgroup, which is of index 2 and is simple. It is known as the Higman-Sims group. ::
sage: H = graphs.HigmanSimsGraph() sage: G = H.automorphism_group() sage: g=G.order(); g 88704000 sage: K = G.normal_subgroups()[1] sage: K.is_simple() True sage: g//K.order() 2
REFERENCES:
.. [BROUWER-HS-2009] `Higman-Sims graph <http://www.win.tue.nl/~aeb/graphs/Higman-Sims.html>`_. Andries E. Brouwer, accessed 24 October 2009. .. [HIGMAN1968] A simple group of order 44,352,000, Math.Z. 105 (1968) 110-113. D.G. Higman & C. Sims. .. [HAFNER2004] `On the graphs of Hoffman-Singleton and Higman-Sims <http://www.combinatorics.org/Volume_11/PDF/v11i1r77.pdf>`_. The Electronic Journal of Combinatorics 11 (2004), #R77, Paul R. Hafner, accessed 24 October 2009.
AUTHOR:
- Rob Beezer (2009-10-24) """
# Four groups of either five pentagons, or five pentagrams # 4 x 5 x 5 = 100 vertices # First digit is "group", second is "penta{gon|gram}", third is "vertex" for g in range(4) for p in range(5) for v in range(5)]
# Edges: Within groups 0 and 2, joined as pentagons # Edges: Within groups 1 and 3, joined as pentagrams
# Edges: group 0 to group 1
# Edges: group 1 to group 2
# Edges: group 2 to group 3
# Edges: group 3 to group 0
# Edges: group 0 to group 2
# Edges: group 1 to group 3
# Rename to integer vertex labels, creating dictionary # Or not, and create identity mapping else: vmap={} for v in vlist: vmap[v] = v # Layout vertices in a circle # In the order given in vlist # Using labels from vmap
r""" Returns the Hoffman-Singleton graph.
The Hoffman-Singleton graph is the Moore graph of degree 7, diameter 2 and girth 5. The Hoffman-Singleton theorem states that any Moore graph with girth 5 must have degree 2, 3, 7 or 57. The first three respectively are the pentagon, the Petersen graph, and the Hoffman-Singleton graph. The existence of a Moore graph with girth 5 and degree 57 is still open.
A Moore graph is a graph with diameter `d` and girth `2d + 1`. This implies that the graph is regular, and distance regular.
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. A novel algorithm written by Tom Boothby gives a random layout which is pleasing to the eye.
REFERENCES:
.. [GodsilRoyle] Godsil, C. and Royle, G. Algebraic Graph Theory. Springer, 2001.
EXAMPLES::
sage: HS = graphs.HoffmanSingletonGraph() sage: Set(HS.degree()) {7} sage: HS.girth() 5 sage: HS.diameter() 2 sage: HS.num_verts() 50
Note that you get a different layout each time you create the graph. ::
sage: HS.layout()[1] (-0.844..., 0.535...) sage: graphs.HoffmanSingletonGraph().layout()[1] (-0.904..., 0.425...)
""" 'q00':['q01'], 'q01':['q02'], 'q02':['q03'], 'q03':['q04'], 'q04':['q00'], \ 'q10':['q11'], 'q11':['q12'], 'q12':['q13'], 'q13':['q14'], 'q14':['q10'], \ 'q20':['q21'], 'q21':['q22'], 'q22':['q23'], 'q23':['q24'], 'q24':['q20'], \ 'q30':['q31'], 'q31':['q32'], 'q32':['q33'], 'q33':['q34'], 'q34':['q30'], \ 'q40':['q41'], 'q41':['q42'], 'q42':['q43'], 'q43':['q44'], 'q44':['q40'], \ 'p00':['p02'], 'p02':['p04'], 'p04':['p01'], 'p01':['p03'], 'p03':['p00'], \ 'p10':['p12'], 'p12':['p14'], 'p14':['p11'], 'p11':['p13'], 'p13':['p10'], \ 'p20':['p22'], 'p22':['p24'], 'p24':['p21'], 'p21':['p23'], 'p23':['p20'], \ 'p30':['p32'], 'p32':['p34'], 'p34':['p31'], 'p31':['p33'], 'p33':['p30'], \ 'p40':['p42'], 'p42':['p44'], 'p44':['p41'], 'p41':['p43'], 'p43':['p40']})
r""" Returns the Hoffman Graph.
See the :wikipedia:`Wikipedia page on the Hoffman graph <Hoffman_graph>`.
EXAMPLES::
sage: g = graphs.HoffmanGraph() sage: g.is_bipartite() True sage: g.is_hamiltonian() # long time True sage: g.radius() 3 sage: g.diameter() 4 sage: g.automorphism_group().cardinality() 48 """ 0: [1, 7, 8, 13], 1: [2, 9, 14], 2: [3, 8, 10], 3: [4, 9, 15], 4: [5, 10, 11], 5: [6, 12, 14], 6: [7, 11, 13], 7: [12, 15], 8: [12, 14], 9: [11, 13], 10: [12, 15], 11: [14], 13: [15]})
r""" Returns the Holt graph (also called the Doyle graph).
See the :wikipedia:`Wikipedia page on the Holt graph <Holt_graph>`.
EXAMPLES::
sage: g = graphs.HoltGraph();g Holt graph: Graph on 27 vertices sage: g.is_regular() True sage: g.is_vertex_transitive() True sage: g.chromatic_number() 3 sage: g.is_hamiltonian() # long time True sage: g.radius() 3 sage: g.diameter() 3 sage: g.girth() 5 sage: g.automorphism_group().cardinality() 54 """
first=(cos(2*j*pi/6),sin(2*j*pi/6)), last=(cos(2*(j+1)*pi/6),sin(2*(j+1)*pi/6)))
""" Returns a Krackhardt kite graph with 10 nodes.
The Krackhardt kite graph was originally developed by David Krackhardt for the purpose of studying social networks. It is used to show the distinction between: degree centrality, betweeness centrality, and closeness centrality. For more information read the plotting section below in conjunction with the example.
REFERENCES:
- [1] Kreps, V. (2002). "Social Network Analysis". [Online] Available: http://www.orgnet.com/sna.html
PLOTTING: Upon construction, the position dictionary is filled to override the spring-layout algorithm. By convention, the graph is drawn left to right, in top to bottom row sequence of [2, 3, 2, 1, 1, 1] nodes on each row. This places the fourth node (3) in the center of the kite, with the highest degree. But the fourth node only connects nodes that are otherwise connected, or those in its clique (i.e.: Degree Centrality). The eighth (7) node is where the kite meets the tail. It has degree = 3, less than the average, but is the only connection between the kite and tail (i.e.: Betweenness Centrality). The sixth and seventh nodes (5 and 6) are drawn in the third row and have degree = 5. These nodes have the shortest path to all other nodes in the graph (i.e.: Closeness Centrality). Please execute the example for visualization.
EXAMPLES: Construct and show a Krackhardt kite graph
::
sage: g = graphs.KrackhardtKiteGraph() sage: g.show() # long time
TESTS::
sage: import networkx sage: G = graphs.KrackhardtKiteGraph() sage: G.is_isomorphic(Graph(networkx.krackhardt_kite_graph())) True """ 4:[6], 5:[6, 7], 6:[7], 7:[8], 8:[9]}
r""" Return the Klein 3-regular graph.
The cubic Klein graph has 56 vertices and can be embedded on a surface of genus 3. It is the dual of :meth:`~sage.graphs.graph_generators.GraphGenerators.Klein7RegularGraph`. For more information, see the :wikipedia:`Klein_graphs`.
EXAMPLES::
sage: g = graphs.Klein3RegularGraph(); g Klein 3-regular Graph: Graph on 56 vertices sage: g.order(), g.size() (56, 84) sage: g.girth() 7 sage: g.automorphism_group().cardinality() 336 sage: g.chromatic_number() 3 """ 'EcarHwIVHAKh|\\tLVUxT]`ZDTJ{Af[o_AuKs{r_?ef', loops=False, multiedges=False) 45, 18, 20, 47, 42, 23, 17, 16, 10, 41, 11, 49, 25, 51, 26, 54, 9, 22, 15, 21, 12, 24, 7, 52, 31, 32, 36, 46, 35, 29, 50, 27, 19, 28, 5, 33, 13, 53, 39, 38, 44])
r""" Return the Klein 7-regular graph.
The 7-valent Klein graph has 24 vertices and can be embedded on a surface of genus 3. It is the dual of :meth:`~sage.graphs.graph_generators.GraphGenerators.Klein3RegularGraph`. For more information, see the :wikipedia:`Klein_graphs`.
EXAMPLES::
sage: g = graphs.Klein7RegularGraph(); g Klein 7-regular Graph: Graph on 24 vertices sage: g.order(), g.size() (24, 84) sage: g.girth() 3 sage: g.automorphism_group().cardinality() 336 sage: g.chromatic_number() 4 """ 'Q`HOQRcGLRS`BKMSTdJKLPTU',loops=False,multiedges=False) 10, 8, 13, 11, 5, 23, 22, 14, 12, 18, 6])
r""" Return the local McLaughlin graph.
The local McLaughlin graph is a strongly regular graph with parameters `(162,56,10,24)`. It can be obtained from :meth:`~sage.graphs.graph_generators.GraphGenerators.McLaughlinGraph` by considering the stabilizer of a point: one of its orbits has cardinality 162.
EXAMPLES::
sage: g = graphs.LocalMcLaughlinGraph(); g # long time # optional - gap_packages Local McLaughlin Graph: Graph on 162 vertices sage: g.is_strongly_regular(parameters=True) # long time # optional - gap_packages (162, 56, 10, 24) """ g = McLaughlinGraph() orbits = g.automorphism_group().stabilizer(1).orbits() orbit = [x for x in orbits if len(x) == 162][0] g = g.subgraph(vertices=orbit) g.relabel() g.name("Local McLaughlin Graph") return g
r""" Returns the Ljubljana Graph.
The Ljubljana graph is a bipartite 3-regular graph on 112 vertices and 168 edges. It is not vertex-transitive as it has two orbits which are also independent sets of size 56. See the :wikipedia:`Wikipedia page on the Ljubljana Graph <Ljubljana_graph>`.
The default embedding is obtained from the Heawood graph.
INPUT:
- ``embedding`` -- two embeddings are available, and can be selected by setting ``embedding`` to 1 or 2.
EXAMPLES::
sage: g = graphs.LjubljanaGraph() sage: g.order() 112 sage: g.size() 168 sage: g.girth() 10 sage: g.diameter() 8 sage: g.show(figsize=[10, 10]) # long time sage: graphs.LjubljanaGraph(embedding=2).show(figsize=[10, 10]) # long time
TESTS::
sage: graphs.LjubljanaGraph(embedding=3) Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2. """
-49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39]
# Correspondence between the vertices of the Heawood Graph and # 8-sets of the Ljubljana Graph.
0: [1, 21, 39, 57, 51, 77, 95, 107], 1: [2, 22, 38, 58, 50, 78, 94, 106], 2: [3, 23, 37, 59, 49, 79, 93, 105], 3: [4, 24, 36, 60, 48, 80, 92, 104], 4: [5, 25, 35, 61, 15, 81, 91, 71], 9: [6, 26, 44, 62, 16, 82, 100, 72], 10: [7, 27, 45, 63, 17, 83, 101, 73], 11: [8, 28, 46, 64, 18, 84, 102, 74], 12: [9, 29, 47, 65, 19, 85, 103, 75], 13: [10, 30, 0, 66, 20, 86, 56, 76], 8: [11, 31, 111, 67, 99, 87, 55, 43], 7: [12, 32, 110, 68, 98, 88, 54, 42], 6: [13, 33, 109, 69, 97, 89, 53, 41], 5: [14, 34, 108, 70, 96, 90, 52, 40] }
# The vertices of each 8-set are plotted on a circle, and the # circles are slowly shifted to obtain a symmetric drawing.
shift=8.*i/14)
return g
else:
r""" Returns the Livingstone Graph.
The Livingstone graph is a distance-transitive graph on 266 vertices whose automorphism group is the :class:`J1 group <sage.groups.perm_gps.permgroup_named.JankoGroup>`. For more information, see the :wikipedia:`Livingstone_graph`.
EXAMPLES::
sage: g = graphs.LivingstoneGraph() # optional - gap_packages internet sage: g.order() # optional - gap_packages internet 266 sage: g.size() # optional - gap_packages internet 1463 sage: g.girth() # optional - gap_packages internet 5 sage: g.is_vertex_transitive() # optional - gap_packages internet True sage: g.is_distance_regular() # optional - gap_packages internet True """ from sage.groups.perm_gps.permgroup_named import JankoGroup from sage.graphs.graph import Graph G = JankoGroup(1) edges = map(tuple,G.orbit((1,24),action="OnSets")) return Graph(edges,name="Livingstone Graph")
r""" Returns the M22 graph.
The `M_{22}` graph is the unique strongly regular graph with parameters `v = 77, k = 16, \lambda = 0, \mu = 4`.
For more information on the `M_{22}` graph, see `<http://www.win.tue.nl/~aeb/graphs/M22.html>`_.
EXAMPLES::
sage: g = graphs.M22Graph() sage: g.order() 77 sage: g.size() 616 sage: g.is_strongly_regular(parameters = True) (77, 16, 0, 4) """ 36, 23, 27, 25, 40, 26, 16, 71, 61, 63, 50, 68, 39, 52, 48, 44, 69, 28, 9, 64, 60, 17, 38, 49, 45, 65, 14, 70, 72, 21, 43, 56, 33, 73, 58, 55, 41, 29, 66, 54, 76, 46, 67, 11, 51, 47, 62, 53, 15, 8, 18, 13, 59, 37, 30, 57, 75, 74, 42]
r""" Returns the Markström Graph.
The Markström Graph is a cubic planar graph with no cycles of length 4 nor 8, but containing cycles of length 16. For more information, see the `Wolfram page about the Markström Graph <http://mathworld.wolfram.com/MarkstroemGraph.html>`_.
EXAMPLES::
sage: g = graphs.MarkstroemGraph() sage: g.order() 24 sage: g.size() 36 sage: g.is_planar() True sage: g.is_regular(3) True sage: g.subgraph_search(graphs.CycleGraph(4)) is None True sage: g.subgraph_search(graphs.CycleGraph(8)) is None True sage: g.subgraph_search(graphs.CycleGraph(16)) Subgraph of (Markstroem Graph): Graph on 16 vertices """
r""" Returns the McGee Graph.
See the :wikipedia:`Wikipedia page on the McGee Graph <McGee_graph>`.
INPUT:
- ``embedding`` -- two embeddings are available, and can be selected by setting ``embedding`` to 1 or 2.
EXAMPLES::
sage: g = graphs.McGeeGraph() sage: g.order() 24 sage: g.size() 36 sage: g.girth() 7 sage: g.diameter() 4 sage: g.show() sage: graphs.McGeeGraph(embedding=1).show()
TESTS::
sage: graphs.McGeeGraph(embedding=3) Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2. """
-49, 33, 39, -35, -21, 17, -33, 49, 41, 31, -15, -29, 41, 31, -15, -25, 21, 31, -51, -25, 23, 9, -17, 51, 35, -29, 21, -51, -39, 33, -9, -51, 51, -47, -33, 19, 51, -21, 29, 21, -31, -39]
[5, 4, 11, 10, 17, 16, 23, 22], [3, 12, 9, 18, 15, 0, 21, 6]]
else:
r""" Returns the McLaughlin Graph.
The McLaughlin Graph is the unique strongly regular graph of parameters `(275, 112, 30, 56)`.
For more information on the McLaughlin Graph, see its web page on `Andries Brouwer's website <http://www.win.tue.nl/~aeb/graphs/McL.html>`_ which gives the definition that this method implements.
.. NOTE::
To create this graph you must have the gap_packages spkg installed.
EXAMPLES::
sage: g = graphs.McLaughlinGraph() # optional gap_packages sage: g.is_strongly_regular(parameters=True) # optional gap_packages (275, 112, 30, 56) sage: set(g.spectrum()) == {112, 2, -28} # optional gap_packages True """ from sage.combinat.designs.block_design import WittDesign from itertools import combinations from sage.sets.set import Set
blocks = [Set(_) for _ in WittDesign(23).blocks()]
B = [b for b in blocks if 0 in b] C = [b for b in blocks if 0 not in b] g = Graph() for b in B: for x in range(1,23): if not x in b: g.add_edge(b, x)
for b in C: for x in b: g.add_edge(b, x)
for b, bb in combinations(B, 2): if len(b & bb) == 1: g.add_edge(b, bb)
for c, cc in combinations(C, 2): if len(c & cc) == 1: g.add_edge(c, cc)
for b in B: for c in C: if len(b & c) == 3: g.add_edge(b, c)
# Here we relabel the elements of g in an architecture-independent way g.relabel({v: i for i, v in enumerate(list(range(1, 23)) + sorted(blocks, key=sorted))}) g.name("McLaughlin") return g
""" Returns a Möbius-Kantor Graph.
A Möbius-Kantor graph is a cubic symmetric graph. (See also the Heawood graph). It has 16 nodes and 24 edges. It is nonplanar and Hamiltonian. It has diameter = 4, girth = 6, and chromatic number = 2. It is identical to the Generalized Petersen graph, P[8,3].
PLOTTING: See the plotting section for the generalized Petersen graphs.
REFERENCES:
- [1] Weisstein, E. (1999). "Möbius-Kantor Graph - from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/Moebius-KantorGraph.html [2007, February 17]
EXAMPLES::
sage: MK = graphs.MoebiusKantorGraph() sage: MK Moebius-Kantor Graph: Graph on 16 vertices sage: MK.graph6_string() 'OhCGKE?O@?ACAC@I?Q_AS' sage: (graphs.MoebiusKantorGraph()).show() # long time """
r""" Returns the Moser spindle.
For more information, see this `MathWorld article on the Moser spindle <http://mathworld.wolfram.com/MoserSpindle.html>`_.
EXAMPLES:
The Moser spindle is a planar graph having 7 vertices and 11 edges. ::
sage: G = graphs.MoserSpindle(); G Moser spindle: Graph on 7 vertices sage: G.is_planar() True sage: G.order() 7 sage: G.size() 11
It is a Hamiltonian graph with radius 2, diameter 2, and girth 3. ::
sage: G.is_hamiltonian() True sage: G.radius() 2 sage: G.diameter() 2 sage: G.girth() 3
The Moser spindle has chromatic number 4 and its automorphism group is isomorphic to the dihedral group `D_4`. ::
sage: G.chromatic_number() 4 sage: ag = G.automorphism_group() sage: ag.is_isomorphic(DihedralGroup(4)) True """ 0: [1,4,5,6], 1: [2,5], 2: [3,5], 3: [4,6], 4: [6]} 0: [0, 2], 1: [-1.90211303259031, 0.618033988749895], 2: [-1.17557050458495, -1.61803398874989], 3: [1.17557050458495, -1.61803398874989], 4: [1.90211303259031, 0.618033988749895], 5: [1, 0], 6: [-1, 0]}
""" Returns the Nauru Graph.
See the :wikipedia:`Wikipedia page on the Nauru Graph <Nauru_graph>`.
INPUT:
- ``embedding`` -- two embeddings are available, and can be selected by setting ``embedding`` to 1 or 2.
EXAMPLES::
sage: g = graphs.NauruGraph() sage: g.order() 24 sage: g.size() 36 sage: g.girth() 6 sage: g.diameter() 4 sage: g.show() sage: graphs.NauruGraph(embedding=1).show()
TESTS::
sage: graphs.NauruGraph(embedding=3) Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2. sage: graphs.NauruGraph(embedding=1).is_isomorphic(g) True """
else:
""" Returns the Pappus graph, a graph on 18 vertices.
The Pappus graph is cubic, symmetric, and distance-regular.
EXAMPLES::
sage: G = graphs.PappusGraph() sage: G.show() # long time sage: L = graphs.LCFGraph(18, [5,7,-7,7,-7,-5], 3) sage: L.show() # long time sage: G.is_isomorphic(L) True """ float(sin(pi/2 + ((2*pi)/6)*i))] (2/3.0)*float(sin(pi/2 + ((2*pi)/6)*i))] (1/3.0)*float(sin(pi/2 + ((2*pi)/6)*i))] 5:[11],6:[13,17],7:[12,14],8:[13,15],9:[14,16],\ 10:[15,17],11:[12,16],12:[15],13:[16],14:[17]},\ pos=pos_dict, name="Pappus Graph")
r""" Returns the Poussin Graph.
For more information on the Poussin Graph, see its corresponding `Wolfram page <http://mathworld.wolfram.com/PoussinGraph.html>`_.
EXAMPLES::
sage: g = graphs.PoussinGraph() sage: g.order() 15 sage: g.is_planar() True """
""" Returns the Petersen Graph.
The Petersen Graph is a named graph that consists of 10 vertices and 15 edges, usually drawn as a five-point star embedded in a pentagon.
The Petersen Graph is a common counterexample. For example, it is not Hamiltonian.
PLOTTING: See the plotting section for the generalized Petersen graphs.
EXAMPLES: We compare below the Petersen graph with the default spring-layout versus a planned position dictionary of [x,y] tuples::
sage: petersen_spring = Graph({0:[1,4,5], 1:[0,2,6], 2:[1,3,7], 3:[2,4,8], 4:[0,3,9], 5:[0,7,8], 6:[1,8,9], 7:[2,5,9], 8:[3,5,6], 9:[4,6,7]}) sage: petersen_spring.show() # long time sage: petersen_database = graphs.PetersenGraph() sage: petersen_database.show() # long time """
r""" Return the Perkel Graph.
The Perkel Graph is a 6-regular graph with `57` vertices and `171` edges. It is the unique distance-regular graph with intersection array `(6,5,2;1,1,3)`. For more information, see the :wikipedia:`Perkel_graph` or http://www.win.tue.nl/~aeb/graphs/Perkel.html.
EXAMPLES::
sage: g = graphs.PerkelGraph(); g Perkel Graph: Graph on 57 vertices sage: g.is_distance_regular(parameters=True) ([6, 5, 2, None], [None, 1, 1, 3]) """ 48, 40, 17, 20, 27, 43, 16, 7, 14, 6, 4, 15, 41, 24, 37, 28, 9, 55, 38, 19, 34, 39, 36, 54, 52, 44, 23, 12, 22, 32, 10, 13, 26, 1, 21, 42, 56, 49, 31, 47, 11, 25])
""" Returns the Robertson graph.
See the :wikipedia:`Wikipedia page on the Robertson Graph <Robertson_graph>`.
EXAMPLES::
sage: g = graphs.RobertsonGraph() sage: g.order() 19 sage: g.size() 38 sage: g.diameter() 3 sage: g.girth() 5 sage: g.charpoly().factor() (x - 4) * (x - 1)^2 * (x^2 + x - 5) * (x^2 + x - 1) * (x^2 - 3)^2 * (x^2 + x - 4)^2 * (x^2 + x - 3)^2 sage: g.chromatic_number() 3 sage: g.is_hamiltonian() True sage: g.is_vertex_transitive() False """
r""" Returns the Schläfli graph.
The Schläfli graph is the only strongly regular graphs of parameters `(27,16,10,8)` (see [GodsilRoyle]_).
For more information, see the :wikipedia:`Wikipedia article on the Schläfli graph <Schläfli_graph>`.
.. SEEALSO::
:meth:`Graph.is_strongly_regular` -- tests whether a graph is strongly regular and/or returns its parameters.
.. TODO::
Find a beautiful layout for this beautiful graph.
EXAMPLES:
Checking that the method actually returns the Schläfli graph::
sage: S = graphs.SchlaefliGraph() sage: S.is_strongly_regular(parameters = True) (27, 16, 10, 8)
The graph is vertex-transitive::
sage: S.is_vertex_transitive() True
The neighborhood of each vertex is isomorphic to the complement of the Clebsch graph::
sage: neighborhood = S.subgraph(vertices = S.neighbors(0)) sage: graphs.ClebschGraph().complement().is_isomorphic(neighborhood) True """
""" Returns the Shrikhande graph.
For more information, see the `MathWorld article on the Shrikhande graph <http://mathworld.wolfram.com/ShrikhandeGraph.html>`_ or the :wikipedia:`Wikipedia article on the Shrikhande graph <Shrikhande_graph>`.
.. SEEALSO::
:meth:`Graph.is_strongly_regular` -- tests whether a graph is strongly regular and/or returns its parameters.
EXAMPLES:
The Shrikhande graph was defined by S. S. Shrikhande in 1959. It has `16` vertices and `48` edges, and is strongly regular of degree `6` with parameters `(2,2)`::
sage: G = graphs.ShrikhandeGraph(); G Shrikhande graph: Graph on 16 vertices sage: G.order() 16 sage: G.size() 48 sage: G.is_regular(6) True sage: set([ len([x for x in G.neighbors(i) if x in G.neighbors(j)]) ....: for i in range(G.order()) ....: for j in range(i) ]) {2}
It is non-planar, and both Hamiltonian and Eulerian::
sage: G.is_planar() False sage: G.is_hamiltonian() True sage: G.is_eulerian() True
It has radius `2`, diameter `2`, and girth `3`::
sage: G.radius() 2 sage: G.diameter() 2 sage: G.girth() 3
Its chromatic number is `4` and its automorphism group is of order `192`::
sage: G.chromatic_number() 4 sage: G.automorphism_group().cardinality() 192
It is an integral graph since it has only integral eigenvalues::
sage: G.characteristic_polynomial().factor() (x - 6) * (x - 2)^6 * (x + 2)^9
It is a toroidal graph, and its embedding on a torus is dual to an embedding of the Dyck graph (:meth:`DyckGraph <GraphGenerators.DyckGraph>`). """ float(sin((2*i) * pi/8))] 0.5 * pos_dict[i][1]] 0O00: [0O06, 0O07, 0O01, 0O02, 0O11, 0O17], 0O01: [0O07, 0O00, 0O02, 0O03, 0O12, 0O10], 0O02: [0O00, 0O01, 0O03, 0O04, 0O13, 0O11], 0O03: [0O01, 0O02, 0O04, 0O05, 0O14, 0O12], 0O04: [0O02, 0O03, 0O05, 0O06, 0O15, 0O13], 0O05: [0O03, 0O04, 0O06, 0O07, 0O16, 0O14], 0O06: [0O04, 0O05, 0O07, 0O00, 0O17, 0O15], 0O07: [0O05, 0O06, 0O00, 0O01, 0O10, 0O16],
0O10: [0O12, 0O13, 0O15, 0O16, 0O07, 0O01], 0O11: [0O13, 0O14, 0O16, 0O17, 0O00, 0O02], 0O12: [0O14, 0O15, 0O17, 0O10, 0O01, 0O03], 0O13: [0O15, 0O16, 0O10, 0O11, 0O02, 0O04], 0O14: [0O16, 0O17, 0O11, 0O12, 0O03, 0O05], 0O15: [0O17, 0O10, 0O12, 0O13, 0O04, 0O06], 0O16: [0O10, 0O11, 0O13, 0O14, 0O05, 0O07], 0O17: [0O11, 0O12, 0O14, 0O15, 0O06, 0O00] }
""" Returns the Sylvester Graph.
This graph is obtained from the Hoffman Singleton graph by considering the graph induced by the vertices at distance two from the vertices of an (any) edge.
For more information on the Sylvester graph, see `<http://www.win.tue.nl/~aeb/graphs/Sylvester.html>`_.
.. SEEALSO::
* :meth:`~sage.graphs.graph_generators.GraphGenerators.HoffmanSingletonGraph`.
EXAMPLES::
sage: g = graphs.SylvesterGraph(); g Sylvester Graph: Graph on 36 vertices sage: g.order() 36 sage: g.size() 90 sage: g.is_regular(k=5) True """ 10, 28, 29, 7, 24, 23, 26, 19, 12, 13, 21, 11, 31, 3, 27, 25, 17, 8, 34]
""" Returns the Sims-Gewirtz Graph.
This graph is obtained from the Higman Sims graph by considering the graph induced by the vertices at distance two from the vertices of an (any) edge. It is the only strongly regular graph with parameters `v = 56, k = 10, \lambda = 0, \mu = 2`
For more information on the Sylvester graph, see `<http://www.win.tue.nl/~aeb/graphs/Sims-Gewirtz.html>`_ or its :wikipedia:`Wikipedia page <Gewirtz graph>`.
.. SEEALSO::
* :meth:`~sage.graphs.graph_generators.GraphGenerators.HigmanSimsGraph`.
EXAMPLES::
sage: g = graphs.SimsGewirtzGraph(); g Sims-Gewirtz Graph: Graph on 56 vertices sage: g.order() 56 sage: g.size() 280 sage: g.is_strongly_regular(parameters = True) (56, 10, 0, 2)
""" 53, 52, 38, 43, 44, 18, 20, 32, 19, 42, 54, 36, 51, 30, 33, 35, 37, 28, 34, 12, 29, 23, 55, 25, 40, 24, 9, 14, 48, 39, 45, 16, 13, 21, 31, 50, 10, 46]
r""" Returns the Sousselier Graph.
The Sousselier graph is a hypohamiltonian graph on 16 vertices and 27 edges. For more information, see the corresponding `Wikipedia page (in French) <http://fr.wikipedia.org/wiki/Graphe_de_Sousselier>`_.
EXAMPLES::
sage: g = graphs.SousselierGraph() sage: g.order() 16 sage: g.size() 27 sage: g.radius() 2 sage: g.diameter() 3 sage: g.automorphism_group().cardinality() 2 sage: g.is_hamiltonian() False sage: g.delete_vertex(g.random_vertex()) sage: g.is_hamiltonian() True """
r""" Returns the Szekeres Snark Graph.
The Szekeres graph is a snark with 50 vertices and 75 edges. For more information on this graph, see the :wikipedia:`Szekeres_snark`.
EXAMPLES::
sage: g = graphs.SzekeresSnarkGraph() sage: g.order() 50 sage: g.size() 75 sage: g.chromatic_number() 3 """
radius=.3, center=(cos(2*(i+.25)*pi/5),sin(2*(i+.25)*pi/5)), shift=5.45+1.8*i)
""" Returns the Thomsen Graph.
The Thomsen Graph is actually a complete bipartite graph with `(n1, n2) = (3, 3)`. It is also called the Utility graph.
PLOTTING: See CompleteBipartiteGraph.
EXAMPLES::
sage: T = graphs.ThomsenGraph() sage: T Thomsen graph: Graph on 6 vertices sage: T.graph6_string() 'EFz_' sage: (graphs.ThomsenGraph()).show() # long time """
r""" Returns the Tietze Graph.
For more information on the Tietze Graph, see the :wikipedia:`Tietze's_graph`.
EXAMPLES::
sage: g = graphs.TietzeGraph() sage: g.order() 12 sage: g.size() 18 sage: g.diameter() 3 sage: g.girth() 3 sage: g.automorphism_group().cardinality() 12 sage: g.automorphism_group().is_isomorphic(groups.permutation.Dihedral(6)) True """
r""" Return the truncated icosidodecahedron.
The truncated icosidodecahedron is an Archimedean solid with 30 square faces, 20 regular hexagonal faces, 12 regular decagonal faces, 120 vertices and 180 edges. For more information, see the :wikipedia:`Truncated_icosidodecahedron`.
EXAMPLES::
sage: g = graphs.TruncatedIcosidodecahedralGraph(); g Truncated Icosidodecahedron: Graph on 120 vertices sage: g.order(), g.size() (120, 180) """
r""" Return the truncated tetrahedron.
The truncated tetrahedron is an Archimedean solid with 12 vertices and 18 edges. For more information, see the :wikipedia:`Truncated_tetrahedron`.
EXAMPLES::
sage: g = graphs.TruncatedTetrahedralGraph(); g Truncated Tetrahedron: Graph on 12 vertices sage: g.order(), g.size() (12, 18) sage: g.is_isomorphic(polytopes.simplex(3).truncation().graph()) True """
r""" Returns Tutte's 12-Cage.
See the :wikipedia:`Wikipedia page on the Tutte 12-Cage <Tutte_12-cage>`.
EXAMPLES::
sage: g = graphs.Tutte12Cage() sage: g.order() 126 sage: g.size() 189 sage: g.girth() 12 sage: g.diameter() 6 sage: g.show() """ -21, -57, 59, -17]
r""" Returns the Tutte-Coxeter graph.
See the :wikipedia:`Wikipedia page on the Tutte-Coxeter Graph <Tutte-Coxeter_graph>`.
INPUT:
- ``embedding`` -- two embeddings are available, and can be selected by setting ``embedding`` to 1 or 2.
EXAMPLES::
sage: g = graphs.TutteCoxeterGraph() sage: g.order() 30 sage: g.size() 45 sage: g.girth() 8 sage: g.diameter() 4 sage: g.show() sage: graphs.TutteCoxeterGraph(embedding=1).show()
TESTS::
sage: graphs.TutteCoxeterGraph(embedding=3) Traceback (most recent call last): ... ValueError: The value of embedding must be 1 or 2. """
0: [1, 3, 5, 7, 29], 1: [2, 4, 6, 28, 0], 2: [8, 18, 26, 22, 12], 3: [9, 13, 23, 27, 17], 4: [11, 15, 21, 25, 19], 5: [10, 14, 24, 20, 16] }
else:
r""" Returns the Tutte Graph.
The Tutte graph is a 3-regular, 3-connected, and planar non-hamiltonian graph. For more information on the Tutte Graph, see the :wikipedia:`Tutte_graph`.
EXAMPLES::
sage: g = graphs.TutteGraph() sage: g.order() 46 sage: g.size() 69 sage: g.is_planar() True sage: g.vertex_connectivity() # long time 3 sage: g.girth() 4 sage: g.automorphism_group().cardinality() 3 sage: g.is_hamiltonian() False """
shift=3.7*(i-2)+.75, radius=.4, center=(.6*cos(2*(i+.25)*pi/3),.6*sin(2*(i+.25)*pi/3))) shift=1.7*(i-2)+1, radius=.2, center=(.6*cos(2*(i+.25)*pi/3),.6*sin(2*(i+.25)*pi/3)))
""" Returns the Wagner Graph.
See the :wikipedia:`Wikipedia page on the Wagner Graph <Wagner_graph>`.
EXAMPLES::
sage: g = graphs.WagnerGraph() sage: g.order() 8 sage: g.size() 12 sage: g.girth() 4 sage: g.diameter() 2 sage: g.show() """
r""" Returns the Watkins Snark Graph.
The Watkins Graph is a snark with 50 vertices and 75 edges. For more information, see the :wikipedia:`Watkins_snark`.
EXAMPLES::
sage: g = graphs.WatkinsSnarkGraph() sage: g.order() 50 sage: g.size() 75 sage: g.chromatic_number() 3 """
[(i,j) for j in range(4)]+[0]*2+[(i,4)]+[0]*2+[(i,j) for j in range(5,9)], radius=.3, center=(cos(2*(i+.25)*pi/5),sin(2*(i+.25)*pi/5)), shift=2.7*i+7.55)
r""" Returns the Wiener-Araya Graph.
The Wiener-Araya Graph is a planar hypohamiltonian graph on 42 vertices and 67 edges. For more information, see the `Wolfram Page on the Wiener-Araya Graph <http://mathworld.wolfram.com/Wiener-ArayaGraph.html>`_ or its `(french) Wikipedia page <http://fr.wikipedia.org/wiki/Graphe_de_Wiener-Araya>`_.
EXAMPLES::
sage: g = graphs.WienerArayaGraph() sage: g.order() 42 sage: g.size() 67 sage: g.girth() 4 sage: g.is_planar() True sage: g.is_hamiltonian() # not tested -- around 30s long False sage: g.delete_vertex(g.random_vertex()) sage: g.is_hamiltonian() True """
sum([[(1,3*i),(1,3*i+1)]+[0]*3+[(1,3*i+2)]+[0]*3 for i in range(4)],[]), shift=4, radius=.65)
r""" Pseudo-cyclic association scheme for action of `O(3,2^k)` on elliptic lines
The group `O(3,2^k)` acts naturally on the `q(q-1)/2` lines of `PG(2,2^k)` skew to the conic preserved by it, see Sect. 12.7.B of [BCN89]_ and Sect. 6.D in [BvL84]_. Compute the orbitals of this action and return them.
This is a helper for :func:`sage.graphs.generators.smallgraphs.MathonStronglyRegularGraph`.
INPUT:
- ``k`` (integer) -- the exponent of 2 to get the field size
TESTS::
sage: from sage.graphs.generators.smallgraphs import _EllipticLinesProjectivePlaneScheme sage: _EllipticLinesProjectivePlaneScheme(2) [ [1 0 0 0 0 0] [0 1 1 1 1 0] [0 0 0 0 0 1] [0 1 0 0 0 0] [1 0 1 1 0 1] [0 0 0 0 1 0] [0 0 1 0 0 0] [1 1 0 0 1 1] [0 0 0 1 0 0] [0 0 0 1 0 0] [1 1 0 0 1 1] [0 0 1 0 0 0] [0 0 0 0 1 0] [1 0 1 1 0 1] [0 1 0 0 0 0] [0 0 0 0 0 1], [0 1 1 1 1 0], [1 0 0 0 0 0] ] """ libgap.OnTuples) for x in mats]
r""" Return one of Mathon's graphs on 784 vertices.
INPUT:
- ``t`` (integer) -- the number of the graph, from 0 to 2.
EXAMPLES::
sage: from sage.graphs.generators.smallgraphs import MathonStronglyRegularGraph sage: G = MathonStronglyRegularGraph(0) # long time sage: G.is_strongly_regular(parameters=True) # long time (784, 243, 82, 72)
TESTS::
sage: G = graphs.MathonStronglyRegularGraph(1) # long time sage: G.is_strongly_regular(parameters=True) # long time (784, 270, 98, 90) sage: G = graphs.MathonStronglyRegularGraph(2) # long time sage: G.is_strongly_regular(parameters=True) # long time (784, 297, 116, 110)
""" from sage.graphs.generators.families import MathonPseudocyclicMergingGraph ES = _EllipticLinesProjectivePlaneScheme(3) return MathonPseudocyclicMergingGraph(ES, t)
r""" Returns a (936, 375, 150, 150)-srg or a (1800, 1029, 588, 588)-srg.
This functions returns a strongly regular graph for the two sets of parameters shown to be realizable in [JK02]_. The paper also uses a construction from [GM87]_.
INPUT:
- ``v`` (integer) -- one of 936 or 1800.
EXAMPLES::
sage: g = graphs.JankoKharaghaniGraph(936) # long time sage: g.is_strongly_regular(parameters=True) # long time (936, 375, 150, 150)
sage: g = graphs.JankoKharaghaniGraph(1800) # not tested (30s) sage: g.is_strongly_regular(parameters=True) # not tested (30s) (1800, 1029, 588, 588)
REFERENCES:
.. [JK02] Janko, Kharaghani, A block negacyclic Bush-type Hadamard matrix and two strongly regular graphs. J. Combin. Theory Ser. A 98 (2002), no. 1, 118--126. :doi:`10.1006/jcta.2001.3231`
.. [GM87] Gibbons, Mathon, Construction methods for Bhaskar Rao and related designs, J. Austral. Math. Soc. Ser. A 42 (1987), no. 1, 5--30. http://journals.cambridge.org/article_S1446788700033929
""" from sage.rings.finite_rings.finite_field_constructor import FiniteField as GF from sage.matrix.constructor import matrix
# The notations of [JK02] are rather tricky, and so this code attempts to # stick as much as possible to the paper's variable names.
assert v in [1800,936]
J = matrix.ones I = matrix.identity
# Definition of the 36x36 matrix H ([JK02], section 2) A = J(6) B = ("111---","1---11","1--1-1","--111-","-1-11-","-11--1") C = ("-1-1-1","1---11","--11-1","1-1-1-","-1-11-","111---") D = ("--1-11","-11-1-","11-1--","--11-1","11---1","1--11-") E = ("-1--11","1-1--1","-11-1-","---111","1-11--","11-1--") F = ("-1-1-1","11--1-","--111-","1-11--","-11--1","1---11") B,C,D,E,F = [matrix([map({'1':1,'-':-1}.get,r) for r in m]) for m in [B,C,D,E,F]]
H = [A,B,C,D,E,F] H = [[-x for x in H[6-i:]] + H[:6-i] for i in range(6)] H = matrix.block(H)
# Definition of the BGW matrix W with the cyclotomic method # ([JK02] Lemma 1, and [GM87] Construction 1) m = 12 t = (2 if v == 936 else 4) k = m q = m*t+1 K = GF(q,'alpha') a = K.primitive_element() Ci= [[K(0)]] + [set(a**(k*j+i) for j in range(t)) for i in range(m)] Kelem_to_Ci = {v:i for i,s in enumerate(Ci) for v in s} # maps v to [0,...,12]
W = ([[0]+ [1]*(len(K))] + [[1]+[Kelem_to_Ci[aj-ai] for aj in K] for ai in K])
# The nonzero elements of W are considered as elements of C_12, generated by # a matrix Omega of order 12 n = 18 U = matrix.circulant([int(i==1) for i in range(2*n)]) N = matrix.diagonal([1 if i else -1 for i in range(2*n)]) Omega = (U*N)**6 assert Omega**12 == I(36)
# The value w_{ij} is understood in the paper as matrix generated by Omega # acting on the left of a matrix L, which we now define. M = H-I(6).tensor_product(J(6)) L = matrix(list(reversed(I(6).rows()))).tensor_product(I(6))
# w_ij represents in the paper the matrix w_{ij}*L. We perform this action while # computing what is noted '[ M w_{ij} ]' in the paper. D = [[M*0 if w == 0 else M*(Omega**w)*L for w in R] for R in W] D = matrix.block(D)
# for v=1800 the construction is slightly different, and we must add to D a # matrix which we now compute. if v == 1800: abs = lambda M: matrix([[1 if x else 0 for x in R] for R in M.rows()])
M = (J(6)+I(6)).tensor_product(J(6)) # we define M = (J(6)+I(6)) x J(6) D2 = [[M*0 if w == 0 else M*abs((Omega**w)*L) for w in R] # '[ (J(6)+I(6)) x J(6) |w_{ij}| ]' for R in W] D = (D+matrix.block(D2))/2
return Graph([e for e,v in six.iteritems(D.dict()) if v == 1], multiedges=False, name="Janko-Kharaghani")
r""" Returns a (324,153,72,72)-strongly regular graph from [JKT01]_.
Build the graph using the description given in [JKT01]_, taking sets B1 and B163 in the text as adjacencies of vertices 1 and 163, respectively, and taking the edge orbits of the group `G` provided.
EXAMPLES::
sage: Gamma=graphs.JankoKharaghaniTonchevGraph() # long time sage: Gamma.is_strongly_regular(parameters=True) # long time (324, 153, 72, 72)
REFERENCES:
.. [JKT01] \Z.Janko, H.Kharaghani, V.D.Tonchev The existence of a Bush-type Hadamard matrix of order 324 and two new infinite classes of symmetric designs. Des. Codes Cryptogr. 24(2001), 225--232
""" from itertools import product from sage.misc.misc_c import prod from sage.combinat.permutation import Permutation as P from sage.libs.gap.libgap import libgap
m1=prod(P((9*x+k,9*x+k+3,9*x+k+6)) for k in range(1, 4) for x in range(36)) m2=prod(P((3*x+1,3*x+2,3*x+3)) for x in range(108)) t=prod(prod(map(P,[(9*x+2,9*x+3),(9*x+4,9*x+7),(9*x+5,9*x+9),(9*x+6,9*x+8)])) for x in range(36)) n1=prod(prod(map(P,[(1+x,19+x,37+x),(55+x,73+x,91+x),(109+x,127+x,145+x), (163+x,181+x,199+x),(217+x,235+x,253+x),(271+x,289+x,307+x)])) for x in range(18)) n2=prod(prod(map(P,[(1+x,55+x,109+x),(19+x,73+x,127+x),(37+x,91+x,145+x), (163+x,217+x,271+x),(181+x,235+x,289+x),(199+x,253+x,307+x)])) for x in range(18)) s=prod(prod(map(P,[(19+x,37+x),(55+x,109+x),(73+x,145+x),(91+x,127+x), (181+x,199+x),(217+x,271+x),(235+x,307+x),(253+x,289+x)])) for x in range(18)) k=prod(prod(map(P,[(18*x+1,18*x+10),(18*x+2,18*x+11),(18*x+3,18*x+12), (18*x+4,18*x+13),(18*x+5,18*x+14),(18*x+6,18*x+15),(18*x+7,18*x+16), (18*x+8,18*x+17),(18*x+9,18*x+18)])) for x in range(18)) G=libgap.Group(map(lambda p: libgap.PermList(p), [m1,m2,t,n1,n2,s,k])) st=libgap.Group(map(lambda p: libgap.PermList(p), [t,s])) B1=(19,22,25,29,30,31,33,34,35,37,40,43,47,48,49,51,52,53,55,56,57,65, 66,67,68,70,72,76,77,78,79,80,81,82,86,90,92,93,95,96,98,99,100,105,107, 109,110,111,119,120,121,122,124,126,128,129,131,132,134,135,136,141,143, 148,149,150,151,152,153,154,158,162,167,168,170,171,172,176,177,179,180, 184,186,187,188,190,191,192,193,196,202,204,205,206,208,209,210,211,214, 218,219,221,225,226,227,228,229,232,236,237,238,241,244,245,246,249,251, 254,255,256,259,262,265,266,268,270,272,273,275,279,280,281,282,283,286, 290,291,292,295,298,301,302,304,306,308,309,310,313,316,317,318,321,323) B163=(5,6,8,9,10,14,15,17,18,22,24,25,26,28,29,30,31,34,40,42,43,44,46, 47,48,49,52,56,57,59,63,64,65,66,67,70,74,75,76,79,82,83,84,87,89,92,93, 94,97,100,103,104,106,108,110,111,113,117,118,119,120,121,124,128,129, 130,133,136,139,140,142,144,146,147,148,151,154,155,156,159,161,181,185, 189,191,192,194,195,197,198,199,203,207,209,210,212,213,215,216,217,222, 224,229,230,231,232,233,234,236,237,238,240,241,242,244,245,246,254,255, 256,257,259,261,262,265,268,271,276,278,283,284,285,286,287,288,290,291, 292,293,295,297,298,301,304,308,309,310,312,313,314,316,317,318) Gamma=Graph(multiedges=False,name='Janko-Kharaghani-Tonchev') for i,b in ((1,B1),(163,B163)): for j in map(lambda x: x[0], st.OrbitsDomain(b)): Gamma.add_edges(map(tuple,G.Orbit(libgap.Set([i,j]), libgap.OnSets))) Gamma.relabel() return Gamma
r""" Return a `(765, 192, 48, 48)`-strongly regular graph.
Existence of a strongly regular graph with these parameters was claimed in [IK03]_. Implementing the construction in the latter did not work, however. This function implements the following instructions, shared by Yury Ionin and Hadi Kharaghani.
Let `A` be the affine plane over the field `GF(3)=\{-1,0,1\}`. Let
.. MATH::
\phi_1(x,y) &= x\\ \phi_2(x,y) &= y\\ \phi_3(x,y) &= x+y\\ \phi_4(x,y) &= x-y\\
For `i=1,2,3,4` and `j\in GF(3)`, let `L_{i,j}` be the line in `A` defined by `\phi_i(x,y)=j`. Let `\mathcal M` be the set of all 12 lines `L_{i,j}`, plus the empty set. Let `\pi` be the permutation defined on `\mathcal M` by `\pi(L_{i,j}) = L_{i,j+1}` and `\pi(\emptyset) = \emptyset`, so that `\pi` has three orbits of cardinality 3 and one of cardinality 1.
Let `A=(p_1,...,p_9)` with `p_1=(-1,1)`, `p_2=(-1,0)`, `p_3=(-1,1)`, `p_4=(0,-1)`, `p_5=(0,0)`, `p_6=(0,1)`, `p_7=(1,-1)`, `p_8=(1,0)`, `p_9=(1,1)`. Note that `p_i+p_{10-i}=(0,0)`. For any subset `X` of `A`, let `M(X)` be the `(0,1)`-matrix of order 9 whose `(i,j)`-entry equals 1 if and only if `p_{10-i}-p_j\in X`. Note that `M` is a symmetric matrix.
An `MF`-tuple is an ordered quintuple `(X_1, X_2, X_3, X_4, X_5)` of subsets of `A`, of which one is the empty set and the other four are pairwise non-parallel lines. Such a quintuple generates the following block matrix:
.. MATH::
N(X_1, X_2, X_3, X_4, X_5) = \left( \begin{array}{ccccc} M(X_1) & M(X_2) & M(X_3) & M(X_4) & M(X_5)\\ M(X_2) & M(X_3) & M(X_4) & M(X_5) & M(X_1)\\ M(X_3) & M(X_4) & M(X_5) & M(X_1) & M(X_2)\\ M(X_4) & M(X_5) & M(X_1) & M(X_2) & M(X_3)\\ M(X_5) & M(X_1) & M(X_2) & M(X_3) & M(X_4) \end{array}\right)
Observe that if `(X_1, X_2, X_3, X_4, X_5)` is an `MF`-tuple, then `N(X_1, X_2, X_3, X_4, X_5)` is the symmetric incidence matrix of a symmetric `(45, 12, 3)`-design.
Let `\mathcal F` be the set of all `MF`-tuples and let `\sigma` be the following permutation of `\mathcal F`:
.. MATH::
\sigma(X_1, X_2, X_3, X_4, X_5) & = (X_2, X_3, X_4, X_5, X_1)\\ \pi(X_1, X_2, X_3, X_4, X_5) & = (\pi(X_1), \pi(X_2), \pi(X_3), \pi(X_4), \pi(X_5))\\
Observe that `\sigma` and `\pi` commute, and generate a (cyclic) group `G` of order 15. We will from now on identify `G` with the (cyclic) multiplicative group of the field `GF(16)` equal to `\{\omega^0,...,\omega^{14}\}`. Let `W=[w_{ij}]` be the following matrix of order 17 over `GF(16)=\{a_1,...,a_16\}`:
.. MATH::
w_{ij}=\left\{\begin{array}{ll} a_i+a_j & \text{if }1\leq i\leq 16, 1\leq j\leq 16,\\ 1 & \text{if }i=17, j\neq 17,\\ 1 & \text{if }i\neq 17, j= 17,\\ 0 & \text{if }i=j=17 \end{array}\right.
The diagonal entries of `W` are equal to 0, each off-diagonal entry can be represented as `\omega^k` with `0\leq k\leq 14`. Matrix `W` is a symmetric `BGW(17,16,15; G)`.
Fix an `MF`-tuple `(X_1, X_2, X_3, X_4, X_5)` and let `S` be the block matrix obtained from `W` by replacing every diagonal entry of `W` by the zero matrix of order 45, and every off-diagonal entry `\omega^k` by the matrix `N(\sigma^k(X_1, X_2, X_3, X_4, X_5))` (through the association of `\omega^k` with an element of `G`). Then `S` is a symmetric incidence matrix of a symmetric `(765, 192, 48)`-design with zero diagonal, and therefore `S` is an adjacency matrix of a strongly regular graph with parameters `(765, 192, 48, 48)`.
EXAMPLES::
sage: g = graphs.IoninKharaghani765Graph(); g Ionin-Kharaghani: Graph on 765 vertices
TESTS::
sage: graphs.strongly_regular_graph(765, 192, 48, 48) Ionin-Kharaghani: Graph on 765 vertices
.. TODO::
An update to [IK03]_ meant to fix the problem encountered became available 2016/02/24, see http://www.cs.uleth.ca/~hadi/research/IoninKharaghani.pdf
REFERENCE:
.. [IK03] Yury Ionin, Hadi Kharaghani New families of strongly regular graphs. Journal of Combinatorial Designs, Vol 11 (2003), no. 3, 208--217, :doi:`10.1002/jcd.10038` """
# the four φ functions lambda xy: 0*xy[0]+1*xy[1], lambda xy: 1*xy[0]+1*xy[1], lambda xy: 1*xy[0]-1*xy[1]]
# Defining L_{i,j}
# Defining pi
# Defining A
for i in range(9)] for j in range(9)])
for i in range(len(Xi))])
# The matrix W, with off-diagonal entries equal to integers 1,...,15 # (instead of x^1,...,x^15) [[1]*16+[0]])
# Associate a matrix to every entry of W
r""" Returns a (216,40,4,8)-strongly regular graph from [CRS16]_.
Build the graph, interpreting the `U_4(2)`-action considered in [CRS16]_ as the one on the hyperbolic lines of the corresponding unitary polar space, and then doing the unique merging of the orbitals leading to a graph with the parameters in question.
EXAMPLES::
sage: G=graphs.U42Graph216() # optional - gap_packages (grape) sage: G.is_strongly_regular(parameters=True) # optional - gap_packages (grape) (216, 40, 4, 8)
REFERENCES:
.. [CRS16] \Dean Crnković, Sanja Rukavina, Andrea Švob, Strongly regular graphs from orthogonal groups `O^+(6,2)` and `O^-(6,2)`. :arxiv:`1609.07133` """ from sage.libs.gap.libgap import libgap from sage.misc.package import is_package_installed, PackageNotFoundError
if not is_package_installed('gap_packages'): raise PackageNotFoundError('gap_packages')
adj_list=libgap.function_factory("""function() local gg, hl, o216, a216, x, h, re, G; LoadPackage("grape"); gg:=SpecialUnitaryGroup(4,2); hl:=Z(2)*[ [0,0,1,0], [1,1,0,0], [0,1,0,1], [0,1,1,0], [1,1,0,1]]; o216:=Orbit(gg,Set(hl),OnSets); a216:=Action(gg,o216,OnSets); h:=Stabilizer(a216,1); re:=Filtered(Orbits(h,[1..216]),x->Length(x)=20); G:=EdgeOrbitsGraph(a216, [[1,re[1][1]], [1,re[2][1]]]); return List([1..216],x->Adjacency(G,x)); end;""")
adj = adj_list() # for each vertex, we get the list of vertices it is adjacent to G = Graph(((i,int(j-1)) for i,ni in enumerate(adj) for j in ni), format='list_of_edges', multiedges=False) G.name('U42Graph216') return G
r""" Returns a (540,187,58,68)-strongly regular graph from [CRS16]_.
Build the graph, interpreting the `U_4(2)`-action considered in [CRS16]_ as the action of `U_4(2)=Sp_4(3)<U_4(3)` on the nonsingular, w.r.t. to the Hermitean form stabilised by `U_4(3)`, points of the 3-dimensional projective space over `GF(9)`. There are several possible mergings of orbitals, some leading to non-isomorphic graphs with the same parameters. We found the merging here using [COCO]_.
EXAMPLES::
sage: G=graphs.U42Graph540() # optional - gap_packages (grape) sage: G.is_strongly_regular(parameters=True) # optional - gap_packages (grape) (540, 187, 58, 68)
""" from sage.libs.gap.libgap import libgap from sage.misc.package import is_package_installed, PackageNotFoundError
if not is_package_installed('gap_packages'): raise PackageNotFoundError('gap_packages')
adj_list=libgap.function_factory("""function() local f, o540, a540, x, oh, h, lo, G; LoadPackage("grape"); f:=Sp(4,3); o540:=Orbit(f,Z(3)^0*[1,0,0,Z(9)],OnLines); a540:=Action(f,o540,OnLines); h:=Stabilizer(a540,1); oh:=Orbits(h,[1..540]); lo:=List([8,9,10,11,12,16,19,22,23,24],x->[1,oh[x+1][1]]); G:=EdgeOrbitsGraph(a540,lo); return List([1..540],x->Adjacency(G,x)); end;""")
adj = adj_list() # for each vertex, we get the list of vertices it is adjacent to G = Graph(((i,int(j-1)) for i,ni in enumerate(adj) for j in ni), format='list_of_edges', multiedges=False) G.name('U42Graph540') return G |