|
Halved Cube Graph
In graph theory, the halved cube graph or half cube graph of dimension is the graph of the demihypercube, formed by connecting pairs of vertices at distance exactly two from each other in the hypercube graph. That is, it is the half-square of the hypercube. This connectivity pattern produces two isomorphic graphs, disconnected from each other, each of which is the halved cube graph. Equivalent constructions The construction of the halved cube graph can be reformulated in terms of binary numbers. The vertices of a hypercube may be labeled by binary numbers in such a way that two vertices are adjacent exactly when they differ in a single bit. The demicube may be constructed from the hypercube as the convex hull of the subset of binary numbers with an even number of nonzero bits (the evil numbers), and its edges connect pairs of numbers whose Hamming distance is exactly two. It is also possible to construct the halved cube graph from a lower-dimensional hypercube graph, without ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Power
In graph theory, a branch of mathematics, the th power of an undirected graph is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in is at most . Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: is called the ''square'' of , is called the ''cube'' of , etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph. Properties If a graph has diameter , then its -th power is the complete graph. If a graph family has bounded clique-width, then so do its -th powers for any fixed . Coloring Graph coloring on the square of a graph may be used to assign frequencies to the participants of wireless communication networks so that no two participants interfere with each other at any of their common neighbors, and to find graph drawings with high angular resolution. Both the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamiltonian Cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a 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. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete. 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 structure based on roots of unity with many similarities to the quaternions (also invented by Hami ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spanning Subgraph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B C D E F G H I K L M N O ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graphs And Combinatorics
''Graphs and Combinatorics'' (ISSN 0911-0119, abbreviated ''Graphs Combin.'') is a peer-reviewed academic journal in graph theory, combinatorics, and discrete geometry published by Springer Japan. Its editor-in-chief is Katsuhiro Ota of Keio University. The journal was first published in 1985. Its founding editor in chief was Hoon Heng Teh of Singapore, the president of the Southeast Asian Mathematics Society, and its managing editor was Jin Akiyama. Originally, it was subtitled "An Asian Journal". In most years since 1999, it has been ranked as a second-quartile journal in discrete mathematics and theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ... by SCImago Journal Rank.. References {{reflist Publications established in 1985 Combinatorics jo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance-regular Graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. Intersection arrays It turns out that a graph G of diameter d is distance-regular if and only if there is an array of integers \ such that for all 1 \leq j \leq d , b_j gives the number of neighbours of u at distance j+1 from v and c_j gives the number of neighbours of u at distance j - 1 from v for any pair of vertices u and v at distance j on G . The array of integers characterizing a distance-regular graph is known as its intersection array. Cos ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bipartite Half
In graph theory, the bipartite half or half-square of a bipartite graph is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, ) and in which there is an edge for each pair of vertices in that are at distance two from each other in . That is, in a more compact notation, the bipartite half is where the superscript 2 denotes the square of a graph and the square brackets denote an induced subgraph. Examples For instance, the bipartite half of the complete bipartite graph is the complete graph and the bipartite half of the hypercube graph is the halved cube graph. When is a distance-regular graph, its two bipartite halves are both distance-regular. For instance, the halved Foster graph is one of finitely many degree-6 distance-regular locally linear graphs. Representation and hardness Every graph is the bipartite half of another graph, formed by subdividing the edges of into two-edge paths. More generally, a representation of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
5-demicube
In five-dimensional geometry, a demipenteract or 5-demicube is a semiregular 5-polytope, constructed from a ''5-hypercube'' (penteract) with alternated vertices removed. It was discovered by Thorold Gosset. Since it was the only semiregular 5-polytope (made of more than one type of regular facets), he called it a 5-ic semi-regular. E. L. Elte identified it in 1912 as a semiregular polytope, labeling it as HM5 for a 5-dimensional ''half measure'' polytope. Coxeter named this polytope as 121 from its Coxeter diagram, which has branches of length 2, 1 and 1 with a ringed node on one of the short branches, and Schläfli symbol \left\ or . It exists in the k21 polytope family as 121 with the Gosset polytopes: 221, 321, and 421. The graph formed by the vertices and edges of the demipenteract is sometimes called the Clebsch graph, though that name sometimes refers to the folded cube graph of order five instead. Cartesian coordinates Cartesian coordinates for the vertices of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Uniform 5-polytope
In geometry, a uniform 5-polytope is a five-dimensional uniform polytope. By definition, a uniform 5-polytope is vertex-transitive and constructed from uniform 4-polytope Facet (geometry), facets. The complete set of convex uniform 5-polytopes has not been determined, but many can be made as Wythoff constructions from a small set of Coxeter groups, symmetry groups. These construction operations are represented by the permutations of rings of the Coxeter diagrams. History of discovery *Regular polytopes: (convex faces) **1852: Ludwig Schläfli proved in his manuscript ''Theorie der vielfachen Kontinuität'' that there are exactly 3 regular polytopes in 5 or more dimensions. *Convex semiregular polytopes: (Various definitions before Coxeter's uniform category) **1900: Thorold Gosset enumerated the list of nonprismatic semiregular convex polytopes with regular facets (convex regular 4-polytopes) in his publication ''On the Regular and Semi-Regular Figures in Space of n Dimension ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Folded Cube Graph
In graph theory, a folded cube graph is an undirected graph formed from a hypercube graph by adding to it a perfect matching that connects ''opposite'' pairs of hypercube vertices. Construction The folded cube graph of dimension ''k'' (containing 2''k'' − 1 vertices) may be formed by adding edges between opposite pairs of vertices in a hypercube graph of dimension ''k'' − 1. (In a hypercube with 2''n'' vertices, a pair of vertices are ''opposite'' if the shortest path between them has length ''n''.) It can, equivalently, be formed from a hypercube graph (also) of dimension ''k'', which has twice as many vertices, by identifying together (or contracting) every opposite pair of vertices. Properties A dimension-''k'' folded cube graph is a ''k''- regular with 2''k'' − 1 vertices and 2''k'' − 2''k'' edges. The chromatic number of the dimension-''k'' folded cube graph is two when ''k'' is even (that is, in this case, th ... [...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] |
16-cell
In geometry, the 16-cell is the regular convex 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol . It is one of the six regular convex 4-polytopes first described by the Swiss mathematician Ludwig Schläfli in the mid-19th century. It is also called C16, hexadecachoron, or hexdecahedroid .Matila Ghyka, ''The Geometry of Art and Life'' (1977), p.68 It is a part of an infinite family of polytopes, called cross-polytopes or ''orthoplexes'', and is analogous to the octahedron in three dimensions. It is Coxeter's \beta_4 polytope. Conway's name for a cross-polytope is orthoplex, for ''orthant complex''. The dual polytope is the tesseract (4-cube), which it can be combined with to form a compound figure. The 16-cell has 16 cells as the tesseract has 16 vertices. Geometry The 16-cell is the second in the sequence of 6 convex regular 4-polytopes (in order of size and complexity). Each of its 4 successor convex regular 4-polytopes can be constructed as ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
