Printer Friendly

Some bounds on domination related parameters.

1. INTRODUCTION

By 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.
COPYRIGHT 2009 A.K. Sharma, Ed & Pub
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
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:


Related Articles
FORMULA ONE: Montoyaeyes drivers' crown.
FORMULA ONE: Trulli: F1 lifted.
Formula One: Frank flogs jet in title bid.
Motor Racing: FRANK PUTS WIND UP FERRARI.
the Razz: Cats are so hot; tartan heart 2008 belladrum festival.
Button reaps just rewards.
Cowell & Green to take X Factor to Vegas.
Cowell & Green to take X Factor to Vegas.
Cowell & Green to take X Factor to Vegas.

Terms of use | Privacy policy | Copyright © 2022 Farlex, Inc. | Feedback | For webmasters |