|
Degree Diameter Problem
In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is bounded above by the Moore bound; for and , only the Petersen graph, the Hoffman-Singleton graph, and possibly graphs (not yet proven to exist) of diameter and degree attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound. Formula Let n_ be the maximum possible number of vertices for a graph with degree at most ''d'' and diameter ''k''. Then n_\leq M_, where M_ is the Moore bound: :M_ = \begin1 + d\frac & \textd>2 \\ 2k+1 & \textd=2\end This bound is attained for very few graphs, thus the study moves to how close there exist graphs to the Moore bound. For asymptotic behaviour note that M_ = d^k + O(d^). Define the parameter \mu_k=\liminf_\frac. It is conjectured that \mu_ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), have shaped much of mathematical history as new areas of mathematics are developed in order to prove them. Resolution of conjectures Proof Formal mathematics is based on ''provable'' truth. In mathematics, any number of cases supporting a universally quantified conjecture, no matter how large, is insufficient for establishing the conjecture's veracity, since a single counterexample could immediately bring down the conjecture. Mathematical journals sometimes publish the minor results of research teams having extended the search for a counterexample farther than previously done. For instance, the Collatz conjecture, which concerns whether or not certain sequences of integers terminate, has been tested for all integers up to 1.2 × 101 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Electronic Journal Of Combinatorics
The ''Electronic Journal of Combinatorics'' is a peer-reviewed open access scientific journal covering research in combinatorial mathematics. The journal was established in 1994 by Herbert Wilf (University of Pennsylvania) and Neil Calkin (Georgia Institute of Technology). The Electronic Journal of Combinatorics is a founding member of the Free Journal Network. According to the ''Journal Citation Reports'', the journal had a 2017 impact factor of 0.762. Editors-in-chief Current The current editors-in-chief at ''Electronic Journal of Combinatorics'' are: * Maria Axenovich, Karlsruhe Institute of Technology, Germany * Miklós Bóna, University of Florida, United States * Julia Böttcher, London School of Economics, United Kingdom * Richard A. Brualdi, University of Wisconsin, Madison, United States * Zdeněk Dvořák, Charles University, Czech Republic * Nikolaos Fountoulakis, University of Birmingham, United Kingdom * Eric Fusy, CNRS/LIX, École Polytechnique, France * Feli ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
American Mathematical Monthly
''The American Mathematical Monthly'' is a peer-reviewed scientific journal of mathematics. It was established by Benjamin Finkel in 1894 and is published by Taylor & Francis on behalf of the Mathematical Association of America. It is an expository journal intended for a wide audience of mathematicians, from undergraduate students to research professionals. Articles are chosen on the basis of their broad interest and reviewed and edited for quality of exposition as well as content. The editor-in-chief An editor-in-chief (EIC), also known as lead editor or chief editor, is a publication's editorial leader who has final responsibility for its operations and policies. The editor-in-chief heads all departments of the organization and is held accoun ... is Vadim Ponomarenko ( San Diego State University). The journal gives the Lester R. Ford Award annually to "authors of articles of expository excellence" published in the journal. Editors-in-chief The following persons are or have ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
MaxDDBS
The Maximum Degree-and-Diameter-Bounded Subgraph problem (MaxDDBS) is a problem in graph theory. Given a connected ''host graph G'', an upper bound for the degree ''d'', and an upper bound for the diameter ''k'', we look for the largest subgraph ''S'' of ''G'' with maximum degree at most ''d'' and diameter at most ''k''. This problem is also referred to as the Degree-Diameter Subgraph Problem, as it contains the degree diameter problem as a special case (namely, by taking a sufficiently large complete graph as a host graph). Despite being a natural generalization of the Degree-Diameter Problem, MaxDDBS only began to be investigated in 2011, while research in the Degree-Diameter Problem has been active since the 1960s. Regarding its computational complexity, the problem is NP-hard, and not in APX (i.e. it cannot be approximated to within a constant factor in polynomial In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Table Of Vertex-symmetric Digraphs
The best known vertex transitive digraphs (as of October 2008) in the directed Degree diameter problem In graph theory, the degree diameter problem is the problem of finding the largest possible graph (in terms of the size of its vertex set ) of diameter such that the largest degree of any of the vertices in is at most . The size of is boun ... are tabulated below. Table of the orders of the largest known vertex-symmetric graphs for the directed degree diameter problem The footnotes in the table indicate the origin of the digraph that achieves the given number of vertices: References * * * * * * {{citation , last1 = Loz , first1 = Eyal , last2 = Širáň , first2 = Jozef , title = New record graphs in the degree-diameter problem , journal = Australasian Journal of Combinatorics , volume = 41 , year = 2008 , pages = 63–80 , url = http://ajc.maths.uq.edu.au/pdf/41/ajc_v41_p063.pdf External links Vertex-symmetric Digraphs ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Table Of The Largest Known Graphs Of A Given Diameter And Maximal Degree
In graph theory, the degree diameter problem is the problem of finding the largest possible graph for a given maximum degree and diameter. The Moore bound sets limits on this, but for many years mathematicians in the field have been interested in a more precise answer. The table below gives current progress on this problem (excluding the case of degree 2, where the largest graphs are cycles with an odd number of vertices). Table of the orders of the largest known graphs for the undirected degree diameter problem Below is the table of the vertex numbers for the best-known graphs (as of June 2024) in the undirected degree diameter problem for graphs of degree at most 3 ≤ ''d'' ≤ 16 and diameter 2 ≤ ''k'' ≤ 10. Only a few of the graphs in this table (marked in bold) are known to be optimal (that is, largest possible). The remainder are merely the largest so far discovered, and thus finding a larger graph that is closer in order (in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cage (graph Theory)
In the mathematics, mathematical field of graph theory, a cage is a regular graph that has as few vertex (graph theory), vertices as possible for its girth (graph theory), girth. Formally, an is defined to be a graph (discrete mathematics), graph in which each vertex has exactly neighbors, and in which the shortest cycle (graph theory), 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 parity (mathematics), odd girth must have at least :1 + r\sum_^(r-1)^i vertices, and any cage with parity (mathematics), 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. Th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Moore Bound
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] |
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] |
Petersen Graph
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three- edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by . Kempe observed that its vertices can represent the ten lines of the Desargues configuration, and its edges represent pairs of lines that do not meet at one of the ten points of the configuration. Donald Knuth states that the Petersen graph is "a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general." The Petersen graph also makes an appearance in tropical geometry. The cone over the Petersen graph is naturally ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
