Graph isomorphismIn graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if and are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as . In the case when the bijection is a mapping of a graph onto itself, i.
Twin primeA 'twin prime is a prime number that is either 2 less or 2 more than another prime number—for example, either member of the twin prime pair or In other words, a twin prime is a prime that has a prime gap of two. Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin' or prime pair. Twin primes become increasingly rare as one examines larger ranges, in keeping with the general tendency of gaps between adjacent primes to become larger as the numbers themselves get larger.
Regular icosahedronIn geometry, a regular icosahedron (ˌaɪkɒsəˈhiːdrən,-kə-,-koʊ- or aɪˌkɒsəˈhiːdrən) is a convex polyhedron with 20 faces, 30 edges and 12 vertices. It is one of the five Platonic solids, and the one with the most faces. It has five equilateral triangular faces meeting at each vertex. It is represented by its Schläfli symbol {3,5}, or sometimes by its vertex figure as 3.3.3.3.3 or 35. It is the dual of the regular dodecahedron, which is represented by {5,3}, having three pentagonal faces around each vertex.
Chordal graphIn the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.
Planarity testingIn graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal.
Primitive root modulo nIn modular arithmetic, a number g is a primitive root modulo n if every number a coprime to n is congruent to a power of g modulo n. That is, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gk ≡ a (mod n). Such a value k is called the index or discrete logarithm of a to the base g modulo n. So g is a primitive root modulo n if and only if g is a generator of the multiplicative group of integers modulo n.
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.
Formula for primesIn number theory, a formula for primes is a formula generating the prime numbers, exactly and without exception. No such formula which is efficiently computable is known. A number of constraints are known, showing what such a "formula" can and cannot be. A simple formula is for positive integer , where is the floor function, which rounds down to the nearest integer. By Wilson's theorem, is prime if and only if . Thus, when is prime, the first factor in the product becomes one, and the formula produces the prime number .
Bipartite graphIn the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. The two sets and may be thought of as a coloring of the graph with two colors: if one colors all nodes in blue, and all nodes in red, each edge has endpoints of differing colors, as is required in the graph coloring problem.
Proof by contradictionIn logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid. More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved.
