|
Strongly Regular Graph
In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have common neighbours. * Every two non-adjacent vertices have common neighbours. The complement of an is also strongly regular. It is a . 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 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 but fu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clebsch Graph
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 , who used it to evaluate the Ramsey number ''R''(3,3,3) = 17.. Construction The dimension-5 folded cube graph (the 5-regular Clebsch graph) may be constructed by adding edges between opposite pairs of vertices in a 4-dimensional hypercube graph. (In an ''n''-dimensional hypercube, a pair of vertices are ''opposite'' if the shortest path between them has ''n'' edges.) Alternatively, it can be formed from a 5-dime ... [...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 vertices. As a strongly regular graph with the third para ... [...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 Knese ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
M22 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 Knese ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Sims-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) , 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 7- regular 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 (7,5)-cage. Construction Here are two 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 7-set ''abcdefg''. Canonicalize each such Fano plane (e.g. by reducing to lexicographic order) and discard duplicates. Exactly 15 Fano planes remai ... [...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, ... [...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 2n-gons with ''n'' = 2. They are also precisely the 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. * For every point ''p'' not on a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chang Graphs
In the mathematical field of graph theory, the Chang graphs are a set of three 12- regular undirected graphs, each with 28 vertices and 168 edges. They are strongly regular, with the same parameters and spectra 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Line Graph
In the mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between 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, and by Whitney's theorem the same t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Graph
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the ''parts'' of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets U and V may be thought of as a coloring of the graph with two colors: if one colors all nodes in U blue, and all nodes in V red, each edge has endpoints of differing colors, as is required in the graph coloring problem.. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle: after one node is colored blue and another red, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color. One often writes G=(U,V,E) to denote a bipartite graph whose partition has the parts U and V, with E denoting ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.svg "Click for more on -> Generalized Quadrangle")
