|
Zero-symmetric Graph
In the mathematics, mathematical field of graph theory, a zero-symmetric graph is a connected graph in which each vertex has exactly three incident edges and, for each two vertices, there is a unique graph automorphism, symmetry taking one vertex to the other. Such a graph is a vertex-transitive graph but cannot be an edge-transitive graph: the number of symmetries equals the number of vertices, too few to take every edge to every other edge. The name for this class of graphs was coined by R. M. Foster in a 1966 letter to Harold Scott MacDonald Coxeter, H. S. M. Coxeter. In the context of group theory, zero-symmetric graphs are also called graphical regular representations of their symmetry groups.. Examples The smallest zero-symmetric graph is a nonplanar graph with 18 vertices. Its LCF notation is [5,−5]9. Among planar graphs, the truncated cuboctahedral graph, truncated cuboctahedral and truncated icosidodecahedral graphs are also zero-symmetric. These examples are al ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Truncated Cuboctahedron
In geometry, the truncated cuboctahedron is an Archimedean solid, named by Kepler as a truncation of a cuboctahedron. It has 12 square faces, 8 regular hexagonal faces, 6 regular octagonal faces, 48 vertices, and 72 edges. Since each of its faces has point symmetry (equivalently, 180° rotational symmetry), the truncated cuboctahedron is a 9-zonohedron. The truncated cuboctahedron can tessellate with the octagonal prism. Names There is a nonconvex uniform polyhedron with a similar name: the nonconvex great rhombicuboctahedron. Cartesian coordinates The Cartesian coordinates for the vertices of a truncated cuboctahedron having edge length 2 and centered at the origin are all the permutations of: :(±1, ±(1 + ), ±(1 + 2)). Area and volume The area ''A'' and the volume ''V'' of the truncated cuboctahedron of edge length ''a'' are: :\begin A &= 12\left(2+\sqrt+\sqrt\right) a^2 &&\approx 61.755\,1724~a^2, \\ V &= \left(22+14\sqrt\right) a^3 &&\approx 41. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Truncated Cuboctahedral Graph
In geometry, the truncated cuboctahedron is an Archimedean solid, named by Kepler as a truncation of a cuboctahedron. It has 12 square faces, 8 regular hexagonal faces, 6 regular octagonal faces, 48 vertices, and 72 edges. Since each of its faces has point symmetry (equivalently, 180° rotational symmetry), the truncated cuboctahedron is a 9-zonohedron. The truncated cuboctahedron can tessellate with the octagonal prism. Names There is a nonconvex uniform polyhedron with a similar name: the nonconvex great rhombicuboctahedron. Cartesian coordinates The Cartesian coordinates for the vertices of a truncated cuboctahedron having edge length 2 and centered at the origin are all the permutations of: :(±1, ±(1 + ), ±(1 + 2)). Area and volume The area ''A'' and the volume ''V'' of the truncated cuboctahedron of edge length ''a'' are: :\begin A &= 12\left(2+\sqrt+\sqrt\right) a^2 &&\approx 61.755\,1724~a^2, \\ V &= \left(22+14\sqrt\right) a^3 &&\approx 41.798\,98 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algebraic Graph Theory
Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph theory, involving the use of linear algebra, the use of group theory, and the study of graph invariants. Branches of algebraic graph theory Using linear algebra The first branch of algebraic graph theory involves the study of graphs in connection with linear algebra. Especially, it studies the spectrum of the adjacency matrix, or the Laplacian matrix of a graph (this part of algebraic graph theory is also called spectral graph theory). For the Petersen graph, for example, the spectrum of the adjacency matrix is (−2, −2, −2, −2, 1, 1, 1, 1, 1, 3). Several theorems relate properties of the spectrum to other graph properties. As a simple example, a connected graph with diameter ''D'' w ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Semi-symmetric Graph
In the mathematical field of graph theory, a semi-symmetric graph is an undirected graph that is edge-transitive and regular, but not vertex-transitive. In other words, a graph is semi-symmetric if each vertex has the same number of incident edges, and there is a symmetry taking any of the graph's edges to any other of its edges, but there is some pair of vertices such that no symmetry maps the first into the second. Properties A semi-symmetric graph must be bipartite, and its automorphism group must act transitively on each of the two vertex sets of the bipartition (in fact, regularity is not required for this property to hold). For instance, in the diagram of the Folkman graph shown here, green vertices can not be mapped to red ones by any automorphism, but every two vertices of the same color are symmetric with each other. History Semi-symmetric graphs were first studied E. Dauber, a student of F. Harary, in a paper, no longer available, titled "On line- but not point-sym ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lovász Conjecture
In graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says: : Every finite connected vertex-transitive graph contains a Hamiltonian path. Originally László Lovász stated the problem in the opposite way, but this version became standard. In 1996, László Babai published a conjecture sharply contradicting this conjecture, but both conjectures remain widely open. It is not even known if a single counterexample would necessarily lead to a series of counterexamples. Historical remarks The problem of finding Hamiltonian paths in highly symmetric graphs is quite old. As Donald Knuth describes it in volume 4 of ''The Art of Computer Programming'', the problem originated in British campanology (bell-ringing). Such Hamiltonian paths and cycles are also closely connected to Gray codes. In each case the constructions are explicit. Variants of the Lovász conjecture Hamiltonian cycle Another version of Lovász conjecture states that : ... [...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] |
Combinatorial Enumeration
Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets ''S''''i'' indexed by the natural numbers, enumerative combinatorics seeks to describe a ''counting function'' which counts the number of objects in ''S''''n'' for each ''n''. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions. The simplest such functions are ''closed formulas'', which can be expressed as a composition of elementary functions such as factorials, powers, and so on. For instance, as shown below, the number of different possible orderings of a deck of ''n'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cayley Graph
In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem (named after Arthur Cayley), and uses a specified set of generators for the group. It is a central tool in combinatorial and geometric group theory. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing families of expander graphs. Definition Let G be a group and S be a generating set of G. The Cayley graph \Gamma = \Gamma(G,S) is an edge-colored directed graph constructed as follows: In his Collected Mathematical Papers 10: 403–405. * Each element g of G is assigned a vertex: the vertex set of \Gamma is identified with G. * Each element s of S is assigned a color c_s. * For every g \in G and s \in S, there is a directed edge of color c_s from the vertex corresponding to g to the one corresponding to gs. Not ... [...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] |
Truncated Icosidodecahedral Graph
In geometry, a truncated icosidodecahedron, rhombitruncated icosidodecahedron,Wenninger Model Number 16 great rhombicosidodecahedron,Williams (Section 3-9, p. 94)Cromwell (p. 82) omnitruncated dodecahedron or omnitruncated icosahedronNorman Woodason Johnson, "The Theory of Uniform Polytopes and Honeycombs", 1966 is an Archimedean solid, one of thirteen convex, isogonal, non-prismatic solids constructed by two or more types of regular polygon faces. It has 62 faces: 30 squares, 20 regular hexagons, and 12 regular decagons. It has the most edges and vertices of all Platonic and Archimedean solids, though the snub dodecahedron has more faces. Of all vertex-transitive polyhedra, it occupies the largest percentage (89.80%) of the volume of a sphere in which it is inscribed, very narrowly beating the snub dodecahedron (89.63%) and small rhombicosidodecahedron (89.23%), and less narrowly beating the truncated icosahedron (86.74%); it also has by far the greatest volume (206.8 cubic uni ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Planar Graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection. Plane graphs can be encoded by combinatorial maps or rotation systems. An equivalence class of topologically equivalent drawings on the sphere, usually with additional assumptions such as the absence of isthmuses, is called a pl ... [...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] |
