|
Well-covered Graph
In 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. Known characterizations of the well-covered cubic graphs, well-covered claw-free graphs, and well-covered graphs of high girth allow these graphs to be recognized in polynomial time, but testing whether other kinds of graph are well-covered is a coNP-complete problem. Definitions A vertex cover in a graph is a set of vertices that touches every edge in the graph. A vertex cover is minimal, or irredundant, if removing any vertex from it would destroy the covering ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Well-covered Graph
In 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. Known characterizations of the well-covered cubic graphs, well-covered claw-free graphs, and well-covered graphs of high girth allow these graphs to be recognized in polynomial time, but testing whether other kinds of graph are well-covered is a coNP-complete problem. Definitions A vertex cover in a graph is a set of vertices that touches every edge in the graph. A vertex cover is minimal, or irredundant, if removing any vertex from it would destroy the covering ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Critical Graph
In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one. Variations A ''k-critical graph'' is a critical graph with chromatic number k. A graph G with chromatic number k is ''k-vertex-critical'' if each of its vertices is a critical element. Critical graphs are the ''minimal'' members in terms of chromatic number, which is a very important measure in graph theory. Some properties of a k-critical graph G with n vertices and m edges: * G has only one component. * G is finite (this is the de Bruijn–Erdős theorem). * The minimum degree \delta(G) obeys the inequality \delta(G)\ge k-1. That is, every vertex is adjacent to at least k-1 others. More strongly, G is (k-1)- edge-connected. * If ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Induced Subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) be any graph, and let S\subset V be any subset of vertices of . Then the induced subgraph G is the graph whose vertex set is S and whose edge set consists of all of the edges in E that have both endpoints in S . That is, for any two vertices u,v\in S , u and v are adjacent in G if and only if they are adjacent in G . The same definition works for undirected graphs, directed graphs, and even multigraphs. The induced subgraph G may also be called the subgraph induced in G by S , or (if context makes the choice of G unambiguous) the induced subgraph of S . Examples Important types of induced subgraphs include the following. *Induced paths are induced subgraphs that are paths. The shortest path between ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique Cover
In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum for which a clique cover exists is called the clique cover number of the given graph. Relation to coloring A clique cover of a graph may be seen as a graph coloring of the complement graph of , the graph on the same vertex set that has edges between non-adjacent vertices of . Like clique covers, graph colorings are partitions of the set of vertices, but into subsets with no adjacencies ( independent sets) rather than cliques. A subset of vertices is a clique in if and only if it is an independent set in the complement of , so a partition of the vertices of is a clique cover of if and only if it is a coloring of the complement of . Computational complexity The clique cover problem in computati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rooted Product Of Graphs
In mathematical graph theory, the rooted product of a graph ''G'' and a rooted graph ''H'' is defined as follows: take , ''V''(''G''), copies of ''H'', and for every vertex v_i of ''G'', identify v_i with the root node of the ''i''-th copy of ''H''. More formally, assuming that ''V''(''G'') = , ''V''(''H'') = and that the root node of ''H'' is h_1, define :G \circ H := (V, E) where :V = \left\ and :E = \left\ \cup \bigcup_^n \left\ If ''G'' is also rooted at ''g''1, one can view the product itself as rooted, at (''g''1, ''h''1). The rooted product is a subgraph of the cartesian product of the same two graphs. Applications The rooted product is especially relevant for trees, as the rooted product of two trees is another tree. For instance, Koh et al. (1980) used rooted products to find graceful numberings for a wide family of trees. If ''H'' is a two-vertex complete graph ''K''2, then for any graph ''G'', the rooted product of ''G'' and ''H'' has domination number exactly ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Simple Polygon
In geometry, a simple polygon is a polygon that does not Intersection (Euclidean geometry), intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed curve, closed path. If the sides intersect then the polygon is not simple. The qualifier "simple" is frequently omitted, with the above definition then being understood to define a polygon in general. The definition given above ensures the following properties: * A polygon encloses a region (mathematics), region (called its interior) which always has a measurable area. * The line segments that make up a polygon (called sides or edges) meet only at their endpoints, called vertices (singular: vertex) or less formally "corners". * Exactly two edges meet at each vertex. * The number of edges always equals the number of vertices. Two edges meeting at a corner are usually required to form an angle that is not straight ( ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chessboard
A chessboard is a used to play chess. It consists of 64 squares, 8 rows by 8 columns, on which the chess pieces are placed. It is square in shape and uses two colours of squares, one light and one dark, in a chequered pattern. During play, the board is oriented such that each player's near-right corner square is a light square. The columns of a chessboard are known as ', the rows are known as ', and the lines of adjoining same-coloured squares (each running from one edge of the board to an adjacent edge) are known as '. Each square of the board is named using algebraic, descriptive, or numeric chess notation; algebraic notation is the FIDE standard. In algebraic notation, using White's perspective, files are labeled ''a'' through ''h'' from left to right, and ranks are labeled ''1'' through ''8'' from bottom to top; each square is identified by the file and rank which it occupies. The a- through d-files comprise the , while the e- through h-files comprise the . History and evo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rook (chess)
The rook (; ♖, ♜) is a piece in the game of chess. It may move any number of squares horizontally or vertically without jumping, and it may an enemy piece on its path; additionally, it may participate in castling. Each player starts the game with two rooks, one in each corner on their own side of the board. Formerly, the rook (from Persian رخ ''rokh''/''rukh'', meaning "chariot") was alternatively called the tower, marquess, rector, and comes (count or earl). The term "castle" is considered to be informal, incorrect, or old-fashioned. Placement and movement The white rooks start on squares a1 and h1, while the black rooks start on a8 and h8. The rook moves horizontally or vertically, through any number of unoccupied squares (see diagram). The rook cannot jump over pieces. The rook may capture an enemy piece by moving to the square on which the enemy piece stands, removing it from play. The rook also participates with the king in a special move called castling, wherein i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Isolated Vertex
In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of vertices), while a directed graph consists of a set of vertices and a set of arcs (ordered pairs of vertices). In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another. From the point of view of graph theory, vertices are treated as featureless and indivisible objects, although they may have additional structure depending on the application from which the graph arises; for instance, a semantic network is a graph in which the vertices represent concepts or classes of objects. The two vertices forming an edge are said to be the endpoints of this edge, and the edge is said to be incident to the vertices. A vertex ''w'' is said to be ad ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Triangle-free Graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs. By Turán's theorem, the ''n''-vertex triangle-free graph with the maximum number of edges is a complete bipartite graph in which the numbers of vertices on each side of the bipartition are as equal as possible. Triangle finding problem The triangle finding problem is the problem of determining whether a graph is triangle-free or not. When the graph does contain a triangle, algorithms are often required to output three vertices which form a triangle in the graph. It is possible to test whether a graph with edges is triangle-free in time . Another approach is to find the trace of , where is the adjacency matrix of the graph. The trace is zero if and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Complement Graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there.. The complement is not the set complement of the graph; only the edges are complemented. Definition Let be a simple graph and let consist of all 2-element subsets of . Then is the complement of , where is the relative complement of in . For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element ordered pairs of in place of the set in the formula above. In terms of the adjacency matrix ''A'' of the graph, if ''Q'' is the adjacency matrix of the complete graph of the same number of vertices (i.e. all entries are unity ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cluster Graph
In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called -free graphs. They are the complement graphs of the complete multipartite graphsCluster graphs Information System on Graph Classes and their Inclusions, accessed 2016-06-26. and the 2-leaf powers. The cluster graphs are transitively closed, and every transitively closed undirected graph is a cluster graph. Related graph classes Every cluster graph is a |
