|
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. The cluster graphs are the graphs for which adjacency is an |
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 a maximum clique that are hard on more general graph classes. Special types of cograph include complete graphs, complete bipartite graphs, cluster graphs, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Transactions Of The American Mathematical Society
The ''Transactions of the American Mathematical Society'' is a monthly peer-reviewed scientific journal of pure and applied mathematics published by the American Mathematical Society. It was established in 1900. As a requirement, all articles must be more than 15 printed pages. Its ISSN number is 0002-9947. See also * ''Bulletin of the American Mathematical Society'' * ''Journal of the American Mathematical Society'' * '' Memoirs of the American Mathematical Society'' * '' Notices of the American Mathematical Society'' * ''Proceedings of the American Mathematical Society'' References External links * ''Transactions of the American Mathematical Society''on JSTOR JSTOR ( ; short for ''Journal Storage'') is a digital library of academic journals, books, and primary sources founded in 1994. Originally containing digitized back issues of academic journals, it now encompasses books and other primary source ... American Mathematical Society academic journals Mathematics jo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Countably Infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements. In more technical terms, assuming the axiom of countable choice, a set is ''countable'' if its cardinality (the number of elements of the set) is not greater than that of the natural numbers. A countable set that is not finite is said to be countably infinite. The concept is attributed to Georg Cantor, who proved the existence of uncountable sets, that is, sets that are not countable; for example the set of the real numbers. A note on terminology Although the terms "countable" and "countably infinite" as defin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Journal Of Combinatorial Theory
The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applications of combinatorics. ''Series B'' is concerned primarily with graph and matroid theory. The two series are two of the leading journals in the field and are widely known as ''JCTA'' and ''JCTB''. The journal was founded in 1966 by Frank Harary and Gian-Carlo Rota.They are acknowledged on the journals' title pages and Web sites. SeEditorial board of JCTA Originally there was only one journal, which was split into two parts in 1971 as the field grew rapidly. In 2020, most of the editorial board of ''JCTA'' resigned to form a new, |
Graph Automorphism
In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge– vertex connectivity. Formally, an automorphism of a graph is a permutation of the vertex set , such that the pair of vertices form an edge if and only if the pair also form an edge. That is, it is a graph isomorphism from to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs. The composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Frucht's theorem, all groups can be represented as the automorphism group of a connected graph – indeed, of a cubic graph. Computational complexity Constructing the automorphism group of a graph, in the form of a list of generators, is polynomial-time equivalent to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Induced Subgraph
In 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\subseteq 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 any two vertices in ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Isomorphism
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) 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, often denoted by G\simeq H. In the case when the isomorphism is a mapping of a graph onto itself, i.e., when ''G'' and ''H'' are one and the same graph, the isomorphism is called an automorphism of ''G''. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs. The question of whether graph isomorphism can be dete ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Homogeneous Graph
In mathematics, a ''k''-ultrahomogeneous graph is a graph in which every isomorphism between two of its induced subgraphs of at most ''k'' vertices can be extended to an automorphism of the whole graph. A ''k''-homogeneous graph obeys a weakened version of the same property in which every isomorphism between two induced subgraphs implies the existence of an automorphism of the whole graph that maps one subgraph to the other (but does not necessarily extend the given isomorphism). A homogeneous graph is a graph that is ''k''-homogeneous for every ''k'', or equivalently ''k''-ultrahomogeneous for every ''k'', and thus, every homogeneous graph is also ultrahomogeneous. It is a special case of a homogenous model. Classification The only finite homogeneous graphs are the cluster graphs ''mK''''n'' formed from the disjoint unions of isomorphic complete graphs, the Turán graphs formed as the complement graphs of ''mK''''n'', the 3 × 3 rook's graph, and the 5- cycle. ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Diamond-free Graph
In the mathematical field of graph theory, the diamond graph is a planar, undirected graph with 4 vertices and 5 edges. It consists of a complete graph minus one edge. The diamond graph has radius 1, diameter 2, girth 3, chromatic number 3 and chromatic index 3. It is also a 2- vertex-connected and a 2- edge-connected, graceful, Hamiltonian graph. Diamond-free graphs and forbidden minor A graph is diamond-free if it has no diamond as an induced subgraph. The triangle-free graphs are diamond-free graphs, since every diamond contains a triangle. The diamond-free graphs are locally clustered: that is, they are the graphs in which every neighborhood is a cluster graph. Alternatively, a graph is diamond-free if and only if every pair of maximal cliques in the graph shares at most one vertex. The family of graphs in which each connected component is a cactus graph is downwardly closed under graph minor operations. This graph family may be characterized ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Neighborhood (graph Theory)
In graph theory, an adjacent vertex of a vertex (graph theory), vertex in a Graph (discrete mathematics), graph is a vertex that is connected to by an edge (graph theory), edge. The neighbourhood of a vertex in a graph is the subgraph of induced subgraph, induced by all vertices adjacent to , i.e., the graph composed of the vertices adjacent to and all edges connecting vertices adjacent to . The neighbourhood is often denoted or (when the graph is unambiguous) . The same neighbourhood notation may also be used to refer to sets of adjacent vertices rather than the corresponding induced subgraphs. The neighbourhood described above does not include itself, and is more specifically the open neighbourhood of ; it is also possible to define a neighbourhood in which itself is included, called the closed neighbourhood and denoted by . When stated without any qualification, a neighbourhood is assumed to be open. Neighbourhoods may be used to represent graphs in computer algori ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turán Graph
The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where q and s are the quotient and remainder of dividing n by r (so n = qr + s), the graph is of the form K_, and the number of edges is : \left(1 - \frac\right)\frac + . For r\le7, this edge count can be more succinctly stated as \left\lfloor\left(1-\frac1r\right)\frac2\right\rfloor. The graph has s subsets of size q+ 1 , and r - s subsets of size q; each vertex has degree n-q-1 or n-q. It is a regular graph if n is divisible by r (i.e. when s=0). Turán's theorem Turán graphs are named after Pál Turán, who used them to prove Turán's theorem, an important result in extremal graph theory. By the pigeonhole principle, every set of ''r'' + 1 vertices in the Turán graph includes two vertices in the same part ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
