Concept
Cubic graph
Related concepts (43)
Tutte 12-cage
In the mathematical field of graph theory, the Tutte 12-cage or Benson graph is a 3-regular graph with 126 vertices and 189 edges named after W. T. Tutte. The Tutte 12-cage is the unique (3-12)-cage . It was discovered by C. T. Benson in 1966. It has chromatic number 2 (bipartite), chromatic index 3, girth 12 (as a 12-cage) and diameter 6. Its crossing number is known to be less than 165, see Wolfram MathWorld. The Tutte 12-cage is a cubic Hamiltonian graph and can be defined by the LCF notation [17, 27, –13, –59, –35, 35, –11, 13, –53, 53, –27, 21, 57, 11, –21, –57, 59, –17]7.
Gray graph
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 (see below).
Szekeres snark
In the mathematical field of graph theory, the Szekeres snark is a snark with 50 vertices and 75 edges. It was the fifth known snark, discovered by George Szekeres in 1973. As a snark, the Szekeres graph is a connected, bridgeless cubic graph with chromatic index equal to 4. The Szekeres snark is non-planar and non-hamiltonian but is hypohamiltonian. It has book thickness 3 and queue number 2. Another well known snark on 50 vertices is the Watkins snark discovered by John J. Watkins in 1989. Image:Szekeres snark 3COL.
Handshaking lemma
In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees (the numbers of times each vertex is touched) equals twice the number of edges in the graph.
Linkless embedding
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three-dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three-dimensional analogue of the planar graphs.
Brooks' theorem
In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors. The theorem is named after R. Leonard Brooks, who published a proof of it in 1941. A coloring with the number of colors described by Brooks' theorem is sometimes called a Brooks coloring or a Δ-coloring.
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. The complete graph Kn is integral for all n. The only cycle graphs that are integral are , , and . If a graph is integral, then so is its complement graph; for instance, the complements of complete graphs, edgeless graphs, are integral.
Asymmetric graph
In graph theory, a branch of mathematics, an undirected graph is called an asymmetric graph if it has no nontrivial symmetries. Formally, an automorphism of a graph is a permutation p of its vertices with the property that any two vertices u and v are adjacent if and only if p(u) and p(v) are adjacent. The identity mapping of a graph onto itself is always an automorphism, and is called the trivial automorphism of the graph. An asymmetric graph is a graph for which there are no other automorphisms.
Partial cube
In graph theory, a partial cube is a graph that is isometric to a subgraph of a hypercube. In other words, a partial cube can be identified with a subgraph of a hypercube in such a way that the distance between any two vertices in the partial cube is the same as the distance between those vertices in the hypercube. Equivalently, a partial cube is a graph whose vertices can be labeled with bit strings of equal length in such a way that the distance between two vertices in the graph is equal to the Hamming distance between their labels.
Bipartite double cover
In graph theory, the bipartite double cover of an undirected graph G is a bipartite, covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs, G × K_2. It is also called the Kronecker double cover, canonical double cover or simply the bipartite double of G. It should not be confused with a cycle double cover of a graph, a family of cycles that includes each edge twice. The bipartite double cover of G has two vertices u_i and w_i for each vertex v_i of G.