Independent set (graph theory)In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening.
Graph operationsIn the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations. Unary operations create a new graph from a single initial graph. Elementary operations or editing operations, which are also known as graph edit operations, create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc.
Perfect graphIn 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. The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families.
Wagner graphIn the mathematical field of graph theory, the Wagner graph is a 3-regular graph with 8 vertices and 12 edges. It is the 8-vertex Möbius ladder graph. As a Möbius ladder, the Wagner graph is nonplanar but has crossing number one, making it an apex graph. It can be embedded without crossings on a torus or projective plane, so it is also a toroidal graph. It has girth 4, diameter 2, radius 2, chromatic number 3, chromatic index 3 and is both 3-vertex-connected and 3-edge-connected.
Uniform 10-polytopeIn ten-dimensional geometry, a 10-polytope is a 10-dimensional polytope whose boundary consists of 9-polytope facets, exactly two such facets meeting at each 8-polytope ridge. A uniform 10-polytope is one which is vertex-transitive, and constructed from uniform facets. Regular 10-polytopes can be represented by the Schläfli symbol {p,q,r,s,t,u,v,w,x}, with x {p,q,r,s,t,u,v,w} 9-polytope facets around each peak.
Uniform 9-polytopeIn nine-dimensional geometry, a nine-dimensional polytope or 9-polytope is a polytope contained by 8-polytope facets. Each 7-polytope ridge being shared by exactly two 8-polytope facets. A uniform 9-polytope is one which is vertex-transitive, and constructed from uniform 8-polytope facets. Regular 9-polytopes can be represented by the Schläfli symbol {p,q,r,s,t,u,v,w}, with w {p,q,r,s,t,u,v} 8-polytope facets around each peak.
Uniform 8-polytopeIn eight-dimensional geometry, an eight-dimensional polytope or 8-polytope is a polytope contained by 7-polytope facets. Each 6-polytope ridge being shared by exactly two 7-polytope facets. A uniform 8-polytope is one which is vertex-transitive, and constructed from uniform 7-polytope facets. Regular 8-polytopes can be represented by the Schläfli symbol {p,q,r,s,t,u,v}, with v {p,q,r,s,t,u} 7-polytope facets around each peak.
FacetingStella octangula as a faceting of the cube In geometry, faceting (also spelled facetting) is the process of removing parts of a polygon, polyhedron or polytope, without creating any new vertices. New edges of a faceted polyhedron may be created along face diagonals or internal space diagonals. A faceted polyhedron will have two faces on each edge and creates new polyhedra or compounds of polyhedra. Faceting is the reciprocal or dual process to stellation. For every stellation of some convex polytope, there exists a dual faceting of the dual polytope.
Hypohamiltonian graphIn 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. Hypohamiltonian graphs were first studied by . cites and as additional early papers on the subject; another early work is by . sums up much of the research in this area with the following sentence: “The articles dealing with those graphs ...
CoefficientIn mathematics, a coefficient is a multiplicative factor involved in some term of a polynomial, a series, or an expression. It may be a number (dimensionless), in which case it is known as a numerical factor. It may also be a constant with units of measurement, in which it is known as a constant multiplier. In general, coefficients may be any expression (including variables such as a, b and c). When the combination of variables and constants is not necessarily involved in a product, it may be called a parameter.
Uniform 7-polytopeIn seven-dimensional geometry, a 7-polytope is a polytope contained by 6-polytope facets. Each 5-polytope ridge being shared by exactly two 6-polytope facets. A uniform 7-polytope is one whose symmetry group is transitive on vertices and whose facets are uniform 6-polytopes. Regular 7-polytopes are represented by the Schläfli symbol {p,q,r,s,t,u} with u {p,q,r,s,t} 6-polytopes facets around each 4-face. There are exactly three such convex regular 7-polytopes: {3,3,3,3,3,3} - 7-simplex {4,3,3,3,3,3} - 7-cube {3,3,3,3,3,4} - 7-orthoplex There are no nonconvex regular 7-polytopes.
