Hoffman graph

Last updated
Hoffman graph
Hoffman graph.svg
The Hoffman graph
Named after Alan Hoffman
Vertices 16
Edges 32
Radius 3
Diameter 4
Girth 4
Automorphisms 48 (Z/2Z × S4)
Chromatic number 2
Chromatic index 4
Book thickness 3
Queue number 2
Properties Hamiltonian [1]
Bipartite
Perfect
Eulerian
Table of graphs and parameters

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. [2] Published in 1963, it is cospectral to the hypercube graph Q4. [3] [4]

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure, space, and change.

Graph theory study of graphs, which are mathematical structures used to model pairwise relations between objects

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges, then called arrows, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Regular graph graph where each vertex has the same number of neighbors

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree k is called a k‑regular graph or regular graph of degree k. Also, from the handshaking lemma, a regular graph of odd degree will contain an even number of vertices.

Contents

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. [5]

In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

In graph theory, a connected graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and i = d(v, w).

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.

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v1 and v2 of G, there is some automorphism

Direct product of groups

In group theory, the direct product is an operation that takes two groups G and H and constructs a new group, usually denoted G × H. 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.

Symmetric group automorphism group of a set; the group of bijections on a set, whose group operation is function composition

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 Sn defined over a finite set of n symbols consists of the permutation operations that can be performed on the n symbols. Since there are n! possible permutation operations that can be performed on a tuple composed of n symbols, it follows that the number of elements of the symmetric group Sn is n!.

The characteristic polynomial of the Hoffman graph is equal to

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 as coefficients. The characteristic polynomial of an endomorphism of vector spaces of finite dimension is the characteristic polynomial of the matrix of the endomorphism over any base; it does not depend on the choice of a basis. The characteristic equation is the equation obtained by equating to zero the characteristic polynomial.

making it an integral graph—a graph whose spectrum consists entirely of integers. It is the same spectrum as the hypercube Q4.

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.

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.

Related Research Articles

Desargues graph highly symmetric graph with 20 vertices and 30 edges

In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Girard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial cube, and has been applied in chemical databases.

Butterfly graph

In the mathematical field of graph theory, the butterfly graph is a planar undirected graph with 5 vertices and 6 edges. It can be constructed by joining 2 copies of the cycle graph C3 with a common vertex and is therefore isomorphic to the friendship graph F2.

Coxeter graph

In the mathematical field of graph theory, the Coxeter graph is a 3-regular graph with 28 vertices and 42 edges. It is one of the 13 cubic distance-regular graphs are known. It is named after Harold Scott MacDonald Coxeter.

Pappus graph

In the mathematical field of graph theory, the Pappus graph is a bipartite 3-regular undirected graph with 18 vertices and 27 edges, formed as the Levi graph of the Pappus configuration. It is named after Pappus of Alexandria, an ancient Greek mathematician who is believed to have discovered the "hexagon theorem" describing the Pappus configuration. All the cubic distance-regular graphs are known; the Pappus graph is one of the 13 such graphs.

Foster graph

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.

Shrikhande graph named graph discovered by S. S. Shrikhande in 1959

In the mathematical field of graph theory, the Shrikhande graph is a named graph discovered by S. S. Shrikhande in 1959. It is a strongly regular graph with 16 vertices and 48 edges, with each vertex having degree 6. Every pair of nodes has exactly two other neighbors in common, whether the pair of nodes is connected or not.

Diamond graph node-link graph with four vertices and five edges

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.

Franklin graph

In the mathematical field of graph theory, the Franklin graph a 3-regular graph with 12 vertices and 18 edges.

Folkman graph graph with 20 vertices and 40 edges, the smallest semi-symmetric graph

In the mathematical field of graph theory, the Folkman graph, named after Jon Folkman, is a bipartite 4-regular graph with 20 vertices and 40 edges.

Clebsch graph one of two different regular graphs with 16 vertices

In the mathematical field of graph theory, the Clebsch graph is either of two complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge variant is the order-5 halved cube graph; it was called the Clebsch graph name by Seidel (1968) because of its relation to the configuration of 16 lines on the quartic surface discovered in 1868 by the German mathematician Alfred Clebsch. The 40-edge variant is the order-5 folded cube graph; it is also known as the Greenwood–Gleason graph after the work of Robert E. Greenwood and Andrew M. Gleason (1955), who used it to evaluate the Ramsey number R(3,3,3) = 17.

Biggs–Smith graph

In the mathematical field of graph theory, the Biggs–Smith graph is a 3-regular graph with 102 vertices and 153 edges.

Dyck graph node-link graph, the only cubic symmetric graph on 32 vertices

In the mathematical field of graph theory, the Dyck graph is a 3-regular graph with 32 vertices and 48 edges, named after Walther von Dyck.

F26A graph

In the mathematical field of graph theory, the F26A graph is a symmetric bipartite cubic graph with 26 vertices and 39 edges.

Robertson graph

In the mathematical field of graph theory, the Robertson graph or (4,5)-cage, is a 4-regular undirected graph with 19 vertices and 38 edges named after Neil Robertson.

Horton graph graph with 96 vertices and 144 edges, the first known non-Hamiltonian cubic 3-connected bipartite graph

In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton. Published by Bondy and Murty in 1976, it provides a counterexample to the Tutte conjecture that every cubic 3-connected bipartite graph is Hamiltonian.

Meredith graph 4-regular undirected graph with 70 vertices and 140 edges

In the mathematical field of graph theory, the Meredith graph is a 4-regular undirected graph with 70 vertices and 140 edges discovered by Guy H. J. Meredith in 1973.

Ljubljana graph

In the mathematical field of graph theory, the Ljubljana graph is an undirected bipartite graph with 112 vertices and 168 edges.

Bidiakis cube 3-regular graph with 12 vertices and 18 edges

In the mathematical field of graph theory, the Bidiakis cube is a 3-regular graph with 12 vertices and 18 edges.

Holt graph node-link graph with 27 vertices and 54 edges, the smallest half-transitive graph

In the mathematical field of graph theory, the Holt graph or Doyle graph is the smallest half-transitive graph, that is, the smallest example of a vertex-transitive and edge-transitive graph which is not also symmetric. Such graphs are not common. It is named after Peter G. Doyle and Derek F. Holt, who discovered the same graph independently in 1976 and 1981 respectively.

Tutte graph 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte

In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.

References

  1. ↑ Weisstein, Eric W. "Hamiltonian Graph". MathWorld .
  2. ↑ Weisstein, Eric W. "Hoffman graph". MathWorld .
  3. ↑ Hoffman, A. J. "On the Polynomial of a Graph." Amer. Math. Monthly 70, 30-36, 1963.
  4. ↑ van Dam, E. R. and Haemers, W. H. "Spectral Characterizations of Some Distance-Regular Graphs." J. Algebraic Combin. 15, 189-202, 2003.
  5. ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.