Graph bandwidthIn graph theory, the graph bandwidth problem is to label the n vertices v_i of a graph G with distinct integers f(v_i) so that the quantity is minimized (E is the edge set of G). The problem may be visualized as placing the vertices of a graph at distinct integer points along the x-axis so that the length of the longest edge is minimized. Such placement is called linear graph arrangement, linear graph layout or linear graph placement. The weighted graph bandwidth problem is a generalization wherein the edges are assigned weights w_ij and the cost function to be minimized is .
Chordal bipartite graphIn the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows. Chordal bipartite graphs have various characterizations in terms of perfect elimination orderings, hypergraphs and matrices.
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.
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 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.
5-polytopeIn geometry, a five-dimensional polytope (or 5-polytope) is a polytope in five-dimensional space, bounded by (4-polytope) facets, pairs of which share a polyhedral cell. A 5-polytope is a closed five-dimensional figure with vertices, edges, faces, and cells, and 4-faces. A vertex is a point where five or more edges meet. An edge is a line segment where four or more faces meet, and a face is a polygon where three or more cells meet. A cell is a polyhedron, and a 4-face is a 4-polytope.
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.
Well-covered graphIn graph theory, a well-covered graph is an undirected graph in which every minimal vertex cover has the same size as every other minimal vertex cover. Equivalently, these are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970. The well-covered graphs include all complete graphs, balanced complete bipartite graphs, and the rook's graphs whose vertices represent squares of a chessboard and edges represent moves of a chess rook.
Wagner's theoremIn graph theory, Wagner's theorem is a mathematical forbidden graph characterization of planar graphs, named after Klaus Wagner, stating that a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 (the utility graph, a complete bipartite graph on six vertices). This was one of the earliest results in the theory of graph minors and can be seen as a forerunner of the Robertson–Seymour theorem.
