|
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, 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, a ... [...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] |
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] |
Mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics with the major subdisciplines of number theory, algebra, geometry, and analysis, respectively. There is no general consensus among mathematicians about a common definition for their academic discipline. Most mathematical activity involves the discovery of properties of abstract objects and the use of pure reason to prove them. These objects consist of either abstractions from nature orin modern mathematicsentities that are stipulated to have certain properties, called axioms. A ''proof'' consists of a succession of applications of deductive rules to already established results. These results include previously proved theorems, axioms, andin case of abstraction from naturesome basic properties that are considered true starting points of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by '' edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Regular Graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree is called a graph or regular graph of degree . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree. Regular graphs of degree at most 2 are easy to classify: a graph consists of disconnected vertices, a graph consists of disconnected edges, and a graph consists of a disjoint union of cycles and infinite chains. A graph is known as a cubic graph. A strongly regular graph is a regular graph where every adjacent pair of vertices has the same number of neighbors in common, and every non-adjacent pair of vertices has the same number of neighbors in common. The smallest graphs that are regular but not strong ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Undirected Graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' means that ''A'' owes money to ''B'', th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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] |
Spectral Graph Theory
In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. The adjacency matrix of a simple undirected graph is a real symmetric matrix and is therefore orthogonally diagonalizable; its eigenvalues are real algebraic integers. While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one. Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number. Cospectral graphs Two graphs are called cospectral or isospectral if the adjacency matrices of the graphs are isospectral, that is, if the adjacency matrices have equal multisets of eigenvalues. Cospectral graphs need not be isomorphic, but isomorphic graphs a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complete Graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction). Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete graphs, with their vertices placed on the points of a regular polygon, had already appeared in the 13th century, in the work of Ramon Llull. Such a drawing is sometimes referred to as a mystic rose. Properties The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word , but the German name for a complete graph, , does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory. has edges (a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Two-graph
In mathematics, a two-graph is a set of (unordered) triples chosen from a finite vertex set ''X'', such that every (unordered) quadruple from ''X'' contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph. Two-graphs have been studied because of their connection with equiangular lines and, for regular two-graphs, strongly regular graphs, and also finite groups because many regular two-graphs have interesting automorphism groups. A two-graph is not a graph and should not be confused with other objects called 2-graphs in graph theory, such as 2-regular graphs. Examples On the set of vertices the following collection of unordered triples is a two-graph: :123 124 135 146 156 236 245 256 345 346 This two-graph is a regular two-graph since each pair of distinct vertices appear ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Shrikhande Graph
In the mathematics, mathematical field of graph theory, the Shrikhande graph is a Gallery of named graphs, named graph discovered by S. S. Shrikhande in 1959.. It is a strongly regular graph with 16 vertex (graph theory), vertices and 48 edge (graph theory), edges, with each vertex having degree (graph theory), degree 6. Every pair of nodes has exactly two other neighbors in common, whether the pair of nodes is connected or not. 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 graph, strongly regular and its parameters are: , i.e., \lambda = \mu = 2. This equality implies that the gr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
