Open Journal of Discrete Mathematics
Vol.2 No.3(2012), Article ID:21126,5 pages DOI:10.4236/ojdm.2012.23021

A Note on Edge-Domsaturation Number of a Graph

Devadhas Nidha, Murugan Kala

Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli, India

Email: nidhamaths@gmail.com, karthipyi91@yahoo.co.in

Received April 27, 2012; revised May 30, 2012; accepted June 12, 2012

Keywords: Edge-Dominating Set; Edge-Domination Number; ds'-Critical; Edge-Domsaturation Number; Well Edge Dominated Graph

ABSTRACT

The edge-domsaturation number ds'(G) of a graph G = (V, E) is the least positive integer k such that every edge of G lies in an edge dominating set of cardinality k. In this paper, we characterize unicyclic graphs G with ds'(G) = q – Δ'(G) + 1 and investigate well-edge dominated graphs. We further define γ'-critical, γ'+-critical, ds'-critical, ds'+-critical edges and study some of their properties.

1. Introduction

Throughout this paper, G denotes a graph with order p and size q. By a graph we mean a finite undirected graph without loops or multiple edges. For graph theoretic terms we refer Harary [1] and in particular, for terminology related to domination theory we refer Haynes et al. [2].

1.1. Definition

Let G = (V, E) be a graph. A subset D of E is said to be an edge dominating set if every edge in E-D is adjacent to at least one edge in D. An edge dominating set D is said to be a minimal edge dominating set if no proper subset of D is an edge dominating set of G. The edge domination number γ'(G) of a graph G equals the minimum cardinality of an edge dominating set of G. An edge dominating set of G with cardinality γ'(G) is called a γ'(G)-set or γ'-set.

Acharya [3] introduced the concept of domsaturation number ds(G) of a graph. For any graph G of order p, and for any integer r such that γ(G) ≤ r ≤ p, we call the set the r-level domination core of G. We say that G is r-level domination-saturated (or in short, “r-domsaturated”) if DCr(G) – V(G). The domsaturation number ds(G) is then defined by. Arumugam and Kala [4] observed that for any graph G, or and obtained several results on ds(G). We now extend the concept of domsaturation number of a graph to edges.

1.2. Definition

The least positive integer k such that every edge of G lies in an edge dominating set of cardinality k is called the edge-domsaturation number of G and is denoted by ds'(G).

If G is a graph with edge set E and D is a γ'-set of G, then for any edge e Î E-D, is also an edge dominating set and hence or.

Thus we have the following definition.

1.3. Definition

A graph G is said to be of class 1 or class 2 according as or.

1.4. Definition

An edge e of G is

1) γ'-critical if;

2) γ'+-critical if;

3) γ'-critical if;

4) γ'-fixed if every γ'-set contains e;

5) γ'-free if there exists γ'-sets containing e and also γ'-sets not containing e;

6) γ'-totally free if there is no γ'-set containing e.

We use the following theorem.

1.5. Theorem [5]

For any connected unicyclic graph with cycle C, if and only if one of the following holds.

1);

2), for all vertices w not on C and for at most one vertex w not on C;

3) all the vertices not on C adjacent to u1 have degree at most 2 and all vertices whose distance from u1 is 2 are pendent vertices;

4) and all vertices not on C are pendent vertices;

5);

6), either exactly one vertex of C has degree at least 3 and all vertices not on C are pendent vertices.

2. Main Results

2.1. Lemma

An edge e of G is γ'-critical if and only if

Proof

For any edge e, we observe that or or. Now, suppose e is γ'-critical. Then. Hence. The converse is obvious.

2.2. Theorem

An edge e is γ'-critical if and only if

(1)

for some γ'-set D containing e.

Proof

If e is γ'-critical, by lemma 2.1. Let S be a γ'-set of G – e. If S contains an edge of N(e), then S will be an edge dominating set of G and hence, a contradiction. Thus S does not contain any edge of N(e). Since, is a γ'-set of G and so Equation (1) holds. Conversely, suppose e is an edge such that (1) is true. Then G – e is an edge dominating set of G – e and hence. Thus e is γ'-critical.

2.3. Theorem

Let G be a graph without isolated edges. An edge e in G is γ'-critical if and only if 1) e is γ'-free, and 2) no γ'-set of G – e contains any edge of N(e).

Proof

