A Study of Graphs Decomposing Labeling, and Covering in Mathematical Graph Theory

A graph with a distinction labeling characterized on it is known as a labeled graph. A decomposition of a labeled graph into parts, each part containing the edges having a typical weight is called basic weight decomposition. A typical weight decomposition of G in which each part contains rn edges is called rn-fair. A timberland wherein every segment is a way is known as direct woods. Blossom and Ruiz [13] share demonstrated that each part for all intents and purpose weight decomposition is a direct timberland and the vertices of least and most extreme mark are not interior vertices in any way of a section containing it. Right now consider the accompanying issue given in [13]. Let C = (V E) be a graph. A distinction labeling of C is an infusion f from V to the set of non- negative numbers together with the weight function f on E given by f*(uv) = f(u) - f(v)I for each edge uv E. A graph G = (V,E) comprises of two finite sets: V(G), the vertex set of the graph, regularly indicated by just V, which is a nonempty set of elements called vertices, and E(G), the edge set of the graph, frequently signified by just E, which is a set (potentially empty) of elements called edges. A graph, at that point, can be thought of as a drawing or diagram comprising of an assortment of vertices (spots or points) together with edges (lines) joining certain pairs of these e3, e4, e5, e6, e7 }.

Sometimes we speak to an edge by the two vertices that it interfaces. In Figure 1 we have e1 = (v1, v2), e2 = (v1 ,v4). An edge e of graph G is said to be episode with the vertex v if v is an end vertex of e. For example in Figure 1 an edge e1 is episode with two vertices v1 and v2. An edge e having indistinguishable end vertices called a loop. At the end of the day, in a loop a vertex v is joined to itself by an edge e. The level of a vertex v, composed d(v), is the number of edges occurrence with v. In Figure 1 we have d(v1) = 3, d(v2) = 2, d(v3) = 3, d(v4) = 4 and d(v5) = 2. On the off chance that for some positive whole number k, d(v) = k for each vertex v of graph G, at that point G is called k-customary. The graph in Figure 1 is an associated and undirected graph. In contrast to most different territories in Mathematics, the theory of graphs has a definite beginning stage, when the Swiss mathematician Leonard Euler (1707-1783) considered the problems of the seven Konigsberg spans. In the mid eighteenth century the city of Konigsberg (in Prussia) was isolated into four areas by the Pregel waterway. Seven scaffolds associated these districts as appeared in Figure 2 (a). A graph G is called associated if there is a way between each pair of vertices. When there is no worry about the bearing of an edge the graph is called undirected. Areas are appeared by A, B, C, D individually. It is said that the townsfolk of Konigsberg delighted themselves by attempting to discover a course that crossed each extension just once (It was OK to go to a similar island any number of times).

One of the themes in a mathematical area depicted as Discrete Mathematics is graphic theory. The difficulties and solutions in discrete mathematics contrast very fundamentally with those in constant mathematics. We check the number of articles in discrete mathematics and measure their sizes in continuous mathematics. Although discrete mathematics began just as soon as man for quite a long time. In the twentieth century this image began to change. The major improvement was the change in the development of mathematics. His main problem was transformed from the idea of a few to the idea of a set that was gradually reasonable in terms of discrete mathematics rather than consistent mathematics. Secondly, the expanding use of PCs in the public eye was sensational. In software engineering, a large part of the theory uses ideas of discrete math. In using the graph presented in Figure 2 Euler examined whether such a course could be expected. The main paper he distributed in 1736 in graphic theory shows the difficulty of such a course and provides the necessary conditions to make such a journey happen. The theory of the graph was meant to deal with such problems. Graph theory as an individual in the discrete family of mathematics has an incredible number of applications to software engineering and many sciences, design and trade (physical, organic and societal). Figure 3 contains a portion of major topics in the field of graph theory.

The purpose of this study is to give a few outcomes in a class of problems arranged as Graph labeling. Leave G alone an undirected graph without loops or twofold associations between vertices. In labeling (valuation or numbering) of a graph G, we partner unmistakable nonnegative whole numbers to the vertices of G-as vertex labels (vertex esteems or vertex numbers) so that each edge gets a particular positive whole number as an edge name (edge worth or edge number) contingent upon the vertex labels of vertices which are occurrence with this edge. Enthusiasm for graph labeling started in mid-1960s with a guess by Kotzig-Ringel and a paper by Rosa. In 1967, Rosa distributed a spearheading paper on graph labeling problems. He called a function ƒ a β-labeling of a graph G with n edges (Golomb along these lines called such labeling graceful and this term is presently the well-known one) if ƒ is an infusion from the vertices of G to the set {0, 1, …, n} to such an extent that, when each edge is labeled with the supreme estimation of the contrast between the labels of the two end vertices, the subsequent edge labels are particular. This labeling gives a successive labeling of the edges from 1 to the number of edges. Any graph that can be gracefully labeled is a graceful graph. Examples of graceful graphs are shown in Figure 4.

