Some Results of Domination Theory on Graph

The total number of dominance is determined when a factor is complete and the other factor is determined in a loop. Given that the exact problem is usually very complicated, it is also important to consider that the overall dominance of the product is far below and below in terms of its factors invariant. In [2, 11] there have been two such lower limitations. The total number of factors to regulate the dominance number of a commodity can, on the other hand, be used, cf. [1, 11] In a particular case, the upper limit of the overall product supremacy is also found, involving a total of 2-times the number of factors dominating the product. We demonstrate how one can take the approach of bounding in terms of the {2} - dominance of factors the dominant number of direct products of graphs. We do add some of the definitions and notations required in the paper to ease the reading of the paper. The distance of two vertices u , v in graph G, referred to as d(u, v), is the longest single u −v path in G. We say u and v are adjacent to d(u, v)=1. The ecc(u) distance from the farthest vertex is the eccentriticity of an ecc(u), i.e.,

The diameter of G, diam (G), is the maximum eccentricity. The set of vertices at distance k from a vertex v in G is called the k-neighborhood of v and is denoted by Nk(v). That is, Incase k = 1 we shall refer to it as the neighborhood of v or open neighborhood. Inthis case we shall denote it, as usual, N (v), while N[v] = N (v) ∪ {v}. A vertex v in G is said to dominate itself and each of its neighbors. A set S ⊆ V (G) is domination set if every vertex of G is dominated by some vertex of S. This line includes the notion of stepping dominion and results in [2,4]. A set S = {v1, v2, .... ,vt} of vertical graph G is known as a step domination set for G if the non-negative integral k1, k2, ... ,kt exist to form a partition of V (G) in the set {Nki(vi)}. This partition is referred to as the S step dominance partition. The K = (k1, k2... kt), k1k2 ••• kt is referred to as an S-associated distance dominance sequence, while the ki is called the vi steps and stK (vi) = st(vi) = Ki when no uncertainty exists. This time, we say, too, that ki is labelled with the vertex vi. It is said that each U vertex in Nki(vi) is regulated by vi and vi and u is dominated by vi. We suppose that Nki(vi) is not vacant in the above descriptions. For any integer ki in K, 0ki ecc(vi) therefore. Provided that a vertex cannot dominate both itself and other vertices during a step dominance set S, the cardinality of a step dominance set for G is at least 2 except G = K1.On the other hand, |S||V (G)|. Let G be a V (G) = {v1, v2... vn} graph. Then the set {N0(vi)} n i=1 will obviously be a step dominance partition of V(G) with S = V(G). Each graph has a certain degree of dominance. This leads us to a

defined and satisfies With S(K1) = 1. Recently, a full characterization of the step-domination number of graphs of diameter at most two was obtained in [1]. In [2] it was shown that if T is a tree then wheren denotes the number of vertices of T. The main goal of this paper is to improve the result (2) by showing that whereD denotes the diameter of T. In additionwe show that if some requirements are imposed ona tree T with diameter D, then, S(T )O(D), which leads us toward the following conjecture: Conjecture 1.1. Let T be any tree. Then,

