|
Johnson Graph
In mathematics, Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J(n,k) are the k-element subsets of an n-element set; two vertices are adjacent when the intersection of the two vertices (subsets) contains (k-1)-elements.. Both Johnson graphs and the closely related Johnson scheme are named after Selmer M. Johnson. Special cases *Both J(n,1) and J(n,n-1) are the complete graph . *J(4,2) is the octahedral graph. *J(5,2) is the complement of the Petersen graph, hence the line graph of . More generally, for all n, the Johnson graph J(n,2) is the line graph of and the complement of the Kneser graph K(n,2). Graph-theoretic properties * J(n,k) is isomorphic to J(n,n-k). * For all 0 \leq j \leq \operatorname(J(n,k)), any pair of vertices at distance j share k-j elements in common. * J(n,k) is Hamilton-connected, meaning that every pair of vertices forms the endpoints of a Hamiltonian path in the graph. In parti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Johnson Graph J(5,2)
Johnson may refer to: People and fictional characters *Johnson (surname), a common surname in English *Johnson (given name), a list of people * List of people with surname Johnson, including fictional characters *Johnson (composer) (1953–2011), Indian film score composer *Johnson (rapper) (born 1979), Danish rapper *Mr. Johnson (born 1966), Nigerian singer Places * Mount Johnson (other) Canada * Johnson, Ontario, township * Johnson (electoral district), provincial electoral district in Quebec * Johnson Point (British Columbia), a headland on the north side of the entrance to Belize Inlet United States * Johnson, Arizona * Johnson, Arkansas, a town * Johnson, Delaware * Johnson, Indiana, an unincorporated town * Johnson, Kentucky * Johnson, Minnesota * Johnson, Nebraska * Johnson, New York * Johnson, Ohio, an unincorporated community * Johnson, Oklahoma * Johnson, Utah * Johnson, Vermont, a town ** Johnson (village), Vermont * Johnson, Washington * Johnson, Wisconsin, a ... [...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] |
Subgroup
In group theory, a branch of mathematics, a subset of a group G is a subgroup of G if the members of that subset form a group with respect to the group operation in G. Formally, given a group (mathematics), group under a binary operation ∗, a subset of is called a subgroup of if also forms a group under the operation ∗. More precisely, is a subgroup of if the Restriction (mathematics), restriction of ∗ to is a group operation on . This is often denoted , read as " is a subgroup of ". The trivial subgroup of any group is the subgroup consisting of just the identity element. A proper subgroup of a group is a subgroup which is a subset, proper subset of (that is, ). This is often represented notationally by , read as " is a proper subgroup of ". Some authors also exclude the trivial group from being proper (that is, ). If is a subgroup of , then is sometimes called an overgroup of . The same definitions apply more generally when is an arbitrary se ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance-transitive Graph
In the mathematical field of graph theory, a distance-transitive graph is a graph such that, given any two vertices and at any distance , and any other two vertices and at the same distance, there is an automorphism of the graph that carries to and to . Distance-transitive graphs were first defined in 1971 by Norman L. Biggs and D. H. Smith. A distance-transitive graph is interesting partly because it has a large automorphism group. Some interesting finite groups are the automorphism groups of distance-transitive graphs, especially of those whose diameter is 2. Examples Some first examples of families of distance-transitive graphs include: * The Johnson graphs. * The Grassmann graphs. * The Hamming Graphs (including Hypercube graphs). * The folded cube graphs. * The square rook's graphs. * The Livingstone graph. Classification of cubic distance-transitive graphs After introducing them in 1971, Biggs Biggs may refer to: Arts and entertainment * B ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Rook's Graph
In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs. Rook's graphs are highly symmetric, having symmetries taking every vertex to every other vertex. In rook's graphs defined from square chessboards, more strongly, every two edges are symmetric, and every pair of vertices is symmetric to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Neighbourhood (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] |
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] |
Chromatic Number
In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring is a special case of graph labeling. 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 edges 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 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Eigenvalue
In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a constant factor \lambda when the linear transformation is applied to it: T\mathbf v=\lambda \mathbf v. The corresponding eigenvalue, characteristic value, or characteristic root is the multiplying factor \lambda (possibly a negative or complex number). Geometrically, vectors are multi-dimensional quantities with magnitude and direction, often pictured as arrows. A linear transformation rotates, stretches, or shears the vectors upon which it acts. A linear transformation's eigenvectors are those vectors that are only stretched or shrunk, with neither rotation nor shear. The corresponding eigenvalue is the factor by which an eigenvector is stretched or shrunk. If the eigenvalue is negative, the eigenvector's direction is reversed. Th ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clique Number
In 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 bioinformatics. Definitions ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hypersimplex
In polyhedral combinatorics, the hypersimplex \Delta_ is a convex polytope that generalizes the simplex. It is determined by two integers d and k, and is defined as the convex hull of the d-dimensional vector (mathematics), vectors whose coefficients consist of k ones and d-k zeros. Equivalently, \Delta_ can be obtained by slicing the d-dimensional unit hypercube [0,1]^d with the hyperplane of equation x_1+\cdots+x_d=k and, for this reason, it is a (d-1)-dimensional polytope when 0 Properties The number of vertices of is . The graph formed by the vertices and edges of the hypersimplex is the Johnson graph .Alternative constructions An alternative construction (for ) is to take the convex hull of all -dimensional -vectors that have either |