Although numerous groups of graceful graphs are known, a general essential or adequate condition for gracefulness has not yet been found. Likewise It isn't known whether all tree graphs are graceful. A α-valuation of a graph G is a graceful valuation of G which likewise fulfills the accompanying condition: there exists a number γ (0 ≤ γ < E(G)) to such an extent that, for any edge e∈ E(G) with the end vertices u, v ∈ V(G), min { vertex name (v), vertex name (u) } ≤ γ < max { vertex mark (v), vertex name (u) } Obviously in the event that there exists a α-valuation of graph G, at that point G is a bipartite graph. The main graph in Figure 4 is a way with six edges and it has a α-labeling with γ =3. During the previous thirty years, more than 200 papers on this point have been showed up in diaries. Despite the fact that the guess that all trees are graceful has been the focal point of a large number of these papers, this guess is as yet unproved. Tragically there are hardly any broad outcomes in graph labeling. In reality in any event, for problems as barely engaged as the ones including the unique classes of graphs, the labelings have been hard-won and include a huge number of cases. Finding a graph that has a α-labeling is another regular methodology in numerous papers. The accompanying condition (because of Rosa) is known to be important and on account of cycles likewise adequate for a 2-ordinary graph G = (V,E) to have a α-labeling: ⏐E(G)⏐≡ 0 (mod 4). In 1982, Kotzig guessed that this condition is likewise adequate for a 2-normal graph with parts. Labeled graphs fill in as valuable apparatuses for an expansive scope of applications. Sprout and Golomb in two brilliant reviews have introduced deliberately a use of graph labeling in many research fields, for example, coding theory problems, X-beam crystallographic investigation, correspondence network structure, ideal circuit design, basic voltage generator, and added substance number theory. Right now limit our conversation to applications of graceful labeling and its varieties in decomposition of graphs, ideal arrangement of distinction sets, and number groupings, for example, the Skolem succession: A graph G is a constrained nonempty set of things gathered vertices with a ton of unordered pairs of unmistakable vertices of G which is called edges showed by V (G) and E (G), independently. In case e = {u, v} is an edge, we form e = uv; we express that e joins the vertices u and v; u and v are neighboring vertices; u and v are event with e. In case two vertices are not joined, by then we express that they are non-connecting. If two unmistakable edges are scene with a normal vertex, by then they are said to be coterminous each other.

Definition 1: A decomposition of a graph G is a family H = (H1, H2, … , Hn) of sub graphs of G such that each edge of G is contained in exactly one member of H. In fact G is the edge disjoint

union of its sub graphs Hi