If e is γ'-critical, then by Lemma 2.1. As in theorem 2.2, if S is any γ'-set of G – e, then S will not contain any edge of N(e) and is a γ'- set of G for every. This implies that e is γ'-free. Conversely, suppose (1) and (2) are true. Let S be a γ'- set of G – e. By (2) S does not contain any edge of N[e]. Hence S cannot be an edge dominating set of G. But, for any edge, is an edge dominating set of G. Since S is a minimum edge dominating set for G – e, is also a minimum edge dominating set for G and hence. Thus e is γ'-critical.

2.4. Theorem

Let G be a graph and. Then

1) e is γ'-fixed if and only if there exists no edge dominating set of G – e with γ'(G) edges which is also an edge dominating set of G.

2) e is γ'-totally free if and only if every γ'-set of G is a γ'-set of G – e.

Proof

1) Assume that e is γ'-fixed. Suppose there exists an edge dominating set S of G – e with which is also an edge dominating set of G. Then S is a γ'-set not containing e which is impossible as e is γ'-fixed. The converse is obvious.

2) Let e be γ'-totally free. Then e does not belong to any γ'-set of G and so every γ'-set D of G is an edge dominating set of G – e. Thus. If, then by theorem 2.3, e is γ'-free and so, D is a γ'-set of G – e. The converse is obvious.

2.5. Theorem

Let G be a connected graph. If a cut edge e of G is γ'- fixed, then e is γ'+-critical

Proof

Let S be a γ'-set of G. Let e be a cut edge that is γ'- fixed. Then e belongs to every γ'-set. Since e is a cut edge, G – e is a disconnected graph with at least two components G' and. Let e' and e" be the neighbors of e in G' and G" respectively. Therefore is a minimum edge dominating set of G – e so that. Hence e is γ'+-critical.

2.6. Theorem

An edge e in a graph G is γ'+-critical if and only if 1) e is not isolated edge 2) e is γ'-fixed and 3) There is no edge dominating set for having γ'(G) edges which also dominates N[e].

Proof

If e is γ'+-critical, then, by lemma 2.1. Clearly e is not an isolated edge. If S is a γ'-set of having γ'(G) edges which also dominates N(e) then, a contradiction. Thus no edge dominating set of having γ'(G) edges can dominate N(e). By Theorem 2.4, e is γ'-fixed. The converse is obvious.

We now investigate relationships between, γ'-free edges, γ'-totally free edges and graphs which are class 1 and class 2.

2.7. Theorem

If G is a graph without isolated edges, then G is of class 2 if and only if G has γ'-totally free edges.

Proof

Suppose G has a γ'-totally free edge e. By Theorem 2.4 (2), G is of class 2. Conversely, suppose G is of class 2. Then there exists an edge e which is not in any γ'-set. Hence every γ'-set of G is also a γ'-set of G – e so that e is γ'-totally free.

2.8. Theorem

Proof

Let G be a connected graph. If G has a γ'-fixed edge, then it has a γ'-totally free edge.

Suppose G has a γ'-fixed edge e. Then e belongs to every γ'-set.

Claim: No neighbor of e belongs to any γ'-set of G. Suppose at least one of its neighbor say e' belongs to a γ'- set D. Let and e' be incident with u. Then, where e" is any edge incident with v is an edge dominating set of G – e with γ'-edges which is also an edge dominating set of G. But by Theorem 2.6, this is a contradiction, since e is a γ'-fixed edge. Therefore no neighbor of e belongs to any γ'-set of G. Thus neighbors of e are all γ'-totally free in G.

We now investigate the class of graphs which are ds'+, ds'-critical.

2.9. Lemma

Let e Î E(G). If e is γ'-totally free and G – e is of class 1, then.

Proof

Since e is γ'-totally free, by Theorem 2.4,

(1)

Since e is γ'-totally free, by Theorem 2.3, G is of class 2 and so

(2)

Since G – e is of class 1, we have

(3)

From Equations (1), (2) and (3), we have

.

2.10. Lemma

Let. If e is γ'-totally free and G – e is of class 2, then.

Proof

If e is γ'-totally free, then by Theorem 2.4,

(1)

Since G and G – e are of class 2, we have

(2)

and

(3)

From equations (1), (2) and (3), we have

.

2.11. Lemma

Let e be an edge of G. If e is γ'-free and G – e is of class 1, then or.

Proof

