Livingstone graph | |
---|---|
![]() | |
Vertices | 266 |
Edges | 1463 |
Radius | 4 |
Diameter | 4 |
Girth | 5 |
Automorphisms | 175560 (J1) |
Properties | Symmetric Distance-transitive Primitive |
Table of graphs and parameters |
In the mathematical field of graph theory, the Livingstone graph is a distance-transitive graph with 266 vertices and 1463 edges. Its intersection array is {11,10,6,1;1,1,5,11}. [1] It is the largest distance-transitive graph with degree 11. [2]
The automorphism group of the Livingstone graph is the sporadic simple group J1, and the stabiliser of a point is PSL(2,11). As the stabiliser is maximal in J1, it acts primitively on the graph.
As the Livingstone graph is distance-transitive, PSL(2,11) acts transitively on the set of 11 vertices adjacent to a reference vertex v, and also on the set of 12 vertices at distance 4 from v. The second action is equivalent to the standard action of PSL(2,11) on the projective line over F11; the first is equivalent to an exceptional action on 11 points, related to the Paley biplane.
In mathematics, a group action on a space is a group homomorphism of a given group into the group of transformations of the space. Similarly, a group action on a mathematical structure is a group homomorphism of a group into the automorphism group of the structure. It is said that the group acts on the space or structure. If a group acts on a structure, it will usually also act on objects built from that structure. For example, the group of Euclidean isometries acts on Euclidean space and also on the figures drawn in it. For example, it acts on the set of all triangles. Similarly, the group of symmetries of a polyhedron acts on the vertices, the edges, and the faces of the polyhedron.
Transitivity or transitive may refer to:
In the mathematical disciplines of topology and geometry, an orbifold is a generalization of a manifold. Roughly speaking, an orbifold is a topological space which is locally a finite group quotient of a Euclidean space.
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
In mathematics, especially in the group theoretic area of algebra, the projective linear group (also known as the projective general linear group or PGL) is the induced action of the general linear group of a vector space V on the associated projective space P(V). Explicitly, the projective linear group is the quotient group
In the mathematical field of graph theory, a vertex-transitive graph is a graph G in which, given any two vertices v1 and v2 of G, there is some automorphism
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
In the mathematical field of graph theory, a graph G is symmetric if, given any two pairs of adjacent vertices u1—v1 and u2—v2 of G, there is an automorphism
In the mathematical field of graph theory, the Desargues graph is a distance-transitive, cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.
In the mathematical field of graph theory, a transitive reduction of a directed graph D is another directed graph with the same vertices and as few edges as possible, such that for all pairs of vertices v, w a (directed) path from v to w in D exists if and only if such a path exists in the reduction. Transitive reductions were introduced by Aho, Garey & Ullman (1972), who provided tight bounds on the computational complexity of constructing them.
In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 known cubic distance-regular graphs. It is named after Harold Scott MacDonald Coxeter.
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices v and w at any distance i, and any other two vertices x and y at the same distance, there is an automorphism of the graph that carries v to x and w to y. Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith.
In the mathematical field of graph theory, the Shrikhande graph is a named graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has exactly two other neighbors in common, whether the pair of nodes is connected or not.
In group theory, a branch of mathematics, the automorphisms and outer automorphisms of the symmetric groups and alternating groups are both standard examples of these automorphisms, and objects of study in their own right, particularly the exceptional outer automorphism of S6, the symmetric group on 6 elements.
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity.
In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is the dimension-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the dimension-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number R(3,3,3) = 17.
In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.
In the mathematical field of graph theory, the Nauru graph is a symmetric, bipartite, cubic graph with 24 vertices and 36 edges. It was named by David Eppstein after the twelve-pointed star in the flag of Nauru.
The Gosset graph, named after Thorold Gosset, is a specific regular graph (1-skeleton of the 7-dimensional 321 polytope) with 56 vertices and valency 27.
In the mathematical field of graph theory, the Klein graphs are two different but related regular graphs, each with 84 edges. Each can be embedded in the orientable surface of genus 3, in which they form dual graphs.