|
Trivially Perfect Graph
In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs. Equivalent characterizations Trivially perfect graphs have several other equivalent characterizations: *They are the comparability graphs of order-theoretic trees. That is, let be a partial order such that for each , the set is well-ordered by the relation , and also possesses a minimum element . Then the comparability graph of is trivially perfect, and every trivially perfect graph can be formed in this way. *They are the graphs that do not have a path graph or a cycle graph as induced su ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Trivially Perfect Graph
In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by ; Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs. Equivalent characterizations Trivially perfect graphs have several other equivalent characterizations: *They are the comparability graphs of order-theoretic trees. That is, let be a partial order such that for each , the set is well-ordered by the relation , and also possesses a minimum element . Then the comparability graph of is trivially perfect, and every trivially perfect graph can be formed in this way. *They are the graphs that do not have a path graph or a cycle graph as induced su ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cograph
In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes ''K''1 and is closed under complementation and disjoint union. Cographs have been discovered independently by several authors since the 1970s; early references include , , , and . They have also been called D*-graphs, hereditary Dacey graphs (after the related work of James C. Dacey Jr. on orthomodular lattices), and 2-parity graphs. They have a simple structural decomposition involving disjoint union and complement graph operations that can be represented concisely by a labeled tree, and used algorithmically to efficiently solve many problems such as finding the maximum clique that are hard on more general graph classes. Special cases of the cographs include the complete graphs, complete bipartite graphs, cluster g ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lexicographic Breadth-first Search
In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search. The lexicographic breadth-first search algorithm is based on the idea of partition refinement and was first developed by . A more detailed survey of the topic is presented by . It has been used as a subroutine in other graph algorithms including the recognition of chordal graphs, and optimal coloring of distance-hereditary graphs. Background The breadth-first search algorithm is commonly defined by the following process: *Initialize a queue of graph vertices, with the starting vertex of the graph as the queue's only element. *While the queue is non-empty, remove (dequeue) a vertex from the queue, and add to the queue (enqueue) all the other vertices that can be reached by an edge from that have not already been added in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally express ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Windmill Graph
In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. Properties It has vertices and edges, girth 3 (if ), radius 1 and diameter 2. It has vertex connectivity 1 because its central vertex is an articulation point; however, like the complete graphs from which it is formed, it is -edge-connected. It is trivially perfect and a block graph. Special cases By construction, the windmill graph is the friendship graph , the windmill graph is the star graph and the windmill graph is the butterfly graph. Labeling and colouring The windmill graph has chromatic number and chromatic index . Its chromatic polynomial can be deduced form the chromatic polynomial of the complete graph and is equal to :x\prod_^(x-i)^n. The windmill graph is proved not graceful Gracefulness, or being graceful, is the ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Threshold Graph
In graph theory, a threshold graph is a graph that can be constructed from a one-vertex graph by repeated applications of the following two operations: # Addition of a single isolated vertex to the graph. # Addition of a single dominating vertex to the graph, i.e. a single vertex that is connected to all other vertices. For example, the graph of the figure is a threshold graph. It can be constructed by beginning with a single-vertex graph (vertex 1), and then adding black vertices as isolated vertices and red vertices as dominating vertices, in the order in which they are numbered. Threshold graphs were first introduced by . A chapter on threshold graphs appears in , and the book is devoted to them. Alternative definitions An equivalent definition is the following: a graph is a threshold graph if there are a real number S and for each vertex v a real vertex weight w(v) such that for any two vertices v,u, uv is an edge if and only if w(u)+w(v)> S. Another equivalent definitio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ptolemaic Graph
In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs. Characterization A graph is Ptolemaic if and only if it obeys any of the following equivalent conditions: *The shortest path distances obey Ptolemy's inequality: for every four vertices , , , and , the inequality holds.. For instance, the gem graph (3-fan) in the illustration is not Ptolemaic, because in this graph , greater than . *For every two overlapping maximal cliques, the intersection of the two cliques is a separator that splits the differences of the two cliques.. In the illustration of the gem graph, this is not true: cliques and are not separated by their intersection, , because there is an edge that con ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Chromatic Number
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color. Vertex coloring is often used to introduce graph coloring problems, since other coloring problems can be transformed into a vertex coloring instance. For example, an edge coloring of a graph is just a vertex coloring of its line graph, and a face coloring of a plane graph is just a vertex coloring of its dual. However, non-vertex coloring problems are often stated and studied as-is. This ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique Number
In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied. Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory by , the term ''clique'' comes from , who used complete subgraphs in social networks to model cliques of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique Cover Number
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 computat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stack-sortable Permutation
In mathematics and computer science, a stack-sortable permutation (also called a tree permutation) is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees. Sorting with a stack The problem of sorting an input sequence using a stack was first posed by , who gave the following linear time algorithm (closely related to algorithms for the later all nearest smaller values problem): *Initialize an empty stack *For each input value ''x'': **While the stack is nonempty and ''x'' is larger than the top item on the stack, pop the stack to the output **Push ''x'' onto the stack *While the stack is nonempty, pop it to the output K ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