The open area for the vertex G = (V, E) with a V-shaped vertex, and the edge set v ∈ V is N(v) = {u ∈ V | uv∈ E} and the closed area is N[v] = N(v) {v}. In μ (G), the smallest grade G, i.e. δ(G) = minv |N(v)| is indicated. If a set of S ⊆ V is adjacent to at least one vertex of S, a set of S ⊆ V is a dominant set. The μ(G) of G dominance is the minimum of a predominant set cardinality. Likewise, if every vertex of V adjacent to at least one vertex of S, S ⊆ V is the complete dominating set. The total αt(G) dominance is the minimum cardinality of the dominant total set. The graph is let G = (V , E). The weight of f is w(f) = P v amounts P f(v) for a real-valued function: V os R; and for S os f(S) = violet f(v), so w(f) = f (V). Let k = 1, then f: V = {0, 1,. Let k , k}is known as {k}-dominant if, for each v, it is k {v}, it is k {k}-dominating function. The {k} – μ {k} (g) dominant number of a G-dominating function is the minimum weight of {k}. f: V {0 , 1,. Similarly, .k {k} is a complete function {k}-dominant if there is V f(N(v)) {k} for each v {f}. The {k}-domination {k} t(G) is the minimum weight of a complete dominant function {k}. The following definition has been is in S with a minimum of k − 1 in S or v is in V \ S with a minimum of k neighbours in S. The β-tuple (to-k) (G) dominance of the k-tuple dominating set is the minimal cardinality of G. Please note that μt(G) in μl (including in the list of references 2)(G). S N(v) S Total k-tuples dominant G, if at least k of the S neighbours is dominated by any vertex v > THE V,) THEY S THEY K. The total k-tuple domination number γ (×k) t is the minimum cardinality of a total k-tuple dominating set of G. The 2-packing number ρ(G) of a graph G is the maximum cardinality of a vertex subset X of G such that N[u] ∩ N[v] = ∅ for any different vertices u, v ∈ X. An open packing of a graph G is a set S of vertices such that the sets N(x), x ∈ S, are pairwise disjoint. The open packing number ρ ◦ (G) is the maximal cardinality of an open packing on G. Finally, recall that the direct product G × H is the graph defined by V (G×H) = V (G)×V (H) and two vertices (g1, h1) and (g2, h2) are adjacent if and only if g1g2 and h1h2 are edges of G and H, respectively. Let g be a vertex of G, then the subgraph of G × H induced by {g} × V (H) is called a fiber and denoted gH. Similarly one defines the fiber Gh for a vertex h of H. Note that if the factors graphs are without loops, then the fibers of their direct product are discrete. Note also that the direct product is commutative and associative; for more information on the direct product.

Let G and H be graphs with no isolated vertices. Then Rall [11] proved the following lower bound: While El-Zahar, Gravier, and Klobuˇcar [2] followed with: None of the bounds (1) and (2) follows from the other. For this sake note that for n ≥ 3, ρ ◦ (Kn) = 1, γt(Kn) = 2, so (1) gives γt(Kn × Kn) ≥ 2 while (2) implies γt(Kn × Kn) ≥ 3. (In fact, γt(Kn × Kn) = 3 for n ≥ 3, cf. [1].) On the other hand, for any n ≥ 2, ρ ◦ (K1,n) = 2, γt(K1,n) = 2, so (1) gives γt(K1,n × K1,n) ≥ 4 while (2) only gives γt(K1,n × K1,n) ≥ 3. We now give another lower bound on the total domination number of direct products. Theorem 3.1. For any nontrivial connected graphs G and H we have Proof. Let S be a minimum total dominating set of G × H. Define an integer function f on V (G) with We claim that f is a total {2}-dominating function of G. Let u be an arbitrary vertex of G and let V (H) = {v1, . . . ,vn}. Recall that H is nontrivial, hence n ≥ 2. Since S is a total dominating set, there exists a vertex (x, vi) that dominates (u, v1). Note that x 6= u and i 6= 1. Consider the vertex (u, vi). It is dominated by some vertex (y, vj ), where y 6= u and j 6= i. If x = y, then since i 6= j we have f(x) = 2, and hence f(N(u)) ≥ 2. And if x 6= y, then f(x) ≥ 1, f(y) ≥ 1, and therefore f(N(u)) ≥ 2 again. Thus f is a total {2}-dominating function of G with w(f) ≤ |S|, hence γt(G×H) ≥ γ {2} t (G). By the commutatively of the direct product the inequality follows. To see that the lower bound (3) can be simultaneously better than (1) and (2) consider the following example. For n ≥ 3, let Mn be the graph obtained from n copies of K3 such that in each copy one vertex is selected and these vertices are then identified. Then we have ρ ◦ (Mn) = 1, γt(Mn) = 2, and γ {2} t (Mn) = 4. Then (3) gives γt(Mn × Mn) ≥ 4, while (2) implies γt(Mn × Mn) ≥ 3 and (1) γt(Mn × Mn) ≥ 2. On the other hand, suppose that ρ ◦ (G) ≥ 2. Then hence (3) follows from (1) as soon as ρ ◦ (G) ≥ 2. It would be nice to have a lower bound that would cover the three above bounds. However the provided examples show that this task might be difficult.

