A STUDY OF DOMINATION NUMBER OF FEW GRAPH THEORY

MATHEMATICS

An elementary contraction of a graph G is a transformation of G to a new graph G1, such that two adjacent vertices u and υ of G are replaced by a new vertex w in G1 and w is adjacent in G1 to all vertices to which either u or υ is adjacent in G. A graph G* is said to be a contraction of G if G* can be obtained from G by a sequence of elementary contractions. The following is another characterization of a planar graph due to the German mathematician K. Wagner in 1937. A graph is planar if and only if it is not contractible to K5 or K3,3. A graph G is said to be planar if it can be represented on a plane in such a fashion that the vertices are all distinct points, the edges are simple curves, and no two edges meet one another except at their terminals. For example, K4, the complete graph on four vertices, is planar, as Figure 4A shows. Many of the others, however, require proofs of unusual ingenuity and depth even in the two-dimensional case. Sometimes a plane solution may be readily extendible to higher dimensions, but sometimes just the opposite is true, and a three-dimensional or n-dimensional problem may be entirely different from its two-dimensional counterpart. Each new problem must be attacked individually. The continuing charm and challenge of the subject are at least in part due to the relative simplicity of the statements coupled with the elusive nature of their solutions. In 1893 the British mathematician J.J. Sylvester posed the question: If a finite set S of points in a plane has the property that each line determined by two points of S meets at least one other point of S, must all points of S be on one line? Sylvester never found a satisfactory solution to the problem, and the first (affirmative) solutions were published a half century later. Since then, Sylvester’s problem has inspired many investigations and led to many other questions, both in the plane and in higher dimensions.

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.