|
Strongly Regular Graph
In graph theory, a strongly regular graph (SRG) is a regular graph with vertices and degree such that for some given integers \lambda, \mu \ge 0 * every two adjacent vertices have common neighbours, and * every two non-adjacent vertices have common neighbours. Such a strongly regular graph is denoted by . Its complement graph is also strongly regular: it is an . A strongly regular graph is a distance-regular graph with diameter 2 whenever μ is non-zero. It is a locally linear graph whenever . Etymology A strongly regular graph is denoted as an srg(''v'', ''k'', λ, μ) in the literature. By convention, graphs which satisfy the definition trivially are excluded from detailed studies and lists of strongly regular graphs. These include the disjoint union of one or more equal-sized complete graphs, and their complements, the complete multipartite graphs with equal-sized independent sets. Andries Brouwer and Hendrik van Maldeghem (see #References) use an alternate bu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Shrikhande Graph
In the mathematical field of graph theory, the Shrikhande graph is a 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 or not the pair of nodes is connected. Construction The Shrikhande graph can be constructed as a Cayley graph. The vertex set is \mathbb_4 \times \mathbb_4. Two vertices are adjacent if and only if the difference is in \. Properties In the Shrikhande graph, any two vertices ''I'' and ''J'' have two distinct neighbors in common (excluding the two vertices ''I'' and ''J'' themselves), which holds true whether or not ''I'' is adjacent to ''J''. In other words, it is strongly regular and its parameters are: , i.e., \lambda = \mu = 2. This equality implies that the graph is associated with a symmetric BIBD. The Shrikhande graph shares these parameters with exactly one other graph, the 4× ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Higman–Sims Graph
In mathematical graph theory, the Higman–Sims graph is a 22- regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was first constructed by and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, a subgroup of index two in the group of automorphisms of the Hoffman–Singleton graph. Construction From M22 graph Take the M22 graph, a strongly regular graph srg(77,16,0,4) and augment it with 22 new vertices corresponding to the points of S(3,6,22), each block being connected to its points, and one additional vertex ''C'' connected to the 22 points. From Hoffman–Singleton graph There are 100 independent sets of size 15 in the Hoffman–Singleton graph. Create a new graph with 100 corresponding vertices, and connect vertices wh ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Brouwer–Haemers Graph
In the mathematical field of graph theory, the Brouwer–Haemers graph is a 20- regular undirected graph with 81 vertices and 810 edges. It is a strongly regular graph, a distance-transitive graph, and a Ramanujan graph. Although its construction is folklore, it was named after Andries Brouwer and Willem H. Haemers, who proved its uniqueness as a strongly regular graph. Construction The Brouwer–Haemers graph has several related algebraic constructions. One of the simplest is as a degree-4 generalized Paley graph: it can be defined by making a vertex for each element in the finite field GF(81) and an edge for every two elements that differ by a fourth power. Properties The Brouwer–Haemers graph is the unique strongly regular graph with parameters (81, 20, 1, 6). This means that it has 81 vertices, 20 edges per vertex, 1 triangle per edge, and 6 length-two paths connecting each non-adjacent pair of distinct vertices. As a strongly regular graph with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mesner Graph
The M22 graph, also called the Mesner graph or Witt graph, is the unique strongly regular graph with parameters (77, 16, 0, 4). Brouwer, Andries E. “M22 Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. Accessed 29 May 2018. It is constructed from the Steiner system (3, 6, 22) by representing its 77 blocks as vertices and joining two vertices iff they have no terms in common or by deleting a vertex and its neighbors from the Higman–Sims graph.Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html. Accessed 29 May 2018.Vis, Timothy. “The Higman–Sims Graph.” University of Colorado Denver, http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf. Accessed 29 May 2018. For any term, the family of blocks that contain that term forms an independent set in this graph, with 21 vertices. In a result analogous to the Erdős–Ko–Rado theorem (which can be formulated in terms of independent sets in Knes ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Gewirtz Graph
The Gewirtz graph is a strongly regular graph with 56 vertices and valency 10. It is named after the mathematician Allan Gewirtz, who described the graph in his dissertation. ''Graphs with Maximal Even Girth'', Ph.D. Dissertation in Mathematics, City University of New York, 1967. Construction The Gewirtz graph can be constructed as follows. Consider the unique ''S''(3, 6, 22) Steiner system, with 22 elements and 77 blocks. Choose a random element, and let the vertices be the 56 blocks not containing it. Two blocks are adjacent when they are disjoint. With this construction, one can embed the Gewirtz graph in the |
Hoffman–Singleton Graph
In the mathematical field of graph theory, the Hoffman–Singleton graph is a undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman and Robert Singleton while trying to classify all Moore graphs, and is the highest-order Moore graph known to exist. Since it is a Moore graph where each vertex has degree 7, and the girth is 5, it is a . Construction Here are some constructions of the Hoffman–Singleton graph. Construction from pentagons and pentagrams Take five pentagons ''Ph'' and five pentagrams ''Qi'' . Join vertex ''j'' of ''Ph'' to vertex ''h'' · ''i'' + ''j'' of ''Qi'' (all indices are modulo 5.) Construction from PG(3,2) Take a Fano plane on seven elements, such as and apply all 2520 even permutations on the ''abcdefg''. Canonicalize each such Fano plane (e.g. by reducing to lexicographic order) and discard duplicates. Exactly 15 Fano planes remain. Each (tripl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Schläfli Graph
In the mathematical field of graph theory, the Schläfli graph, named after Ludwig Schläfli, is a 16- regular undirected graph with 27 vertices and 216 edges. It is a strongly regular graph with parameters srg(27, 16, 10, 8). Construction The intersection graph of the 27 lines on a cubic surface is a locally linear graph that is the complement of the Schläfli graph. That is, two vertices are adjacent in the Schläfli graph if and only if the corresponding pair of lines are skew.. The Schläfli graph may also be constructed from the system of eight-dimensional vectors :(1, 0, 0, 0, 0, 0, 1, 0), :(1, 0, 0, 0, 0, 0, 0, 1), and :(−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2), and the 24 other vectors obtained by permuting the first six coordinates of these three vectors. These 27 vectors correspond to the vertices of the Schläfli graph; two vertices are adjacent if and only if the corresponding two vectors have 1 as their inner product.. Alternately, th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Generalized Quadrangle
In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles yet containing many quadrangles. A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = 4 and near polygon, near 2n-gons with ''n'' = 2. They are also precisely the Partial geometry, partial geometries pg(''s'',''t'',α) with α = 1. Definition A generalized quadrangle is an incidence structure (''P'',''B'',I), with I ⊆ ''P'' × ''B'' an incidence relation, satisfying certain axioms. Elements of ''P'' are by definition the ''points'' of the generalized quadrangle, elements of ''B'' the ''lines''. The axioms are the following: * There is an ''s'' (''s'' ≥ 1) such that on every line there are exactly ''s'' + 1 points. There is at most one point on two distinct lines. * There is a ''t'' (''t'' ≥ 1) such that through every point there are exactly ''t'' + 1 lines. There is at most one line through two distinct points. * F ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chang Graphs
In the mathematical field of graph theory, the Chang graphs are three 12- regular undirected graphs, each with 28 vertices and 168 edges. They are strongly regular, with the same parameters and spectrum as the line graph ''L''(''K''8) of the complete graph ''K''''8''. Each of these three graphs may be obtained by graph switching from ''L''(''K''8). That is, a subset ''S'' of the vertices of ''L''(''K''8) is chosen, each edge that connects a vertex in ''S'' with a vertex not in ''S'' is deleted from ''L''(''K''8), and an edge is added for each pair of vertices (with again one in ''S'' and one not in ''S'') that were not already connected by an edge. Among the graphs that can be generated in this way, three of them are the Chang graphs. The Chang graphs are named after Chang Li-Chien, who proved that, with only these exceptions, every line graph of a complete graph is uniquely determined by its parameters as a strongly regular graph.. See also *Shrikhande graph In the mathemat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Line Graph
In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge in , make a vertex in ; for every two edges in that have a vertex in common, make an edge between their corresponding vertices in . The name ''line graph'' comes from a paper by although both and used the construction before this. Other terms used for the line graph include the covering graph, the derivative, the edge-to-vertex dual, the conjugate, the representative graph, and the θ-obrazom, as well as the edge graph, the interchange graph, the adjoint graph, and the derived graph., p. 71. proved that with one exceptional case the structure of a connected graph can be recovered completely from its line graph. Many other properties of line graphs follow by translating the properties of the underlying graph from vertices into edges ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
