Related Research Articles
In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the other. Such dual figures remain combinatorial or abstract polyhedra, but not all can also be constructed as geometric polyhedra. Starting with any given polyhedron, the dual of its dual is the original polyhedron.
In order theory, a Hasse diagram is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set one represents each element of as a vertex in the plane and draws a line segment or curve that goes upward from one vertex to another vertex whenever covers . These curves may cross each other but must not touch any vertices other than their endpoints. Such a diagram, with labeled vertices, uniquely determines its partial order.
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
In mathematics, and more specifically in graph theory, a polytree is a directed acyclic graph whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.
In mathematics, the Burr–Erdős conjecture was a problem concerning the Ramsey number of sparse graphs. The conjecture is named after Stefan Burr and Paul Erdős, and is one of many conjectures named after Erdős; it states that the Ramsey number of graphs in any sparse family of graphs should grow linearly in the number of vertices of the graph.
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. Dushnik & Miller (1941) first studied order dimension; for a more detailed treatment of this subject than provided here, see Trotter (1992).
In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in 1989.
In mathematics, a representation is a very general relationship that expresses similarities between mathematical objects or structures. Roughly speaking, a collection Y of mathematical objects may be said to represent another collection X of objects, provided that the properties and relationships existing among the representing objects yi conform, in some consistent way, to those existing among the corresponding represented objects xi. More specifically, given a set Π of properties and relations, a Π-representation of some structure X is a structure Y that is the image of X under a homomorphism that preserves Π. The label representation is sometimes also applied to the homomorphism itself.
In the mathematical field of graph theory, Fáry's theorem states that any simple, planar graph can be drawn without crossings so that its edges are straight line segments. That is, the ability to draw graph edges as curves instead of as straight line segments does not allow a larger class of graphs to be drawn. The theorem is named after István Fáry, although it was proved independently by Klaus Wagner, Fáry, and Sherman K. Stein.
In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.
In graph theory, the Möbius ladderMn, for even numbers n, is formed from an n-cycle by adding edges connecting opposite pairs of vertices in the cycle. It is a cubic, circulant graph, so-named because (with the exception of M6, Mn has exactly n/2 four-cycles which link together by their shared edges to form a topological Möbius strip. Möbius ladders were named and first studied by Guy and Harary .
In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.
In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.
In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.
In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.
In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.
In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.
In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs, but with a Fibonacci number of vertices. Fibonacci cubes were first explicitly defined in Hsu (1993) in the context of interconnection topologies for connecting parallel or distributed systems. They have also been applied in chemical graph theory.
In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.
Dominance drawing is a style of graph drawing of directed acyclic graphs that makes the reachability relations between vertices visually apparent. In dominance drawing, vertices are placed at distinct points of the Euclidean plane and a vertex v is reachable from another vertex u if and only if both Cartesian coordinates of v are greater than or equal to the coordinates of u. The edges of a dominance drawing may be drawn either as straight line segments, or, in some cases, as polygonal chains.
References
- ↑ Schnyder, W. (1989), "Planar graphs and poset dimension", Order , 5 (4): 323–343, doi:10.1007/BF00353652, S2CID 122785359 .
- ↑ Agnarsson, Geir; Felsner, Stefan; Trotter, William T. (1999), "The maximum number of edges in a graph of bounded dimension, with applications to ring theory", Discrete Mathematics , 201 (1–3): 5–19, doi: 10.1016/S0012-365X(98)00309-4 , MR 1687854 .
- ↑ Trotter, William T.; Wang, Ruidong (2014), "Incidence posets and cover graphs", Order , 31 (2): 279–287, arXiv: 1308.2471 , doi:10.1007/s11083-013-9301-9, S2CID 17560524 .
- ↑ Hoşten, Serkan; Morris, Walter D. Jr. (1999), "The order dimension of the complete graph", Discrete Mathematics , 201 (1–3): 133–139, doi:10.1016/S0012-365X(98)00315-X, MR 1687882 .
- ↑ Brightwell, Graham R.; Trotter, William T. (1994), "Incidence posets of trees in posets of large dimension", Order , 11 (2): 159–167, doi:10.1007/BF01108600, MR 1302404, S2CID 120777046 .