P roof.Let S = {s1, . . . ,sk} be a minimum total 2-tuple dominating set of G and let {v1, . . . , vn} be the vertex set of Kn. We claim that T = {(si , vi) | i = 1, . . . , k} is a minimum total dominating set of G × Kn. Note first that T is well defined since n ≥ γ (×2) t (G) = k. Let (x, vt) be an arbitrary vertex of G × Kn and assume that x is dominated by vertices si and sj . Then si ,sj and x are pairwise different vertices. Suppose withoutloss of generality that t 6= i. Then (x, vt) is dominated by (si, vi), and so T isa total dominating set of G×Kn. We conclude that γt(G×Kn) ≤γ(×2)t(G).

Clearly, by Theorem 3.2. On the other hand, the lower bound easily follows from (2). Using inequality (4) we next construct examples where the lower bound (2) is optimal. Let Gn be the graph obtained from the complete graph Kn by adding a vertex xe for each edge e = uv of Kn, and joining xe with u and v. (See Figure 1 where G4 is drawn.)

We claim that for n ≥ 3, γt(Gn × Kn) = n. It is easy to check that γ (×2) t (Gn) = n, hence by (4), γt(Gn × Kn) ≤ n. On the other hand, (2) implies that for any n ≥ 3, We conclude this section with one more lower bound. We don‘t know whether (5) eventually follows from (1). However, for a given graph G it might be easier to evaluate γ (×2) t (G) than ρ◦ (G) and γt(G). Moreover, the below proof technique is somehow nonstandard and might be useful in other situations.

Recently, quite some attention has been drawn to the complete dominance number γt of the direct product of graphs. The primary objective is to precisely evaluate this invariant graph for direct products. The key outcome is that βt(T = H) = т(T)αt(H) = μt(T) μt(T) without isolated vertices for any tree T with at least one edge and any graph with H. For graphs with the same total dominance and open packing number, the same result is also valid. This helps us to alternate in particular.

Dominating direct products of graphs, submitted. [2] M.El-Zahar, S. Gravier and A. Klobuˇcar, (2004) On the total domination of cross products of graphs, Les Cahiers du laboratoire Leibniz, no. 97. [3] F. Harary and T.W. Haynes, (2000) Double domination in graphs, ArsCombin. 55 pp. 201–213. [4] T.W. Haynes, S.T. Hedetniemi and P.J. Slater (eds), (1998) Fundamentals of Domination in Graphs (Marcel Dekker, Inc. New York). [5] W. Imrich, (1998) Factoring cardinal product graphs in polynomial time, Discrete Math. 192 pp. 119–144. [6] W. Imrich and S. Klavˇzar, (2000) Product Graphs: Structure and Recognition (J. Wiley & Sons, New York). [7] P.K. Jha, S. Klavˇzar and B. Zmazek, (1997) Isomorphic components of Kronecker product of bipartite graphs, Discuss. Math. Graph Theory 17 pp. 301–309. [8] R. Klasing and C. Laforest, (2004) Hardness results and approximation algorithms of k-tuple domination in graphs, Inform. Process.Lett. 89 pp. 75–83. [9] C.S. Liao and G.J. Chang, (2002) Algorithmic aspect of k-tuple domination in graphs, Taiwanese J. Math. 6 pp. 415–420. [10] R. Nowakowski and D. F. Rall, (1996) Associative graph products and their independence, domination and coloring numbers, Discuss. Math. Graph Theory 16 pp. 53–79. [11] D.F. Rall, (2005) Total domination in categorical products of graphs, Discuss. Math. Graph Theory 25 pp. 35–44. [12] P.M. Weichsel, (1962) The Kronecker product of graphs, Proc. Amer. Math. Soc. 13 pp. 47–52. [13] Y. Caro, A. Lev, Y. Roditty, (2003) Some results in step domination, ArsCombin. 68 pp. 105–114. [14] G. Chartrand, M. Jacobson, E. Kubicka, G. Kubicki, The step domination number of a graph, Scientia, to appear. [16] K. Schultz, (2000) Step dominationingraphs, ArsCombin. 55 pp. 65–79. [17] D. West, (1996) Introduction to Graph Theory, Prentice-Hall, Englewood Cliffs, NJ.

Assistant professor of mathematics, Sri Mahadeshwara Govt. First Grade College Kollegal, Chamaraja nagar District -571440 mnswamy1974@gmail.com