1.
Petersen graph
–
In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a 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, although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by A. B. Kempe observed that its vertices can represent the ten lines of the Desargues configuration, donald Knuth states that the Petersen graph is a remarkable configuration that serves as a counterexample to many optimistic predictions about what might be true for graphs in general. The Petersen graph also makes an appearance in tropical geometry, the cone over the Petersen graph is naturally identified with the moduli space of five-pointed rational tropical curves. The Petersen graph is the complement of the graph of K5. As a Kneser graph of the form K G2 n −1, n −1 it is an example of an odd graph. Geometrically, the Petersen graph is the graph formed by the vertices and edges of the hemi-dodecahedron, that is, a dodecahedron with opposite points, lines and faces identified together. Any nonplanar graph has as minors either the complete graph K5, or the bipartite graph K3,3. The K5 minor can be formed by contracting the edges of a perfect matching, the K3,3 minor can be formed by deleting one vertex and contracting an edge incident to each neighbor of the deleted vertex. The most common and symmetric plane drawing of the Petersen graph, however, this is not the best drawing for minimizing crossings, there exists another drawing with only two crossings. Thus, the Petersen graph has crossing number 2, each edge in this drawing is crossed at most once, so the Petersen graph is 1-planar. On a torus the Petersen graph can be drawn without edge crossings, the Petersen graph can also be drawn in the plane in such a way that all the edges have equal length. That is, it is a unit distance graph, the simplest non-orientable surface on which the Petersen graph can be embedded without crossings is the projective plane. This is the embedding given by the construction of the Petersen graph. This construction forms a map and shows that the Petersen graph has non-orientable genus 1. The Petersen graph is strongly regular and it is also symmetric, meaning that it is edge transitive and vertex transitive. More strongly, it is 3-arc-transitive, every directed path in the Petersen graph can be transformed into every other such path by a symmetry of the graph
2.
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 graph is a 3-regular graph. Cubic graphs are also called trivalent graphs, a bicubic graph is a cubic bipartite graph. In 1932, Ronald M. Foster began collecting examples of symmetric graphs. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number s such that two oriented paths of length s can be mapped to each other by exactly one symmetry of the graph. He showed that s is at most 5, and provided examples of graphs with each value of s from 1 to 5. Semi-symmetric cubic graphs include the Gray graph, the Ljubljana graph, the Frucht graph is one of the two smallest cubic graphs without any symmetries, it possesses only a single graph automorphism, the identity automorphism. According to Brooks theorem every connected cubic graph other than the complete graph K4 can be colored with at most three colors, according to Vizings theorem every cubic graph needs either three or four colors for an edge coloring. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings, by Königs line coloring theorem every bicubic graph has a Tait coloring. The bridgeless cubic graphs that do not have a Tait coloring are known as snarks and they include the Petersen graph, Tietzes graph, the Blanuša snarks, the flower snark, the double-star snark, the Szekeres snark and the Watkins snark. There is a number of distinct snarks. Cubic graphs arise naturally in topology in several ways, for example, if one considers a graph to be a 1-dimensional CW complex, cubic graphs are generic in that most 1-cell attaching maps are disjoint from the 0-skeleton of the graph. Cubic graphs are formed as the graphs of simple polyhedra in three dimensions, polyhedra such as the regular dodecahedron with the property that three faces meet at every vertex. An arbitrary graph embedding on a surface may be represented as a cubic graph structure known as a graph-encoded map. In this structure, each vertex of a graph represents a flag of the embedding, a mutually incident triple of a vertex, edge. The three neighbors of each flag are the three flags that may be obtained from it by changing one of the members of this mutually incident triple, there has been much research on Hamiltonicity of cubic graphs. In 1880, P. G. Tait conjectured that every polyhedral graph has a Hamiltonian circuit. William Thomas Tutte provided a counter-example to Taits conjecture, the 46-vertex Tutte graph, in 1971, Tutte conjectured that all bicubic graphs are Hamiltonian
3.
Graph automorphism
–
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. Formally, an automorphism of a graph G = is a permutation σ of the vertex set V, such that the pair of vertices form an edge if and that is, it is a graph isomorphism from G to itself. Automorphisms may be defined in this way both for directed graphs and for undirected graphs, the composition of two automorphisms is another automorphism, and the set of automorphisms of a given graph, under the composition operation, forms a group, the automorphism group of the graph. In the opposite direction, by Fruchts theorem, all groups can be represented as the group of a connected graph – indeed. Constructing the automorphism group is at least as difficult as solving the graph isomorphism problem, for, G and H are isomorphic if and only if the disconnected graph formed by the disjoint union of graphs G and H has an automorphism that swaps the two components. In fact, just counting the automorphisms is polynomial-time equivalent to graph isomorphism The graph automorphism problem is the problem of testing whether a graph has a nontrivial automorphism and it belongs to the class NP of computational complexity. Similar to the isomorphism problem, it is unknown whether it has a polynomial time algorithm or it is NP-complete. There is a polynomial algorithm for solving the graph automorphism problem for graphs where vertex degrees are bounded by a constant. The graph automorphism problem is polynomial-time many-one reducible to the isomorphism problem. While no worst-case polynomial-time algorithms are known for the general Graph Automorphism problem, several open-source software tools are available for this task, including NAUTY, BLISS and SAUCY. SAUCY and BLISS are particularly efficient for sparse graphs, e. g. SAUCY processes some graphs with millions of vertices in mere seconds, however, BLISS and NAUTY can also produce Canonical Labeling, whereas SAUCY is currently optimized for solving Graph Automorphism. It also appears that the support of all generators is limited by a linear function of n. However, this has not been established for a fact, as of March 2012, molecular symmetry can predict or explain chemical properties. Several graph drawing researchers have investigated algorithms for drawing graphs in such a way that the automorphisms of the graph become visible as symmetries of the drawing. It is not always possible to display all symmetries of the graph simultaneously, so it may be necessary to choose which symmetries to display, several families of graphs are defined by having certain types of automorphisms, An asymmetric graph is an undirected graph without any nontrivial automorphisms. A vertex-transitive graph is a graph in which every vertex may be mapped by an automorphism into any other vertex. An edge-transitive graph is a graph in which every edge may be mapped by an automorphism into any other edge. A symmetric graph is a such that every pair of adjacent vertices may be mapped by an automorphism into any other pair of adjacent vertices
4.
Mathematics
–
Mathematics is the study of topics such as quantity, structure, space, and change. There is a range of views among mathematicians and philosophers as to the exact scope, Mathematicians seek out patterns and use them to formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proof, when mathematical structures are good models of real phenomena, then mathematical reasoning can provide insight or predictions about nature. Through the use of abstraction and logic, mathematics developed from counting, calculation, measurement, practical mathematics has been a human activity from as far back as written records exist. The research required to solve mathematical problems can take years or even centuries of sustained inquiry, rigorous arguments first appeared in Greek mathematics, most notably in Euclids Elements. Galileo Galilei said, The universe cannot be read until we have learned the language and it is written in mathematical language, and the letters are triangles, circles and other geometrical figures, without which means it is humanly impossible to comprehend a single word. Without these, one is wandering about in a dark labyrinth, carl Friedrich Gauss referred to mathematics as the Queen of the Sciences. Benjamin Peirce called mathematics the science that draws necessary conclusions, David Hilbert said of mathematics, We are not speaking here of arbitrariness in any sense. Mathematics is not like a game whose tasks are determined by arbitrarily stipulated rules, rather, it is a conceptual system possessing internal necessity that can only be so and by no means otherwise. Albert Einstein stated that as far as the laws of mathematics refer to reality, they are not certain, Mathematics is essential in many fields, including natural science, engineering, medicine, finance and the social sciences. Applied mathematics has led to entirely new mathematical disciplines, such as statistics, Mathematicians also engage in pure mathematics, or mathematics for its own sake, without having any application in mind. There is no clear line separating pure and applied mathematics, the history of mathematics can be seen as an ever-increasing series of abstractions. The earliest uses of mathematics were in trading, land measurement, painting and weaving patterns, in Babylonian mathematics elementary arithmetic first appears in the archaeological record. Numeracy pre-dated writing and numeral systems have many and diverse. Between 600 and 300 BC the Ancient Greeks began a study of mathematics in its own right with Greek mathematics. Mathematics has since been extended, and there has been a fruitful interaction between mathematics and science, to the benefit of both. Mathematical discoveries continue to be made today, the overwhelming majority of works in this ocean contain new mathematical theorems and their proofs. The word máthēma is derived from μανθάνω, while the modern Greek equivalent is μαθαίνω, in Greece, the word for mathematics came to have the narrower and more technical meaning mathematical study even in Classical times
5.
Graph theory
–
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, nodes, or points which are connected by edges, arcs, Graphs are one of the prime objects of study in discrete mathematics. Refer to the glossary of graph theory for basic definitions in graph theory, the following are some of the more basic ways of defining graphs and related mathematical structures. To avoid ambiguity, this type of graph may be described precisely as undirected, other senses of graph stem from different conceptions of the edge set. In one more generalized notion, V is a set together with a relation of incidence that associates with each two vertices. In another generalized notion, E is a multiset of unordered pairs of vertices, Many authors call this type of object a multigraph or pseudograph. All of these variants and others are described more fully below, the vertices belonging to an edge are called the ends or end vertices of the edge. A vertex may exist in a graph and not belong to an edge, V and E are usually taken to be finite, and many of the well-known results are not true for infinite graphs because many of the arguments fail in the infinite case. The order of a graph is |V|, its number of vertices, the size of a graph is |E|, its number of edges. The degree or valency of a vertex is the number of edges that connect to it, for an edge, graph theorists usually use the somewhat shorter notation xy. Graphs can be used to model many types of relations and processes in physical, biological, social, Many practical problems can be represented by graphs. Emphasizing their application to real-world systems, the network is sometimes defined to mean a graph in which attributes are associated with the nodes and/or edges. In computer science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation, etc. For instance, the structure of a website can be represented by a directed graph, in which the vertices represent web pages. A similar approach can be taken to problems in media, travel, biology, computer chip design. The development of algorithms to handle graphs is therefore of major interest in computer science, the transformation of graphs is often formalized and represented by graph rewrite systems. Graph-theoretic methods, in forms, have proven particularly useful in linguistics. Traditionally, syntax and compositional semantics follow tree-based structures, whose power lies in the principle of compositionality
6.
Graph (discrete mathematics)
–
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense related. The objects correspond to mathematical abstractions called vertices and each of the pairs of vertices is called an edge. Typically, a graph is depicted in form as a set of dots for the vertices. Graphs are one of the objects of study in discrete mathematics, the edges may be directed or undirected. In contrast, if any edge from a person A to a person B corresponds to As admiring B, then this graph is directed, because admiration is not necessarily reciprocated. The former type of graph is called a graph and the edges are called undirected edges while the latter type of graph is called a directed graph. Graphs are the subject studied by graph theory. The word graph was first used in this sense by J. J. Sylvester in 1878, the following are some of the more basic ways of defining graphs and related mathematical structures. In one very common sense of the term, a graph is an ordered pair G = comprising a set V of vertices, nodes or points together with a set E of edges, arcs or lines, which are 2-element subsets of V. To avoid ambiguity, this type of graph may be described precisely as undirected, other senses of graph stem from different conceptions of the edge set. In one more general conception, E is a set together with a relation of incidence that associates with each two vertices. In another generalized notion, E is a multiset of unordered pairs of vertices, many authors call these types of object multigraphs or pseudographs. All of these variants and others are described more fully below, the vertices belonging to an edge are called the ends or end vertices of the edge. A vertex may exist in a graph and not belong to an edge, V and E are usually taken to be finite, and many of the well-known results are not true for infinite graphs because many of the arguments fail in the infinite case. Moreover, V is often assumed to be non-empty, but E is allowed to be the empty set, the order of a graph is |V|, its number of vertices. The size of a graph is |E|, its number of edges, the degree or valency of a vertex is the number of edges that connect to it, where an edge that connects to the vertex at both ends is counted twice. For an edge, graph theorists usually use the shorter notation xy. As stated above, in different contexts it may be useful to refine the term graph with different degrees of generality, whenever it is necessary to draw a strict distinction, the following terms are used
7.
Group (mathematics)
–
In mathematics, a group is an algebraic structure consisting of a set of elements equipped with an operation that combines any two elements to form a third element. The operation satisfies four conditions called the group axioms, namely closure and it allows entities with highly diverse mathematical origins in abstract algebra and beyond to be handled in a flexible way while retaining their essential structural aspects. The ubiquity of groups in areas within and outside mathematics makes them a central organizing principle of contemporary mathematics. Groups share a kinship with the notion of symmetry. The concept of a group arose from the study of polynomial equations, after contributions from other fields such as number theory and geometry, the group notion was generalized and firmly established around 1870. Modern group theory—an active mathematical discipline—studies groups in their own right, to explore groups, mathematicians have devised various notions to break groups into smaller, better-understandable pieces, such as subgroups, quotient groups and simple groups. A theory has developed for finite groups, which culminated with the classification of finite simple groups. Since the mid-1980s, geometric group theory, which studies finitely generated groups as objects, has become a particularly active area in group theory. One of the most familiar groups is the set of integers Z which consists of the numbers, −4, −3, −2, −1,0,1,2,3,4. The following properties of integer addition serve as a model for the group axioms given in the definition below. For any two integers a and b, the sum a + b is also an integer and that is, addition of integers always yields an integer. This property is known as closure under addition, for all integers a, b and c, + c = a +. Expressed in words, adding a to b first, and then adding the result to c gives the final result as adding a to the sum of b and c. If a is any integer, then 0 + a = a +0 = a, zero is called the identity element of addition because adding it to any integer returns the same integer. For every integer a, there is a b such that a + b = b + a =0. The integer b is called the element of the integer a and is denoted −a. The integers, together with the operation +, form a mathematical object belonging to a class sharing similar structural aspects. To appropriately understand these structures as a collective, the abstract definition is developed
8.
Group action
–
In mathematics, an action of a group is a way of interpreting the elements of the group as acting on some space in a way that preserves the structure of that space. Common examples of spaces that groups act on are sets, vector spaces, actions of groups on vector spaces are called representations of the group. Some groups can be interpreted as acting on spaces in a canonical way, more generally, symmetry groups such as the homeomorphism group of a topological space or the general linear group of a vector space, as well as their subgroups, also admit canonical actions. A common way of specifying non-canonical actions is to describe a homomorphism φ from a group G to the group of symmetries of a set X. The action of an element g ∈ G on a point x ∈ X is assumed to be identical to the action of its image φ ∈ Sym on the point x. The homomorphism φ is also called the action of G. Thus, if G is a group and X is a set, if X has additional structure, then φ is only called an action if for each g ∈ G, the permutation φ preserves the structure of X. The abstraction provided by group actions is a one, because it allows geometrical ideas to be applied to more abstract objects. Many objects in mathematics have natural group actions defined on them, in particular, groups can act on other groups, or even on themselves. Because of this generality, the theory of group actions contains wide-reaching theorems, such as the orbit stabilizer theorem, the group G is said to act on X. The set X is called a G-set. In complete analogy, one can define a group action of G on X as an operation X × G → X mapping to x. g. =. h for all g, h in G and all x in X, for a left action h acts first and is followed by g, while for a right action g acts first and is followed by h. Because of the formula −1 = h−1g−1, one can construct an action from a right action by composing with the inverse operation of the group. Also, an action of a group G on X is the same thing as a left action of its opposite group Gop on X. It is thus sufficient to only consider left actions without any loss of generality. The trivial action of any group G on any set X is defined by g. x = x for all g in G and all x in X, that is, every group element induces the identity permutation on X. In every group G, left multiplication is an action of G on G, g. x = gx for all g, x in G
9.
Vertex-transitive graph
–
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 f, V → V such that f = v 2. In other words, a graph is vertex-transitive if its automorphism group acts transitively upon 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 graph is regular. However, not all graphs are symmetric, and not all regular graphs are vertex-transitive. Finite vertex-transitive graphs include the symmetric graphs, the finite Cayley graphs are also vertex-transitive, as are the vertices and edges of the Archimedean solids. Potočnik, Spiga and Verret have constructed a census of all connected cubic vertex-transitive graphs on at most 1280 vertices, although every Cayley graph is vertex-transitive, there exist other vertex-transitive graphs that are not Cayley graphs. The most famous example is the Petersen graph, but others can be constructed including the graphs of edge-transitive non-bipartite graphs with odd vertex degrees. The edge-connectivity of a graph is equal to the degree d. If the degree is 4 or less, or the graph is also edge-transitive, or the graph is a minimal Cayley graph, infinite vertex-transitive graphs include, infinite paths infinite regular trees, e. g. A well known conjecture stated that every infinite graph is quasi-isometric to a Cayley graph. A counterexample was proposed by Diestel and Leader in 2001, in 2005, Eskin, Fisher, and Whyte confirmed the counterexample. Edge-transitive graph Lovász conjecture Semi-symmetric graph Zero-symmetric graph Weisstein, Eric W. Vertex-transitive graph, a census of small connected cubic vertex-transitive graphs. Primož Potočnik, Pablo Spiga, Gabriel Verret,2012
10.
Edge-transitive graph
–
In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is an automorphism of G that maps e1 to e2. In other words, a graph is edge-transitive if its automorphism group acts transitively upon its edges, Edge-transitive graphs include any complete bipartite graph K m, n, and any symmetric graph, such as the vertices and edges of the cube. Symmetric graphs are also vertex-transitive, but in general edge-transitive graphs need not be vertex-transitive, the Gray graph is an example of a graph which is edge-transitive but not vertex-transitive. All such graphs are bipartite, and hence can be colored with two colors. An edge-transitive graph that is regular, but not vertex-transitive, is called semi-symmetric. The Gray graph again provides an example, every edge-transitive graph that is not vertex-transitive must be bipartite and either semi-symmetric or biregular. Edge-transitive Weisstein, Eric W. Edge-transitive graph