Suppose e is a γ'-free edge. In any case G is either of class 1 or class 2.

Case (1). G is of class 1.

Let S be a γ'-set of G – e. If S does not contain any neighbor of e, then every neighbor of e is γ'-totally free in G – e. This implies that G – e is of class 2. But this is a contradiction and so S must contain a neighbor of e. Then by theorem 2.4,. Since G and G – e are of class 1, we have

.

Case (2). G is of class 2.

Since G – e is of class 1, then by a similar argument, S must contain a neighbor of e. Since G is of class 2, we have.

2.12. Lemma

Let e be an edge of G. If e is γ'-free and G – e is of class 2, then, or.

Proof

Case (1). G is of class 1.

Let S be a γ'-set of G – e. We have the following cases:

Subcase (1). S contains a neighbor of e.

Now. Since G is of class 1 and G – e is of class 2, we have.

Subcase (2). S does not contain a neighbor of e.

Now. Since G – e is of class 2 and G is of class 1, we have.

Case (2). G is of class 2.

By an argument similar to that in case (1), we have or.

2.13. Lemma

Let e be an edge of G. If e is γ'-fixed and G – e is of class 1, then.

Proof

If e is γ'-fixed, then by Theorem 2.8, all of its neighbors are γ'-totally free. Then by Theorem 2.7, G is of class 2 and hence

(1)

As e is γ'-fixed, by Theorem 2.4,. If, then e is γ'-critical. Then by Lemma 2.11, e is γ'-free and this is a contradiction. Therefore. Since G is of class 2 and G – e is of class 1, we have.

2.14. Lemma

Let. If e is γ'-fixed and G – e is of class 2, then.

Proof

By an argument analogous to that in Lemma 2.13, since G – e is of class 2, we have.

2.15. Theorem

Let G be a graph without isolated edges. An edge e in G is ds'-critical if and only if one of the following holds.

1) e is γ'-totally free and G – e is of class 1.

2) e is γ'-free, G is of class 2 and G – e is of class 1.

3) e is γ'-free and both G and G – e are of class 2.

Proof

Suppose e is ds'-critical. Then

(1)

Let S be a γ'-set of G. Then we have the following cases:

Case (1). G and G – e are of class 1.

By (1),. By theorem 2.3, e is γ'- free and no γ'-set of G-e contains any edge of N(e). Now every neighbor of e is γ'-totally free in G – e. Therefore G – e is of class 2, which is a contradiction.

Case (2). G is of class 1 and G – e is of class 2.

Then Equation (1) becomes. But this is not possible.

Case (3). G is of class 2 and G – e is of class 1.

Then Equation (1) becomes. Then either e is γ'-free or γ'-totally free.

Case (4). G and G – e are of class 2.

In this case, Equation (1) becomes. Then by theorem 2.3, e is γ'-free.

From Lemmas 2.9, 2.11 and 2.12, the converse is true.

2.16. Theorem

Let G be a graph without isolated edges. An edge e in G is ds'+-critical if and only if one of the following holds.

1) e is γ'-free, G is of class 1 and G – e is of class 2.

2) e is γ'-fixed and G – e is of class 2.

Proof

Suppose e in G is ds'+-critical. Hence

(1)

Let S be a γ'-set of G. Then we have the following cases:

Case (1). G and G-e are of class 1.

From equation (1) and so G is γ'+-critical. Hence by Theorem 2.6, e is γ'-fixed, which is a contradiction.

Case (2). G is of class 1 and G – e is of class 2.

Now equation (1) becomes. Then S must contain a neighbor of e. Since G is of class 1, e is γ'-free.

Case (3). G is of class 2 and G – e is of class 1.

Then Equation (1) becomes, which is not possible.

Case (4). G is of class 2 and G – e is of class 2.

In this case, Equation (1) becomes. Then by Theorem 2.4, e is γ'-fixed.

Conversely, suppose if (1) or (2) is true. Then by case (1) of Lemma 2.12 and Lemma 2.14, the result follows.

3. Edge-Domsaturation Number of a Graph

Theorem

For any connected unicyclic graph with cycle C, if and only if one of the following holds.

1)

, and there exists

such that, i = 1, 2.

2) , exactly one vertex w not on C has and remaining vertices are pendent vertices.

Proof

Suppose.

Let be the unique cycle in G.

If, then for all n ≥ 3 and so.

