Franklin graph

Last updated
Franklin Graph
Franklin graph hamiltonian.svg
The Franklin Graph
Named after Philip Franklin
Vertices 12
Edges 18
Radius 3
Diameter 3
Girth 4
Automorphisms 48 (Z/2Z×S4)
Chromatic number 2
Chromatic index 3
Genus 1
Properties Cubic
Hamiltonian
Bipartite
Triangle-free
Perfect
Vertex-transitive
Table of graphs and parameters

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

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 Franklin graph is named after Philip Franklin, who disproved the Heawood conjecture on the number of colors needed when a two-dimensional surface is partitioned into cells by a graph embedding. [2] [3] The Heawood conjecture implied that the maximum chromatic number of a map on the Klein bottle should be seven, but Franklin proved that in this case six colors always suffice. The Franklin graph can be embedded in the Klein bottle so that it forms a map requiring six colors, showing that six colors are sometimes necessary in this case. This embedding is the Petrie dual of its embedding in the projective plane shown below.

Philip Franklin was an American mathematician and professor whose work was primarily focused in analysis.

In graph theory, the Heawood conjecture or Ringel–Youngs theorem gives a lower bound for the number of colors that are necessary for graph coloring on a surface of a given genus. For surfaces of genus 0, 1, 2, 3, 4, 5, 6, 7, ..., the required number of colors is 4, 7, 8, 9, 10, 11, 12, 12, .... OEIS: A000934, the chromatic number or Heawood number.

In topological graph theory, an embedding of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs are associated with edges in such a way that:

It is Hamiltonian and has chromatic number 2, chromatic index 3, radius 3, diameter 3 and girth 4. It is also a 3-vertex-connected and 3-edge-connected perfect graph.

In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

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.

Algebraic properties

The automorphism group of the Franklin graph is of order 48 and is isomorphic to Z/2Z×S4, the direct product of the cyclic group Z/2Z and the symmetric group S4. It acts transitively on the vertices of the graph, making it vertex-transitive.

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.

Cyclic group mathematical group that can be generated as the set of powers of a single element

In group theory, a branch of abstract algebra, a cyclic group or monogenous group is a group 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 a power of g in multiplicative notation, or as a multiple of g in additive notation. This element g is called a generator of the group.

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 Franklin graph is

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.

Truncation (geometry) operation that cuts polytope vertices, creating a new facet in place of each vertex

In geometry, a truncation is an operation in any dimension that cuts polytope vertices, creating a new facet in place of each vertex. The term originates from Kepler's names for the Archimedean solids.

Hemi-octahedron polyhedron with 4 faces

A hemi-octahedron is an abstract regular polyhedron, containing half the faces of a regular octahedron.

Related Research Articles

Petersen graph graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

Heawood graph undirected graph with 14 vertices, 21 edges, and girth 6

In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.

Wheel graph graph formed from a cycle graph by adding a new vertex adjacent to all the vertices in the cycle

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n-1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n+1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. In the rest of this article we use the former notation.

Heawood number

In mathematics, the Heawood number of a surface is a certain upper bound for the maximal number of colors needed to color any graph embedded in the surface.

Gray graph undirected bipartite graph with 54 vertices and 81 edges

In the mathematical field of graph theory, the Gray graph is an undirected bipartite graph with 54 vertices and 81 edges. It is a cubic graph: every vertex touches exactly three edges. It was discovered by Marion C. Gray in 1932 (unpublished), then discovered independently by Bouwer 1968 in reply to a question posed by Jon Folkman 1967. The Gray graph is interesting as the first known example of a cubic graph having the algebraic property of being edge but not vertex transitive.

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.

Grötzsch graph

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch.

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.

Tietzes graph

In the mathematical field of graph theory, Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges. It is named after Heinrich Franz Friedrich Tietze, who showed in 1910 that the Möbius strip can be subdivided into six regions that all touch each other – three along the boundary of the strip and three along its center line – and therefore that graphs that are embedded onto the Möbius strip may require six colors. The boundary segments of the regions of Tietze's subdivision form an embedding of Tietze's graph.

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.

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.

Hoffman graph 4-regular graph with 16 vertices and 32 edges

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.

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.

Polyhedral graph

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected planar graphs.

References

  1. Weisstein, Eric W. "Franklin Graph". MathWorld .
  2. Weisstein, Eric W. "Heawood conjecture". MathWorld .
  3. Franklin, P. "A Six Color Problem." J. Math. Phys. 13, 363-379, 1934. hdl : 2027/mdp.39015019892200