A study of line graph theory towards line set domination

Introduction

A line graph L (G) is the graph whose vertices correspond to the edges of G and two vertices in L (G) are adjacent if and only if the corresponding edges in G are adjacent. We begin by recalling some standard definitions from domination theory. A set S⊆ V (G) is said to be a dominating set of G, if every vertex in V-S is adjacent to some vertex in S. The minimum cardinality of vertices in such a set is called the domination number of G and is denoted by γ (G). Adominating set S is called the total dominating set, if for every vertex v ∈V; there exists a vertex u ∈S, u ≠v such that u is adjacent to v. The total domination number of G denoted by γt (G) is the minimum cardinality of total dominating set of G. A dominating set S ⊆V (G) is a connected dominating set, if the induced sub graph S has no isolated vertices. The connected domination number, γc (G) of G is the minimum cardinality of a connected dominating set of G. A set D ⊆V (L (G)) is said to be line dominating set of G, if every vertex not in D is adjacent to a vertex in D. The line domination number of G is denoted by γ l (G) is the minimum cardinality of a line dominating set. The concept of domination in graphs with its many variations is now well studied in graph theory (see [2] and [3] ). In this paper, we introduce the new concept in domination theory. Also we study the graph theoretic properties of γ sl(G) and many bounds were obtained in terms of elements of G and its relationships with other domination parameters were found. Throughout this paper, we consider the graphs with p≥4 vertices.

In this paper, we follow the notations of [1] . All the graphs considered here are simple and finite. As usual p =|V| and q =|E| denote the number of vertices and edges of a graph G respectively.

In general, we use to denote the sub graph induced by the set of vertices X and N (v) (N [v]) denote the open (closed) neighborhoods of a vertex v.

Review of Literature: In this paper, many bounds on i L G were obtained. Also their relationships with other domination parameters were obtained. Further, we introduce the concept of domatic number of L G, exact values of domatic number were obtained for some standard graphs. Also bound for domatic number is also obtained. A domatic partition in L G is a partition of V L G, all of whose classes are dominating sets in L G. The maximum number of classes of a domatic partition of LG is called the domatic number of L G and is denoted by d L G. The concept of domatic number in G was introduced by Cockeyne et al. [4] .

Line Set Domination Number: Initially we list out independent domination number of L G for some standard graphs.All graphs considered here are finite, nontrivial, undirected, connected, without loops or multiple edges or isolated vertices. For undefined terms or notations in this paper, may be found in Harary [1] . Let G = (V, E) be a graph. A set S ⊆ E is an edge dominating set of G, if every edge in E-S is adjacent to at least one edge in S. The edge domination number γ ′ (G) of G is the minimum cardinality of an edge dominating set. The minimal dominating graph of G is an intersection graph on the minimal dominating sets of vertices of G. This concept was introduced by Kulli and Janakiram [4] . In [5] , the concept of common minimal dominating graph of G was defined as the graph having same vertex set as G with two vertices adjacent if there is a minimal dominating set containing them. The concept of vertex minimal dominating graph MV D (G) of G was introduced in [6] , as the graph having V (MV D (G)) = V (G) ∪S (G), where S (G) is the set of all minimal dominating sets of G with two vertices u, v adjacent if they are adjacent in G or v = D is a minimal dominating set containing u.

Theorem 1

The following Theorem relates domination and independent domination in L G. Suppose . Then in this case, . Since and , it follows that .

Theorem 4: For any connected graph G, .

Proof: Suppose be the maximum set of edges in G such that for .

Then j forms maximal independent set of edges with . Since , there exists an independent set '

, where ' and such that , which covers all the vertices in L G.

Clearly, D forms a minimal independent dominating set of L G and it follows that . Therefore, .

Conclusion

A dominating set D is called independent dominating set of LG, if D is also independent. The independent domination number of LG denoted by i LG, equals min {; DD is an independent dominating set of LG}.Further we develop its relationship with other different domination parameters. Also we introduce the concept of domatic number in LG. The minimum cardinality of vertices in such a set is called a split line domination number in L (G) and is denoted by γsl (G). In this paper, we introduce the new concept in domination theory. Also, we study the graph theoretic properties of γ sl (G) and many bounds were obtained in terms of elements of G and its relationships with other domination parameters were found.

References

1. Kulli VR, Janakiram B, Niranjan KM. The dominating graph, Graph Theory Notes of New York. 2004; 46:5-8.
2. Kulli VR, Janakiram B, Niranjan KM, The vertex minimal dominating graph, Acta Ciencia Indica. 2002; 28:435-440
3. Haynes TW, Hedetniemi ST, Slater PJ. Fundamentals of domination in graphs, New York, Marcel Dekker, Inc, 2008.
4. Haynes TW, Hedetniemi ST, Slater PJ. Domination in graphs, Advanced Topics, New York, Marcel Dekker, Inc, 2007.
5. Kulli VR, Janakiram B. The minimal dominating graph, Graph Theory Notes of New York, New York. 2005; 28:12-15.
6. Araya Chaemchan. The edge domination number of connected graphs, Australasian journal of Combinatorics. 2010; 48:185189.