Let S denote the set of all pendent edges of G and let.

Claim 1:. Since is an edge dominating set for any edge e of C,. For any pendent edge f, is an edge dominating set of G containing f. Here g is an edge adjacent to f and e is any edge of the cycle. Hence, so that.

Claim 2: e = uv is an edge with degree ∆'. Then either u or v lies on Ck.

Now let and be an edge of maximum degree ∆'. If e Î Ck, then for some edge  is a tree T of G with at least pendent edges. If X is the set of all pendent edges of G – e, then . Then is an edge dominating set of cardinality at most. Therefore , which is a contradiction.

Case (1). u or v lies on C.

Claim 3: is the union of P1 and P2. Suppose not. Then, contains. Suppose lies on CK. Let be the maximal tree rooted at u1 not containing any edge of Ck. Clearly has at least ∆'(G) – 2 pendent edges, say S. Then

is an edge dominating set of cardinality less than. Therefore, which is a contradiction.

In this case, G has at least ∆' – 2 pendent edges. Let W be the set of these pendent edges. Further  and let Y denote a γ'-set of Ck. Let. If k > 4, then is an edge dominating set of cardinality less than Hence or. Since. By claim 1,.

Subcase (1).

is the union of P1 and P2. Also u or v lies on C. Let. Therefore contains at least one P2. Since, no other vertex other than u and v has degree > 3.

If G – C3 is the union of alone, then or is an edge dominating set and every edge lies in a γ'-set. Therefore.

If is the union of and, then from Theorem 1.5,. But pendent edges adjacent to u1 does not lie in any γ'-set. Therefore.

Subcase (2).

As in subcase (1), G – C4 also contains P2. Then is an edge dominating set of cardinality. Therefore.

Case (2). u and v lies on C.

Claim 4: G – Ck is the union of P1 and P2.

Suppose not. Then, G – Ck contains . Suppose lies on Ck. Let .

Clearly has at least pendent edges, say P.

Then is an edge dominating set of cardinality less than. Therefore, which is a contradiction.

As in case (1),. Let be an edge of maximum degree.

Subcase (1).

In this case, from Theorem 1.5, (3), u3u1 does not belong to any γ'-set. Therefore.

Subcase (2).

From Theorem 1.5, there does not exist an edge dominating set of cardinality.

The converse is obvious.

4. Well-Edge Dominated Graph

A graph G is called well dominated if all minimal dominating sets have the same cardinality. This concept was introduced by Finbow, Hartnell and Nowakowski [6].

4.1. Definition

A graph G is well-edge dominated if every minimal edge dominating set of G has the same cardinality.

4.2. Lemma

If G is a well-edge dominated graph and e is an edge of G, then there exists a minimum edge dominating set containing e and a minimum edge dominating set not containing e.

Proof

To obtain an edge dominating set containing e, place e in the set D, delete from G and continue in this greedy fashion until there are no edges left. Then D is minimal and since G is well-edge dominated, it is minimum.

To obtain a minimum edge dominating set not containing e, we use the same greedy method except that we use a neighbor of e as our initial edge in D.

4.3. Theorem

If G is well-edge dominated, then G is of class 1.

Proof

From the above lemma, it is clear that every edge belongs to any one of the γ'-set. Therefore G is of class 1.

REFERENCES

  1. F. Harary, “Graph Theory,” Addison-Wesley Publishing Company, Boston, 1969.
  2. T. W. Haynes, S. T. Hedetniemi and P. J. Slater, “Fundamentals of Domination in Graphs,” Marcel Dekker, New York, 1998.
  3. B. D. Acharya, “The Strong Domination Number of a Graph and Related Concepts,” Journal of Mathematical Physics, Vol. 14, No. 5, 1980, pp. 471-475.
  4. S. Arumugam and R. Kala, “Domsaturation Number of a Graph,” Indian Journal of Pure and Applied Mathematics, Vol. 33, No. 11, 2002, pp. 1671-1676.
  5. S. Arumugam and S. Velammal, “Edge Domination in Graphs,” Taiwanese Journal of Mathematics, Vol. 2, No. 2, 1998, pp. 173-179.
  6. A. Finbow, B. L. Hartnell and R. Nowakowski, “Well Dominated Graphs: A Collection of Covered Ones,” Ars Combinatoria, Vol. 25, No. A, 1988, pp. 5-10.