Some bounds on domination related parameters.
1. INTRODUCTIONBy a graph, G = (V,E) we mean a simple, finite undirected graph. Unless otherwise stated, all graphs are assumed to have p--vertices and q--edges. Terms not defined here are used in the sense of Harary [5]. The concept of domination for vertices was introduced by Ore [9]. The maximum and minimum degree of vertices of G are denoted by [Delta](G), [delta](G) respectively. The smallest number of vertices in any cover for G is the covering number [[alpha].sub.0] and the smallest number of edges in edge cover for G is the edge covering number [[alpha].sub.1]. The independence number and edge independence number of G are respectively denoted by [[beta].sub.0] and [[beta].sub.1]. A set D of vertices in a graph G=(V,E) is a dominating set of G if every vertex in V\D is adjacent to some vertex in D. The domination number [gamma](G) of G is the minimum cardinality of dominating sets of G. A dominating set D of a graph G is said to be split and non-split dominating set if the induced subgraph <V\D> disconnected and <V\D> connected respectively. The split and non-split domination number [[gamma].sub.s](G) and [[gamma].sub.ns](G) of G are the minimum cardinality of their corresponding dominating sets of G. In [1], B.D. Acharya, S. Arumugam and P.J. Slater introduced the parameter for the dominating sets of G and posted the problem of finding either the exact value of [mu](G) or 'good' bounds for it and to characterize the class of dominating sets of D for which [mu](G) [??] m(D,V\D) where m(D,V\D) where denote the number of edges with one end in D and other end in. In this paper, we present some results on [mu](G) and we introduce a new parameter [upsilon](G).
2. PRIOR RESULTS
Theorem 2.1 [10] For any graph G, (i) p - q [less than or equal to] [gamma](G) [less than or equal to] p - [Delta] (ii) p - q [less than or equal to] [gamma](G) [less than or equal to] p + 1 - [square root of 1 + 2q]
Theorem 2.2 [10] For any graph G, (i) [p/[Delta] + 1] [less than or equal to] [gamma](G) [less than or equal to] p - [[beta].sub.0], and (ii) [[alpha].sub.0] + [[beta].sub.0] = p = [[alpha].sub.1] + [[beta].sub.1]
Theorem 2.3 [10] If G is a graph with p [greater than or equal to] 2, and [bar.G] its complement then (i) 3 [less than or equal to] [gamma](G) [less than or equal to] [gamma]([bar.G]) [less than or equal to] p + 1 (ii) 2 [less than or equal to] [gamma](G) * [gamma]([bar.G]) [less than or equal to] p
Theorem 2.4 [10] If a graph G has diam (G) = 2 then [gamma](G) [less than or equal to] [delta](G)
Theorem 2.5 [7] For any non-complete connected graph G, (i)[gamma](G) [less than or equal to] [[gamma].sub.s](G), (ii) [[gamma].sub.s](G) [less than or equal to] [[alpha].sub.0](G) and (iii) [[gamma].sub.s](G) [less than or equal to] p[Delta](G)/([Delta](G) + 1).
Theorem 2.6 [8] For any connected graph G, (i)[gamma](G) [less than or equal to] [[gamma].sub.ns](G), (ii) [[gamma].sub.ns](G) [less than or equal to] [[gamma].sub.ns](H) where H is a spanning subgraph of G, (iii) [[gamma].sub.ns](G) [less than or equal to] (q - 2p + 1)/2 and (iv) [[gamma].sub.ns](G) [less than or equal to] p - [omega](G) + 1 where [omega](G) is the clique number of G.
3. MAIN RESULTS
Here, we consider connected graphs only. Definition 3.1 [1] For any dominating set D [??] V of G, let m(D,V\D) (or [m.sub.D](G)) denote the number of edges with one end in D and other end in V\D. Then [mu](G) is defined by [??][m.sub.D](G), where D(G) denotes the set of all dominating sets of G.
We further define a new parameter [upsilon](G) by, [upsilon](G) = [??] [m.sub.D](G).
Remark 3.2 (i) If we consider D = V then [mu](G) = [upsilon](G) = 0. Hence we exclude D = V from D(G). (ii) From the definition of [mu](G) and [upsilon](G), we always have [mu](G) [less than or equal to] [m.sub.D](G) [less than or equal to] [upsilon](G), [for all]D [member of] D(G).
[ILLUSTRATION OMITTED]
For this graph G, we present some dominating sets for possible values of [m.sub.D](G).
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence and [mu](G) = 1 and [upsilon](G) = 6.
Theorem 3.4 For any graph G, 1 [less than or equal to] [m.sub.D](G) [less than or equal to] q.
Proof: Since we exclude that D=V from D(G), the minimum value of [m.sub.D](G) is one. Suppose all the edges are covered by any minimal dominating set then the maximum value of [m.sub.D](G) is q and hence the results.
Corollary 3.5 If G is any tree then [m.sub.D](G) [less than or equal to] p - 1.
Proposition 3.6
(i) For the cycle graph, [C.sub.n], n [greater than or equal to] 3, [mu][C.sub.n] = 2, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
(ii) For the path graph [P.sub.n], n [greater than or equal to] 2, [mu][P.sub.n] = 1 [upsilon]([P.sub.n]) = n - 1
(iii)For the complete graph [K.sub.n], n [greater than or equal to] 4, [mu][K.sub.n] = n - 1, [upsilon]([P.sub.n]) = n - 1,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
(iv) For the fan graph [F.sub.n], n [greater than or equal to] 2, [mu][F.sub.n] = 2, [upsilon]([P.sub.n]) = n + 1
(v) For the book graph [B.sub.n], n [greater than or equal to] 1, [mu][B.sub.n] = 2, [upsilon]([B.sub.n]) = 3n + 1
(vi) For the wheel graph [W.sub.n], n [greater than or equal to] 3, [mu][W.sub.n] = 3, [upsilon]([W.sub.n]) = n + 2
Theorem 3.7 For any graph G, [m.sub.D](G) [less than or equal to]|D|[Delta](G), [for all]D [member of] D(G) and equality holds if and only if D is any independent dominating set in which each vertex has degree [Delta](G).
Proof: We first observe that the maximum value of [m.sub.D](G) occurs at an independent dominating set D of G and hence from the definition of [m.sub.D](G), we get [m.sub.D](G) [less than or equal to]|D|[Delta](G), [for all]D [member of] D(G). Suppose all the vertices in D has the maximum degree [Delta](G) then the maximum number of edges in [m.sub.D](G) is |D|[Delta](G), which completes the necessary part. For the converse, if [m.sub.D](G) [less than or equal to]|D|[Delta](G), [for all]D [member of] D(G) then [mu](G) = [upsilon](G) which gives D is an independent dominating set with each vertex has degree [Delta](G), the proof is complete.
Remark 3.8 The bound is attained, for the dominating set D = {[v.sub.2], [v.sub.5]} in the graph given in Example 3.3, since [m.sub.D](G) = 6 = |D|[Delta](G).
Corollary 3.9 For any graph G, (i) [m.sub.D](G) [less than or equal to]|D|(p - 1) (ii) [m.sub.D](G) [less than or equal to]|D| ([[alpha].sub.0] + [[beta].sub.0] - 1) and (iii) [m.sub.D](G) [less than or equal to]|D| ([[alpha].sub.1] + [[beta].sub.1] - 1) [for all]D [member of] D(G).
Proof: Since G is connected, we have [Delta]p - 1 then the results follows from Theorem 3.7 and Theorem2.2(ii).
Theorem 3.10 For any graph G, if D(G) consists of only the minimal dominating sets of G then [m.sub.D](G) [less than or equal to] [Gamma](G)(p - 1), [for all]D [member of] D(G) where [Gamma](G) is the maximum domination number of minimal dominating sets of G.
Proof: Let D be any minimal dominating set of G. Since |D|[less than or equal to][Gamma](G) then the result follows from Corollary 3.9(i).
Corollary 3.11 If G is a star graph then [upsilon](G) = p - 1.
Proof: Since for star graph [Gamma](G) = 1, and hence the result follows from Theorem 3.10 and from the definition of [upsilon](G).
Theorem 3.12 For any graph G, [m.sub.D](G) [greater than or equal to] [delta](G) and the equality holds if D = V\{v} with deg(v) = [delta](G) for v [member of] V.
Proof: If is any vertex with degree d. By taking the dominating set D = V\{v}, it clearly following that there will be d edges connecting D and V\D and hence [m.sub.D](G) = d [greater than or equal to] [delta](G); equality is attained when d = [delta](G).
Corollary 3.13 For any graph G [not equal to] [C,sub,3], V\{v} is a dominating set with deg(v) = [delta](G) if and only if (i)[mu](G) = [delta](G) and (ii) [upsilon](G) [greater than or equal to] [delta](G).
Proof: For the graph if V\{v} is a dominating set then by Theorem3.12, [m.sub.D](G) [greater than or equal to] [delta](G) which gives the results by using the definition of [mu](G) and [upsilon](G). For converse, if [mu](G) = [delta](G) and [upsilon](G) [greater than or equal to] [delta](G) then [m.sub.D](G) [greater than or equal to] [delta](G). Again the result follows from the same Theorem3.12.
Theorem 3.14 For any graph G, D = V\{v} is a dominating set with deg(v) = [delta](G) then [mu](G) [greater than or equal to] [delta](G) if diam(G) = 2.
Proof: It follows from Theorem 2.4 and Theorem 3.12.
Theorem 3.15 For any graph G [not equal to] [C,sub,3], [mu](G) = [m.sub.D](G) = [delta](G) if and only if D is maximal dominating set of G.
Proof: Assume that [mu](G) = [delta](G). Then from Theorem3.14, V\{v} is a dominating set with deg(v) = [delta](G). Now to prove that D = V\{v} is maximal dominating set. Suppose D is not a maximal dominating set of G then there exist another dominating set D' of G such that V [??] D' [??] D. Therefore there exist atleast an vertex u [not equal to] v in V such that D' = D [union] {u} is a dominating set. It gives either u = v or D' = V, which is a contradiction. Hence D is a maximal dominating set of G. For converse, assume that D = V\{v} since we excude D=V from D(G). Now to prove that deg(v) = [delta](G). Suppose deg(v) > [delta](G) then [m.sub.D](G) > [delta](G) and [mu](G) > [delta](G) which is a contradiction. Then the result follows from Theorem3.14.
Theorem 3.16 For any graph G, [m.sub.D](G) [greater than or equal to] [delta](G).
Proof: Let D be any dominating set of G. Then |D|[less than or equal to][Gamma](G). Since G is connected we have always |V\D|[less than or equal to]|D|. Hence the number of edges in [m.sub.D](G) is atleast |D| and hence [delta](G), which completes the proof.
Theorem 3.17 For any graph G [mu](G) = [gamma](G) if [gamma](G) = [delta](G).
Proof: Since [gamma](G) = [delta](G) then from Theorem3.16 and Remark3.2 (ii) we have [gamma](G) [less than or equal to] [m.sub.D](G) and [mu](G) [less than or equal to] [m.sub.D](G). Now to prove [mu](G) = [gamma](G). Since [mu](G) < [delta](G) is not possible and [mu](G) > [gamma](G) gives the minimum value of [m.sub.D](G) greater than [gamma](G) which is a contradiction since for [gamma](G) = [delta](G), the minimum value of [m.sub.D](G) is [gamma](G) and hence the result.
Corollary 3.18 For any graph G, if [gamma](G) = [delta](G) then (i) [mu](G) [greater than or equal to] p - q (ii) [mu](G) [greater than or equal to] [p/[Delta] + 1].
Proof: It follows from Theorem 2.1, Theorem 2.2(i) and Theorem 3.17.
Theorem 3.19 For any non-complete connected graph G, if D(G) consists only the split dominating sets of G with cardinality [[gamma].sub.s](G) then (i) [m.sub.D](G) [less than or equal to] [[alpha].sub.0][Delta](G), (ii) [m.sub.D](G) [less than or equal to] p[Delta].sup.2](G)/([Delta](G) + 1).
Proof: Let G be any non-complete connected graph and D [member of] D(G). From the hypothesis we have |D| = [[gamma].sub.s](G). By using Theorem3.7, [m.sub.D](G) [less than or equal to] [[gamma].sub.s](G)[Delta](G). Then the results follows from Theorem2.5.
Theorem 3.20 For any connected graph G, if D(G) consists only the non-split dominating sets of G with cardinality [[gamma].sub.ns](G) then (i) [m.sub.D](G) [less than or equal to] [[gamma].sub.ns](H)[Delta](G) where H is a spanning subgraph of G, (ii) [m.sub.D](G) [less than or equal to] (q - 2p + 1/2) [Delta](G), (iii) [m.sub.D](G) [less than or equal to](p - [omega](G) + 1)[Delta](G) where [omega](G) is the clique number of G.
Proof: Let G be a connected graph and D [member of] D(G). From the hypothesis we have |D| = [[gamma].sub.ns](G). By using Theorem3.7, [m.sub.D](G) [less than or equal to] [[gamma].sub.ns](G)[Delta](G). Then the results follows from Theorem2.6.
Theorem 3.21 If D(G) consists only the dominating sets with cardinality [Delta](G) then (i) For any non-complete connected graph G, [mu](G) [less than or equal to] [[gamma].sub.s](G) (ii) For any complete graph G, [mu](G) [less than or equal to] [[gamma].sub.ns](G).
Proof: Let D [member of] D(G). Then |D| = [Delta](G) = [gamma](G). By using Corollary3.17, [mu](G) = [gamma](G). Then the results follows from Theorem2.5(i) and Theorem2.6(i)
Theorem 3.22 If G is a graph of order p [greater than or equal to] 2, [gamma](G) = [delta](G) and [gamma]([bar.G]) = [delta]([bar.G]) then
(i) 3 [less than or equal to] [mu](G) + [mu]([bar.G]) [less than or equal to] p + 1
(ii) 2 [less than or equal to] [mu](G) + [mu]([bar.G]) [less than or equal to] p.
Proof: The result follows from Theorem 3.17 and Theorem 2.3
Theorem 3.23 For any dominating set D of G, [m.sub.D](G) = [summation over v[member of]D] deg(v) - [2q.sub.D] and [m.sub.D](G) = [summation over v[member of]V\D] deg(v) - [2q.sub.V\D] where [q.sub.D] and [q.sub.V\D] denote the number of edges in <D> and <V\D> respectively.
Proof: Let D be any dominating set of G and let [m.sub.D](G) = t. Since these edges contribute t/2 vertices to D and t/2 vertices to V\D , 1/2 [summation over v[member of]D] deg(v) represents the sum of the edges in the induced subgraph <D> and t/2 edges. Hence t/2 = 1/2 [summation over v[member of]D] deg(v) - [q.sub.D] and hence the result. The second result follows by the similar arguments.
Corollary 3.24 If D is any independent dominating set of G then [m.sub.D](G) = [summation over v[member of]D] deg(v).
Proof: Since D is an independent dominating set, the induced subgraph <D> does not contain any edge and hence the result follows from Theorem 3.23.
3.25 Algorithm for finding [m.sub.D](G) for the given dominating set D of G.
* Step 1 Compute the degree of each vertex v of G and store it in d(v).
* Step 2 Get the vertices of the given dominating set.
* Step 3 Find the sum of the degree of each vertex in D and store it in d (D).
* Step 4 Let q(D)=0.
* Step 5 For each edge e = uv, if both and are in D then increase q(D) by 1, repeat this process for all the edges in G.
* Step 6 Find m(D) = d(D) - 2q(D).
3.26 Illustration: Consider the graph in Example 3.4.
* Step 1. d([v.sub.1]) = 1,d([v.sub.2]) = 3,d([v.sub.3]) = 2,d([v.sub.4]) = 2,d([v.sub.5]) = 2,d([v.sub.6]) = 1.
* Step 2 Let D = {[v.sub.1], [v.sub.3], [v.sub.6]} be a dominating set.
* Step 3 d(D) = d([v.sub.2]) + d([v.sub.3]) + d([v.sub.6]) = 3 + 2 + 1 = 6
* Step 4 q (D) = 1
* Step 5 For [e.sub.2] = [v.sub.2][v.sub.3], q(D) becomes 1.
* Step 6 m(D) = d(D) - 2q(D) = 6 - 2 x 1 = 4.
REFERENCES
[1.] Acharya, B.D., Arumugam, S. and Slater,P.J.2007. Domination in discrete structures-New Directions- AKCE. J.Graphs and combin., 4 (No.2): 113-115, 2007.
[2.] Berge, C. 1973.Graphs and Hypergraphs--North Holland- Amsterdam1973.
[3.] Cokayne,E.J. and Hedetniemi,S.T.1977. Towards a theory of domination in graphs- Networks.- pp. 247-261- 1977.
[4.] B. Gayathri,B. and V. Mohanaselvi,V.2008. On co-edge tree domination and co-edge spanning tree domination in graphs, International Journal of Mathematics and Computer Science, Vol.27(No.1):39-44.
[5.] Harary,F. 1972. Graph Theory. Addison-wesley, Reading Mass., 1972.
[6.] Haynes,J.W., Hedetniemi,S.T. and Slater,P.J.1998. Fundamentals of domination in graphs- Marcel Dekkar Inc., New York--1998.
[7.] Kulli,V.R. and Janakiram,B.1997.The split domination number of a graph--Graph Theory Notes of New York XXXII--New York Academy of Sciences-pp. 16-19, 1997.
[8.] Kulli,V.R. and Janakiram,B.2000. The non-split domination number of a graph. Indian J. Pure and Appl. Math.31(4): 441-447, April 2000.
[9.] Ore,O. Theory of Graphs, Amer. Math. Soc. Colloq. Publi., 38, Providence, 1962.
[10.] Walikar,H.B., Acharya,B.D. and Sampathkumar,E. Recent developments in the theory of domination in graphs- M.R.I. Lecturer notes in Math. 1-Metha Research Institute- Allahabad- 1979.
B. Gayathri (1) and V. Mohanaselvi (2) P.G. & Research Department of Mathematics, Periyar E.V.R. College (Autonomous), Trichy--620 023,India, Email: maduraigayathri@gmail.com
(1) (S.G.) Lecturer,
(2) Lecturer in P.G. Department of Mathematics, Nehru Memorial College (Autonomous), Puthanampatti--621 007. Email:pathangjali@gmail.com AMS Subject Classification: 05C70, 05C05.
 Printer friendly
 Cite/link
 Email
 Feedback
| |
| Author: | Gayathri, B.; Mohanaselvi, V. |
|---|---|
| Publication: | Bulletin of Pure & Applied Sciences-Mathematics |
| Article Type: | Formula |
| Geographic Code: | 9INDI |
| Date: | Jan 1, 2009 |
| Words: | 3260 |
| Previous Article: | Integrability of certain cosine sum. |
| Next Article: | Perfect fuzzy graphs. |
| Topics: | |