|
Regular Graphs
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 internal vertex are equal to each other. A regular graph with vertices of degree is called a graph or regular graph of degree . Special cases 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 strongly regular are the cycle graph and the circulant graph on 6 vertices. The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Graph Theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') which are connected by ''Glossary of graph theory terms#edge, edges'' (also called ''arcs'', ''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 (mathematics), set of vertices (also called nodes or points); * ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Hamiltonian Cycle
In the mathematics, mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path (graph theory), path in an undirected or directed graph that visits each vertex (graph theory), vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle (graph theory), cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details. Hamiltonian paths and cycles are named after William Rowan Hamilton, who invented the icosian game, now also known as ''Hamilton's puzzle'', which involves finding a Hamiltonian cycle in the edge graph of the dodecahedron. Hamilton solved this problem using the icosian calculus, an algebraic structur ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
 |
Highly Irregular Graph
In graph theory, a highly irregular graph is a graph in which, for every vertex, all neighbors of that vertex have distinct degrees. History Irregular graphs were initially characterized by Yousef Alavi, Gary Chartrand, Fan Chung, Paul Erdős, Ronald Graham, and Ortrud Oellermann. They were motivated to define the ‘opposite’ of a regular graph, a concept which has been thoroughly studied and well understood. Locality and regularity Defining an ‘irregular graph’ was not immediately obvious. In a ''k''-regular graph, all vertices have degree ''k''. In any graph ''G'' with more than one vertex, two vertices in ''G'' must have the same degree, so an irregular graph cannot be defined as a graph with all vertices of different degrees. One may be tempted then to define an irregular graph as having all vertices of distinct degrees except for two, but these types of graphs are also well understood and thus not interesting. Graph theorists thus turned to the issue of lo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
Cage Graph
In the mathematical field of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an is defined to be a graph in which each vertex has exactly neighbors, and in which the shortest cycle has a length of exactly . An is an with the smallest possible number of vertices, among all . A is often called a . It is known that an exists for any combination of and . It follows that all exist. If a Moore graph exists with degree and girth , it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth must have at least :1 + r\sum_^(r-1)^i vertices, and any cage with even girth must have at least :2\sum_^(r-1)^i vertices. Any with exactly this many vertices is by definition a Moore graph and therefore automatically a cage. There may exist multiple cages for a given combination of and . For instance there are three non-isomorphic , each with 70 vertices: the , the Harri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Moore Graph
In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is and its diameter is , its girth must equal . This is true, for a graph of degree and diameter , if and only if its number of vertices (its order) equals :1 + d\sum_^(d-1)^i, an upper bound on the largest possible number of vertices in any graph with this degree and diameter. Therefore, these graphs solve the degree diameter problem for their parameters. Another equivalent definition of a Moore graph is that it has girth and precisely cycles of length , where and are, respectively, the numbers of vertices and edges of . They are in fact extremal with respect to the number of cycles whose length is the girth of the graph. Moore graphs were named by after Edward F. Moore, who posed the question of describing and classifying these graphs. As well as having the maximum p ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
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] |
|
|
Random Regular Graph
A random ''r''-regular graph is a graph selected from \mathcal_, which denotes the probability space of all ''r''-regular graphs on n vertices, where 3 \le r 0 is a positive constant, and d is the least integer satisfying (r-1)^ \ge (2 + \epsilon)rn \ln n then, asymptotically almost surely, a random ''r''-regular graph has diameter at most ''d''. There is also a (more complex) lower bound on the diameter of ''r''-regular graphs, so that almost all ''r''-regular graphs (of the same size) have almost the same diameter. The distribution of the number of short cycles is also known: for fixed m \ge 3, let Y_3,Y_4,...Y_m be the number of cycles of lengths up to m. Then the Y_iare asymptotically independent Poisson random variables with means \lambda_i=\frac Algorithms for random regular graphs It is non-trivial to implement the random selection of ''r''-regular graphs efficiently and in an unbiased way, since most graphs are not regular. The ''pairing model'' (also ''configuration ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Journal Of Graph Theory
The ''Journal of Graph Theory'' is a peer-reviewed mathematics journal specializing in graph theory and related areas, such as structural results about graphs, graph algorithms with theoretical emphasis, and discrete optimization on graphs. The scope of the journal also includes related areas in combinatorics and the interaction of graph theory with other mathematical sciences. It is published by John Wiley & Sons. The journal was established in 1977 by Frank Harary.Frank Harary a biographical sketch at the ACM site The are [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Adjacency Algebra
In algebraic graph theory, the adjacency algebra of a graph ''G'' is the algebra of polynomials in the adjacency matrix ''A''(''G'') of the graph. It is an example of a matrix algebra and is the set of the linear combinations of powers of ''A''.Algebraic graph theory, by Norman L. Biggs, 1993, p. 9/ref> Some other similar mathematical objects are also called "adjacency algebra". Properties Properties of the adjacency algebra of ''G'' are associated with various spectral, adjacency and connectivity properties of ''G''. ''Statement''. The number of walks of length ''d'' between vertices ''i'' and ''j'' is equal to the (''i'', ''j'')-th element of ''Ad''. ''Statement''. The dimension of the adjacency algebra of a connected graph of diameter ''d'' is at least ''d'' + 1. ''Corollary''. A connected graph of diameter ''d'' has at least ''d'' + 1 distinct eigenvalues. Spectral Properties Adjacency algebra is closely linked with Spectral graph ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Matrix Of Ones
In mathematics, a matrix of ones or all-ones matrix is a matrix with every entry equal to one. For example: :J_2 = \begin 1 & 1 \\ 1 & 1 \end,\quad J_3 = \begin 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end,\quad J_ = \begin 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end,\quad J_ = \begin 1 & 1 \end.\quad Some sources call the all-ones matrix the unit matrix, but that term may also refer to the identity matrix, a different type of matrix. A vector of ones or all-ones vector is matrix of ones having row or column form; it should not be confused with ''unit vectors''. Properties For an matrix of ones ''J'', the following properties hold: * The trace of ''J'' equals ''n'', and the determinant equals 0 for ''n'' ≥ 2, but equals 1 if ''n'' = 1. * The characteristic polynomial of ''J'' is (x - n)x^. * The minimal polynomial of ''J'' is x^2-nx. * The rank of ''J'' is 1 and the eigenvalues are ''n'' with multiplicity 1 and 0 with multiplicity . * J^k = n^ J for k = 1,2,\ldots .. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
|
Perron–Frobenius Theorem
In matrix theory, the Perron–Frobenius theorem, proved by and , asserts that a real square matrix with positive entries has a unique eigenvalue of largest magnitude and that eigenvalue is real. The corresponding eigenvector can be chosen to have strictly positive components, and also asserts a similar statement for certain classes of nonnegative matrices. This theorem has important applications to probability theory (ergodicity of Markov chains); to the theory of dynamical systems ( subshifts of finite type); to economics ( Okishio's theorem, Hawkins–Simon condition); to demography ( Leslie population age distribution model); to social networks ( DeGroot learning process); to Internet search engines (PageRank); and even to ranking of American football teams. The first to discuss the ordering of players within tournaments using Perron–Frobenius eigenvectors is Edmund Landau. Statement Let positive and non-negative respectively describe matrices with exclusively positi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
|
 |
Eigenvalue
In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a constant factor \lambda when the linear transformation is applied to it: T\mathbf v=\lambda \mathbf v. The corresponding eigenvalue, characteristic value, or characteristic root is the multiplying factor \lambda (possibly a negative or complex number). Geometrically, vectors are multi-dimensional quantities with magnitude and direction, often pictured as arrows. A linear transformation rotates, stretches, or shears the vectors upon which it acts. A linear transformation's eigenvectors are those vectors that are only stretched or shrunk, with neither rotation nor shear. The corresponding eigenvalue is the factor by which an eigenvector is stretched or shrunk. If the eigenvalue is negative, the eigenvector's direction is reversed. Th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |