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 of its vertices with the property that any two vertices and are adjacent if and only if and 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. Examples The smallest asymmetric non-trivial graphs have 6 vertices. The smallest asymmetric regular graphs have ten vertices; there exist ten-vertex asymmetric graphs that are 4-regular and 5-regular. One of the five smallest asymmetric cubic graphs is the twelve-vertex Frucht graph discovered in 1939.. According to a strengthened version of Frucht's theorem, there are infinitely many asymmetric cubic graphs. Properties The class of asymmetric graphs is closed under complements: a graph ' ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  

Cubic Graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs. A bicubic graph is a cubic bipartite graph. Symmetry In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census.. Many well-known individual graphs ar