|
Hoffman Graph
In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman. Published in 1963, it is cospectral to the hypercube graph Q4. The Hoffman graph has many common properties with the hypercube Q4—both are Hamiltonian and have chromatic number 2, chromatic index 4, girth 4 and diameter 4. It is also a 4- vertex-connected graph and a 4- edge-connected graph. However, it is not distance-regular. It has book thickness 3 and queue number 2.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 Algebraic properties The Hoffman graph is not a vertex-transitive graph and its full automorphism group is a group of order 48 isomorphic to the direct product of the symmetric group S4 and the cyclic group Z/2Z. The characteristic polynomial of the Hoffman graph is equal to :(x-4) (x-2)^4 x^6 (x+2)^4 (x+4) making it an integral graph—a graph whose spectrum consists e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hoffman Graph
In the mathematical field of graph theory, the Hoffman graph is a 4-regular graph with 16 vertices and 32 edges discovered by Alan Hoffman. Published in 1963, it is cospectral to the hypercube graph Q4. The Hoffman graph has many common properties with the hypercube Q4—both are Hamiltonian and have chromatic number 2, chromatic index 4, girth 4 and diameter 4. It is also a 4- vertex-connected graph and a 4- edge-connected graph. However, it is not distance-regular. It has book thickness 3 and queue number 2.Jessica Wolz, ''Engineering Linear Layouts with SAT''. Master Thesis, University of Tübingen, 2018 Algebraic properties The Hoffman graph is not a vertex-transitive graph and its full automorphism group is a group of order 48 isomorphic to the direct product of the symmetric group S4 and the cyclic group Z/2Z. The characteristic polynomial of the Hoffman graph is equal to :(x-4) (x-2)^4 x^6 (x+2)^4 (x+4) making it an integral graph—a graph whose spectrum consists e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-edge-connected Graph
In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration of -edge-connected graphs was studied by Camille Jordan in 1869. Formal definition Let G = (V, E) be an arbitrary graph. If subgraph G' = (V, E \setminus X) is connected for all X \subseteq E where , X, < k, then ''G'' is ''k''-edge-connected. The edge connectivity of is the maximum value ''k'' such that ''G'' is ''k''-edge-connected. The smallest set ''X'' whose removal disconnects ''G'' is a minimum cut in ''G''. The edge connectivity version of Menger's theorem provides an alternative and equivalent characterization, in terms o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spectral Graph Theory
In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix. The adjacency matrix of a simple undirected graph is a real symmetric matrix and is therefore orthogonally diagonalizable; its eigenvalues are real algebraic integers. While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one. Spectral graph theory is also concerned with graph parameters that are defined via multiplicities of eigenvalues of matrices associated to the graph, such as the Colin de Verdière number. Cospectral graphs Two graphs are called cospectral or isospectral if the adjacency matrices of the graphs are isospectral, that is, if the adjacency matrices have equal multisets of eigenvalues. Cospectral graphs need not be isomorphic, but isomorphic gr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Integral Graph
In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjacency matrix are integers. The notion was introduced in 1974 by Frank Harary and Allen Schwenk. Examples *The complete graph ''Kn'' is integral for all ''n''. *The only cycle graphs that are integral are C_3, C_4, and C_6. *If a graph is integral, then so is its complement graph; for instance, the complements of complete graphs, edgeless graphs, are integral. If two graphs are integral, then so is their Cartesian product and strong product; for instance, the Cartesian products of two complete graphs, the rook's graphs, are integral. Similarly, the hypercube graphs, as Cartesian products of any number of complete graphs K_2, are integral. *The line graph of an integral graph is again integral. For instance, as the line graph of K_4, the o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Characteristic Polynomial
In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix among its coefficients. The characteristic polynomial of an endomorphism of a finite-dimensional vector space is the characteristic polynomial of the matrix of that endomorphism over any base (that is, the characteristic polynomial does not depend on the choice of a basis). The characteristic equation, also known as the determinantal equation, is the equation obtained by equating the characteristic polynomial to zero. In spectral graph theory, the characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. Motivation In linear algebra, eigenvalues and eigenvectors play a fundamental role, since, given a linear transformation, an eigenvector is a vector whose direction is not changed by the transformation, and the correspondin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cyclic Group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative binary operation, and it contains an element ''g'' such that every other element of the group may be obtained by repeatedly applying the group operation to ''g'' or its inverse. Each element can be written as an integer power of ''g'' in multiplicative notation, or as an integer multiple of ''g'' in additive notation. This element ''g'' is called a '' generator'' of the group. Every infinite cyclic group is isomorphic to the additive group of Z, the integers. Every finite cyclic group of order ''n'' is isomorphic to the additive group of Z/''n''Z, the integers modulo ''n''. Every cyclic group is an abelian group (meaning that its group operation is commutative), and every finitely generated abelian group ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symmetric Group
In abstract algebra, the symmetric group defined over any set is the group whose elements are all the bijections from the set to itself, and whose group operation is the composition of functions. In particular, the finite symmetric group \mathrm_n defined over a finite set of n symbols consists of the permutations that can be performed on the n symbols. Since there are n! (n factorial) such permutation operations, the order (number of elements) of the symmetric group \mathrm_n is n!. Although symmetric groups can be defined on infinite sets, this article focuses on the finite symmetric groups: their applications, their elements, their conjugacy classes, a finite presentation, their subgroups, their automorphism groups, and their representation theory. For the remainder of this article, "symmetric group" will mean a symmetric group on a finite set. The symmetric group is important to diverse areas of mathematics such as Galois theory, invariant theory, the repres ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Direct Product Of Groups
In mathematics, specifically in group theory, the direct product is an operation that takes two groups and and constructs a new group, usually denoted . This operation is the group-theoretic analogue of the Cartesian product of sets and is one of several important notions of direct product in mathematics. In the context of abelian groups, the direct product is sometimes referred to as the direct sum, and is denoted G \oplus H. Direct sums play an important role in the classification of abelian groups: according to the fundamental theorem of finite abelian groups, every finite abelian group can be expressed as the direct sum of cyclic groups. Definition Given groups (with operation ) and (with operation ), the direct product is defined as follows: The resulting algebraic object satisfies the axioms for a group. Specifically: ;Associativity: The binary operation on is associative. ;Identity: The direct product has an identity element, namely , where is the identity e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vertex-transitive Graph
In the mathematical field of graph theory, a vertex-transitive graph is a graph in which, given any two vertices and of , there is some automorphism :f : G \to G\ such that :f(v_1) = v_2.\ In other words, a graph is vertex-transitive if its automorphism group acts transitively on its vertices.. A graph is vertex-transitive if and only if its graph complement is, since the group actions are identical. Every symmetric graph without isolated vertices is vertex-transitive, and every vertex-transitive graph is regular. However, not all vertex-transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex-transitive (for example, the Frucht graph and Tietze's graph). Finite examples Finite vertex-transitive graphs include the symmetric graphs (such as the Petersen graph, the Heawood graph and the vertices and edges of the Platonic solids). The finite Cayley graphs (such as cube-connected cycles) are also ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Queue Number
In the mathematical field of graph theory, the queue number of a graph is a graph invariant defined analogously to stack number (book thickness) using first-in first-out (queue) orderings in place of last-in first-out (stack) orderings. Definition A queue layout of a given graph is defined by a total ordering of the vertices of the graph together with a partition of the edges into a number of "queues". The set of edges in each queue is required to avoid edges that are properly nested: if and are two edges in the same queue, then it should not be possible to have in the vertex ordering. The queue number of a graph is the minimum number of queues in a queue layout.. Equivalently, from a queue layout, one could process the edges in a single queue using a queue data structure, by considering the vertices in their given ordering, and when reaching a vertex, dequeueing all edges for which it is the second endpoint followed by enqueueing all edges for which it is the first ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Book Thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings into a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the ''spine'', and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number. Every graph with vertices has book thickness at most \lceil n/2\rceil, and this formula gives the exact book thickness for complete graphs. The graphs with book thickness one are the outerplanar graphs. The graphs with book thickness at most two are the subhamiltonian graphs, which are always planar; more generally, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distance-regular Graph
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and . Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. Intersection arrays It turns out that a graph G of diameter d is distance-regular if and only if there is an array of integers \ such that for all 1 \leq j \leq d , b_j gives the number of neighbours of u at distance j+1 from v and c_j gives the number of neighbours of u at distance j - 1 from v for any pair of vertices u and v at distance j on G . The array of integers characterizing a distance-regular graph is known as its intersection array. Cos ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