For example the graph G shown in Figure 5 has a decomposition H = (H1, H2, H3) into three K3: E(H1) = {(u1, u2), (u2, u6), (u1, u6), E(H2) = {(u2, u3), (u3, u4), (u2, u4), E(H3) = {(u1, u4), (u1, u6)} and V(H1) = (u1, u2, u6 ), V(H2) = (u2, u3, u4 ), V(H3) = (u4, u5, u6 ). Definition 2: Let two graphs G and G′ be given. A G-decomposition of a graph G′ is a decomposition of G into sub graphs isomorphic to G. In other words, each member Hi in definition 2. must be isomorphic to G. We write ′ whenever a G-decomposition of G′ exists. The decomposition of graph G in Figure 5 is a K3-decomposition, i.e., Definition 3: A decomposition H of a graph G into subgraphs H1,H2, … , Hn is said to be cyclic if there exists an isomorphism ƒ of G which induces a cyclic permutation fv of the set V(G) and satisfies the following implication: if Hi ∈ H then f (Hi) ∈ H for i = 1,2, … ,n. Here f (Hi) is the subgraph of G with vertex set {f (u); u ∈ V(Hi)} and edgeset { (f (u), f (v) ); e = ( u, v )∈ E(Hi) }.

Definition 4: Let c, m, p1, p2, … , pm be positive integers, and Si ={ X0i < X1i < … < Xpi,i }; i = 1,2, … ,m be a sequence of integers and Di = { Xji - Xki , 0 ≤ k < j ≤ pi }, i = 1,2, … ,m be their difference sets. Then we say that the system {D1, D2, … ,Dm } is a perfect system of difference sets (PSDS) starting with c if Each set Di is called a component of PSDS {D1, D2, … , Dm }. The size of Di is pi. A PSDS is called regular if all its components are of the same size i.e. p1 = p2 = … = pm = n-1. Traditionally a regular PSDS with m components of size n-1 starting at c is referred to as (m, n, c). Biraud and Blum and Ribes [5] were most likely the initial ones to watch a connection between graceful labeling of graphs and PSDS. The ordinary PSDS (1,n,1) is a PSDS with one segment beginning with 1. There exists just two normal PSDS (1,n,1) [5]. They are The mirror images of the above PSDS are also PSDS.

Definition 5 A standards in a numerical framework (Σ; R) is said to be Smarandachely denied on the off chance that it carries on in at any rate two unique ways inside a similar set Σ, i.e., approved and invalided, or just invalided however in different unmistakable manners. A Smarandache framework (Σ; R) is a scientific framework which has at any rate one Smarandachely denied rule in R. Definition 6 For an integer m ≥ 2, let (Σ1; R1), (Σ2; R2), · · · , (Σm; Rm) be m mathematical systems different two by two. A Smarandache multi-space is a pair (Σ; e Re) with Definition 7 A maxims is said to be Smarandachely denied if the saying carries on in at any rate two unique ways inside a similar space, i.e., approved and invalided, or just invalided yet in numerous particular manners. Example 1 Let us consider an Euclidean plane R2 and three non-collinear points A, B and C. Characterize s-points as all standard Euclidean points on R2 and s-lines any Euclidean line that goes through one and only one of points A, B and C, for example, those appeared in Fig.6. (i) The adage (A5) that through a point outside to a given line there is just one equal going through it is presently supplanted by two articulations: one equal, and no equal. Leave L alone a s-line goes through C and is equal in the Euclidean sense to AB. Notice that through any s-point not lying on AB there is one s-line corresponding to L and through some other s-point lying on AB there is no s-lines corresponding to L, for example, those appeared in Fig.6(a). is presently supplanted by; one s-line, and no s-line. Notice that through any two unmistakable spoints D, E collinear with one of A, B and C, there is one s-line going through them and through any two particular s-points F, G lying on AB or non-collinear with one of A, B and C, there is no s-line going through them, for example, those appeared in Fig.6(b).

Definition 8 A combinatorial system CG is a union of mathematical systems (Σ1; R1),(Σ2; R2), · · · , (Σm; Rm) for an integer m, i.e., with an underlying connected graph structure G, where

Definition 9 A labeling on a graph G = (V, E) is a mapping θL : V ∪ E → L for a name set L, meant by GL. In the event that θL: E → ∅ or θL: V → ∅, at that point GL is known as a vertex labeled graph or an edge labeled graph, meant by GV or GE, separately. Else, it is known as a vertex-edge labeled graph. Example:

Specified Parts Decomposition Problem Given a graph C with edge set E(C) and an assortment of edge-disjoint straight woods F1, F2,..., Fk containing a sum of JEJ edges, does there exist a typical weight decomposition of C whose parts are individually isomorphic to F1 , F2,..., Fk? We get normal weight decompositions into determined parts for cycles, cartesian item G1 x C2 of two graphs C1 and C2 , rn-crystals Cm x P, rectangular matrices Pm X P and for n-shapes Q. We likewise talk about the comparing issue for added substance labelings. Theorem 1. A labeling exists for every cycle with ns edges which decomposes it into n copies of sP2. Case (ii) s is even. Define a labeling f as follows. A common-weight decomposition of an even cycle into two immaculate matching's. In the accompanying theorem we get a comparative outcome for odd cycles.

CONCLUSION

A vertex v of a graph G is known as a cut-vertex of G if the evacuation of v expands the quantity of parts. An edge e of a graph G is known as a cut edge or extension if the evacuation of e expands the quantity of parts. A lot of edges S is called an edge cut of G if the quantity of segments of G - S is more prominent than that of G. A square of a graph is a maximal associated, non-unimportant sub graph without cut-vertices. A graph is non-cyclic in the event that it has no cycles. A tree is an associated non-cyclic graph. A tree with precisely one vertex of degree > 3 is known as a creepy crawly tree and an established tree comprising of k - branches where ith branch is a path of length I, is called an olive tree. Let G be a graph with vertex set{ v, v2, ..., v}. At that point the graph obtained by presenting n new vertices u1 , u2 , ..., u and edges u1 vi is indicated by G. The separation between two vertices u and v in an associated graph G is the length of the most limited u - v path in G and is signified by d(u, v). The level of a vertex v in a graph G, indicated by d(v), is the quantity of edges episode with v. The base degree among the vertices of G is indicated by 6(G), while the greatest degree among the vertices of G is signified by A(G). In the event that 6(G) = A(G) = r, at that point all vertices have a similar degree and G is known as a customary graph of degree r. In the event that d(v) = 0, v is called a disconnected vertex.

REFERENCES

L. Pandiselvi, S. Navaneetha Krishnan and A. Nellai Murugan (2016). Path Related V4 Cordial Graphs. International Journal Of Recent Advances in Multidisciplinary Research, Vol. 03, Issue 02, pp.1285-1294, February 2016. A. Rosa (1966). On certain valuations of the vertices of a graph, Theory of graphs (International Symposium, Rome). C. Sekar (2002). Studies in Graph Theory, PhD Thesis, Madurai Kamaraj University. R. Sridevi, S. Navaneethakrishnan and K. Nagarajan (2012). Odd-Even graceful graphs, J.Appl.Math.& Informatics Vol.30, No. 5-6, pp. 913-923. M. Sundaram, R. Ponraj and S. Somasundaram (2005). Prime Cordial Labeling of graphs, Journal of Indian Academy of Mathematics, 27, pp. 373-390. R. Sridevi, A. Nellai Murugan, A. Nagarajan, and S. Navaneethakrishnan (2013). Fibonacci Divisor Cordial Graphs, International Journal of Mathematics and Soft Computing. R. Sridevi, S. Navaneetha Krishnan (2013). Some New Graph Labeling Problems and Related Topics(Thesis). ManonmaniamSundaranar University. Solomon W. Golombo (1972). How to number a graph, Graph Theory and Computing, Academic Press, New York, pp. 23-37. R. Tao (1998). On k-cordiality of cycles, crowns and wheels, Systems Sci., 11, pp. 227-229. Cordial graphs, International Mathematical Forum, Vol. 7, No. 35, 1737-1749. R. Varatharajan, S. Navaneethakrishnan and K. Nagarajan (2011). Divisor cordial graph, International Journal of Mathematical Comb., Vol .4, pp. 15-25. S.K. Vaidya, U.M. Prajapati (2011). Fibonacci and Super Fibonacci Graceful Labelings of some cycle related graphs, International J.Math.Combi. Vol.4, pp. 59-69. R. Vasuki, A. Nagarajan (2010). Studies in Graph Theory – Labeling Problems in Graphs(Thesis), Manonmaniam Sundaranar University. M.Z. Youssef (2009). On k-cordial labeling,Australas .J. Combin., Vol 43, pp. 31- 37. G.J. Gallian (2009). A Dynamic survey of graph labeling, The electronic journal of combinotorics, 16 (2009), #DS6. Z. Gao (2007). Odd graceful labelings of some union of graphs, J. Nat. Sci. Heilongjiang Univ, 24, pp. 35-39. R.B. Gnanajothi (1991). Topics in Graph Theory, Ph.D. Thesis, Madurai Kamaraj University. S.W. Golombo (1972). How to number a graph in graph Theory and Computing, R.C.Read, ed., Academic Press, New York, pp. 23-37. L. F. Mao (2009). Combinatorial Geometry with Applications to Field Theory, InfoQuest, USA. ShreedharK, B. Sooryanarayana and Raghunath P. (2009). Smarandachely k-Constrained labeling of Graphs, International J.Math. Combin. Vol.1, pp. 50-60. P. Devadas Rao, B. Sooryanarayana and M. Jayalakshmi (2009). Smarandachely k-Constrained Number of Paths and Cycles, International J.Math. Combin. Vol. 3, pp. 48-60. R. Vasuki and A. Nagarajan (2009). Some Results on Super Mean Graphs, International J.Math. Combin. Vol. 3, pp. 82-96. Bibin K. Jose (2009). Open Distance-Pattern Uniform Graphs, International J.Math. Combin. Vol.3, pp. 103-115.

Associate Professor, Department of Mathematics, Galgotias University, Greater Noida, Uttar Pradesh, India