New parameters on inverse domination

Chia sẻ: Nguyễn Thảo | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

7
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

A set D of vertices in a graph G(V, E) is a dominating set of G, if every vertex of V not in D is adjacent to at least one vertex in D. A dominating set D of G(V, E)is a k – fair dominating set of G, for

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: New parameters on inverse domination

International Journal of Mechanical Engineering and Technology (IJMET) Volume 10, Issue 03, March 2019, pp. 1111-1116. Article ID: IJMET_10_03_113 Available online at http://www.iaeme.com/ijmet/issues.asp?JType=IJMET&VType=10&IType=3 ISSN Print: 0976-6340 and ISSN Online: 0976-6359 © IAEME Publication Scopus Indexed NEW PARAMETERS ON INVERSE DOMINATION Jayasree T G Adi Shankara Institute of Engineering and Technology, Kalady, Kerala. Radha Rajamani Iyer Department of Mathematics, Amrita School of Engineering, Coimbatore, Amrita Viswa Vidyapeetham, India. ABSTRACT A set D of vertices in a graph G(V, E) is a dominating set of G, if every vertex of V not in D is adjacent to at least one vertex in D. A dominating set D of G(V, E)is a k – fair dominating set of G, for 𝑘 ≥ 1 if every vertex in V – D is adjacent to exactly k vertices in D. The k – fair domination number 𝛾𝑘𝑓𝑑 (𝐺) of G is the minimum cardinality of a k – fair dominating set. In this article, we define the inverse of the k – fair domination number and try to find it for some class of graphs. Key words: Fair Domination, Inverse Domination, Inverse of k-fd set. Mathematics Subject Classification: 05C69. Cite this Article Jayasree T G and Radha Rajamani Iyer, New Parameters on Inverse Domination, International Journal of Mechanical Engineering and Technology, 10(3), 2019, pp. 1111-1116. http://www.iaeme.com/IJMET/issues.asp?JType=IJMET&VType=10&IType=3 1. INTRODUCTION Let G(V, E) be a simple graph with vertex set V(G) and edge set E(G). The order and size of G are denoted by n and m respectively. For graph theoretic terminology we refer to Gary Chartrand and Ping Zhang [10] and Haynes et al. [11, 12]. For any vertex 𝑣 ∈ 𝑉, the open neighborhood N(v) is the set {𝑢 ∈ 𝑉: 𝑢𝑣 ∈ 𝐸}, and the closed neighborhood N[v] is the set 𝑁(𝑣) ∪ {𝑣}. For any 𝑆 ⊆ 𝑉, 𝑁(𝑆) = ⋃𝑣∈𝑆 𝑁(𝑣) and 𝑁[𝑆] = 𝑁(𝑆) ∪ 𝑆. A set D of vertices in a graph G(V, E) is a dominating set of G, if every vertex of V not in D is adjacent to at least one vertex in D. Let D be a minimum dominating set of G. If V - D contains a dominating set say D' is called an inverse dominating set with respect to D. The inverse domination number 𝛾 ′ (𝐺) of G is the order of a smallest inverse dominating set of G. A fair dominating set in graph G(V, E) is a dominating set D such that all vertices not in D are dominated by same number of vertices from D, that is, every two vertices not in D has same http://www.iaeme.com/IJMET/index.asp 1111 editor@iaeme.com
New Parameters on Inverse Domination number of neighbors in D. The fair domination number 𝛾𝑓𝑑 (𝐺) of G is the minimum cardinality of an fd-set. A dominating set 𝐷 ⊆ 𝑉(𝐺) is a k-fd set in G, if for every two distinct vertices 𝑢, 𝑣 ∈ 𝑉 − 𝐷 , |𝑁(𝑢) ∩ 𝐷| = | 𝑁(𝑣) ∩ 𝐷| = 𝑘. That is, every two distinct vertices not in D have exactly k neighbors from D. Now, let as define the inverse of k-fair dominating set and the inverse of k-fair domination number as follows. Definition: A set S of vertices in a graph G (V, E) is a k-fair dominating set of G, if every vertex of V not in S is adjacent to exactly k vertices in S. Let S be a minimum k-fair dominating set of G. If V - S contains a set say S ' called an inverse k-fair dominating set with respect to S, if every vertex not in S ', is adjacent to at least k vertices in S '. The inverse k-fair domination number 𝛾𝑘𝑓𝑑 ′(𝐺) of G is the order of a smallest inverse k-fair dominating set of G. The following results are obvious. ′ 1. For complete graph 𝐾𝑛 , 𝛾1𝑓𝑑 (𝐾𝑛 ) = 𝛾1𝑓𝑑 (𝐾𝑛 ) = 1 . 2. For complete bipartite graph 𝐾𝑚,𝑛 , 𝛾1𝑓𝑑 (𝐾𝑚,𝑛 ) = 𝛾1𝑓𝑑 ′ (𝐾𝑚,𝑛 ) = 2. 3. Let S be a 𝛾1𝑓𝑑 - set of a connected graph G. If 𝛾1𝑓𝑑 ′ - set exists, then G has at least two vertices. 4. Let G be a connected graph with 𝛾(𝐺) = 𝛾1𝑓𝑑 (𝐺), then 𝛾1𝑓𝑑 ′ (𝐺) = 𝛾 ′ (𝐺). 5. Let G be a connected graph, then 𝛾𝑘𝑓𝑑 (𝐺) always depends on Δ(𝐺) and 𝛾𝑘𝑓𝑑 ′ (𝐺) depends on 𝛿(𝐺). In other words, for k-fair domination, 𝑘 ≤ Δ and for inverse k-fair domination, 𝑘 ≤ 𝛿. 𝑛 Lemma: Let 𝐾𝑛 be a complete graph of order n and let k be a positive integer with 𝑘 ≤ ⌊ 2⌋, then 𝛾𝑘𝑓𝑑 ′ (𝐾𝑛 ) = 𝑘. Proof: As we have, 𝐾𝑛 be a complete graph of order n, there exist k-fd sets for all 𝑘 ≤ (𝑛 − 1), with 𝛾𝑘𝑓𝑑 (𝐾𝑛 ) = 𝑘 for all 𝑛 ≥ 2. But 𝛾- set and 𝛾 ′ -set forms partition of vertex set and in a complete graph, 2- distinct vertices are connected by edges, if there is a k-fd set, the inverse set can have at the most (n - k) vertices. Hence for the maximum case, k = (n - k). In 𝑛 𝑛 other words, 𝑘 = 2 , or in general, 𝑘 ≤ ⌊ 2⌋. Then the result follows. 2. INVERSE DOMINATION IN 1-FD SETS In this section we can find inverse fair domination in paths and trees, because in both cases we can’t expect higher order inverse fair domination as 𝛿 = 1. 𝑛 Theorem: Let 𝑃𝑛 be a path with 𝑛 ≥ 2 vertices. Then 𝛾1𝑓𝑑 (𝑃𝑛 ) = ⌈ 3⌉ and 𝛾1𝑓𝑑 ′ (𝑃𝑛 ) = 𝑛+1 ⌈ ⌉. 3 Proof: Let 𝑃𝑛 be a path with 𝑛 ≥ 2 vertices. To dominate n vertices exactly by one vertex, 𝑛 we need 3 vertices. This is true for any n, which is a multiple of 3. For each additional vertex 𝑛 we need one more vertex for fair domination. This lead to the result 𝛾1𝑓𝑑 (𝑃𝑛 ) = ⌈ 3⌉ . 𝑛+1 Now, 1-fd set and its inverse are mutually disjoint sets, the result 𝛾1𝑓𝑑 ′ (𝑃𝑛 ) = ⌈ 3 ⌉ follows. Now, consider the case of trees. We refer Yair Caro, et.al [9] for the following notation. A vertex of degree one is called a leaf and its neighbor is called a support vertex. Let 𝑆𝑇 , denote http://www.iaeme.com/IJMET/index.asp 1112 editor@iaeme.com
Jayasree T G and Radha Rajamani Iyer the set of all support vertices of a tree T, and 𝐿𝑇 denotes the set of all leaves. A vertex adjacent to at least two leaves in a tree T is known as strong support vertex of the tree. The graph obtained by attaching a leaf to each vertex of a graph H is called corona of graph H and is denoted by cor(H). Observation: Every 𝛾1𝑓𝑑 ′ - set in a tree T contains all its leaves. Proof: Already we have by [9], every 1-fd set contains all its strong support vertices. Also we know that 𝛾1𝑓𝑑 set and 𝛾1𝑓𝑑 ′ set are mutually disjoint sets, the result follows. 𝑛 Observation: If T is the corona of a tree H and T has order n, then 𝛾1𝑓𝑑 ′ (𝑇) = . 2 Proof: If T is the corona of a tree of order n,[9], V(T) can be partitioned as 𝑆𝑇 and 𝐿𝑇 of 𝑛 cardinality 2 and these two sets are 𝛾1𝑓𝑑 - sets. Hence the result. Observation: In a tree, if 𝛾𝑘𝑓𝑑 ′ exists, then k = 1. Proof: Let T be a tree and let D be a fd-set. Then by the result of Yair Caro et.al.,[9], D is a 1fd-set. But we have by the above observation, every 𝛾1𝑓𝑑 ′ set in a tree T contains all is leaves, the result follows. Proposition: Let T be a tree with 𝑛 ≥ 3 vertices with 𝑒 pendent vertices and 𝑏 supports. ′ Then 𝑏 ≤ 𝛾 ≤ 𝛾1𝑓𝑑 ≤ 𝛾1𝑓𝑑 ≤ 𝑒. Theorem: Let S be a 𝛾1𝑓𝑑 - set of the tree T. Then T has a 𝛾1𝑓𝑑 ′ - set, if and only if the following conditions satisfied. T should be connected, that is, T contains no isolated vertices. T has more than two end vertices. |𝑆| ≤ |𝑉 − 𝑆|. Proof: Given S be a 𝛾1𝑓𝑑 - set of the tree T, if T contains isolated vertex, say v, then 𝑣 ∈ 𝑆 and we can’t find a disjoined dominating set containing v. It contradicts our assumption that T has a 𝛾1𝑓𝑑 ′ - set. Hence T should be connected. Let as assume that T contains no isolated vertices. If T has only one end vertex, as T is connected, T may contain cycles. And if T has no end vertices also assure the presence of cycles in T. So these two cases contradict the assumption that T is a tree. Hence T must have more than two end vertices. Now let as assume that T has more than two end vertices. Then by the definition of S, all the support vertices must belongs to S and all the leaves belongs to V - S. Hence, |𝑆| ≤ |𝑉 − 𝑆|. Let |𝑆| ≤ |𝑉 − 𝑆|. We have to prove, T contains no isolated vertices. On the contrary, if possible, assume that T is disconnected. Then each component contain 𝛾1𝑓𝑑 - set and if T contain isolated vertex, they must be members of S and this contradicts our assumption that |𝑆| ≤ |𝑉 − 𝑆|. Hence, T must be connected. Here we have, 1 ⟹ 2 ⟹ 3 ⟹ 1 . Hence the theorem. 𝑛+1 Theorem: If T is a tree of order 𝑛 ≥ 2, then 𝛾1𝑓𝑑 ′ (𝑇) ≥ ⌈ ⌉ and the equality will be 3 attained when T is a path 𝑃𝑛 . Proof: Let T be a tree of order 𝑛 ≥ 2. A path is an acyclic graph or a tree by its construction ′ which has only two end vertices. If T is a path 𝑃𝑛 , then already we have the result, 𝛾1𝑓𝑑 (𝑃𝑛 ) = 𝑛+1 ⌈ ⌉ and the result follows. 3 http://www.iaeme.com/IJMET/index.asp 1113 editor@iaeme.com
New Parameters on Inverse Domination If there exist more than two end vertices in a tree, then 𝐿𝑇 set contains more elements than 𝑆𝑇 . Hence in such cases, the inverse domination set contains more terms than the dominating ′ 𝑛+1 sets. Hence 𝛾1𝑓𝑑 (𝑇) ≥ ⌈ ⌉. 3 ′ Theorem: If T is a tree of order 𝑛 ≥ 2, then 𝛾1𝑓𝑑 (𝑇) ≤ (𝑛 − 1) and the equality will be attained when T is a star 𝑆1,(𝑛−1) . Proof: Let T be a tree of order 𝑛 ≥ 2. If T is a star, 𝑆1,(𝑛−1), the central vertex of T is a 𝛾1𝑓𝑑 ′ ′ - set, hence 𝛾1𝑓𝑑 (𝑇) = (𝑛 − 1). Also, this should be the maximum possible value for 𝛾1𝑓𝑑 (𝑇). Hence the result. 3. INVERSE DOMINATION IN 2-FD SETS Here we try to find inverse fair domination in total graph and square graph of cycles. Proposition: In cycles, as every vertex is of degree 2, maximum expected value for k in 𝑛 𝛾𝑘𝑓𝑑 is 2 and 𝛾2𝑓𝑑 (𝐶𝑛 ) = ⌈ 2⌉, for 𝑛 ≥ 3. 𝑛 Proposition: Let 𝐶𝑛 be cycle with 𝑛 ≥ 4 vertices. Then 𝛾2𝑓𝑑 ′ (𝐶𝑛 ) = 2, if n is even. Also for 𝑛 ≥ 4 and if n is odd, 𝛾2𝑓𝑑 ′ (𝐶𝑛 ) does not exists. Now, we can consider the total graph of Cn . Let G(V,E) be a graph with vertex set V and edge set E. The total graph of G, denoted by T(G) is defined as follows. The vertex set of T(G) is 𝑉(𝐺) ∪ 𝐸(𝐺). Two vertices u, v in T(G) are adjacent if any one of the following holds: (i) u, v are in V(G) and u is adjacent to v in G, (ii) u, v are in E(G) and u is adjacent to v in G, (iii) u is in V(G), v is in E(G) and u, v are incident in G. 2n Proposition: For 𝑛 ≥ 3, γ2fd [T(Cn )] = ⌈ 3 ⌉ . 2n Theorem: Let Cn be a cycle with 𝑛 ≥ 3, vertices. γ2fd ′ [T(Cn )] = ⌈ 3 ⌉. Proof: In Cn every vertex dominates exactly three vertices. Hence in T(Cn ) every vertex dominates exactly 5 vertices because T(Cn ) is a 4- regular graph. Let as consider the graph T(Cn ) as the union of two cycles Cn and Cn ′ joined by edges. Take any vertex v of Cn . Beginning with v proceed cyclically about these two cycles in some direction to cover all the 2n vertices. Since T(Cn ) is a 4- regular graph, the vertices can partitioned into two sets say D and D' such that they dominate every vertex of the graph exactly be two vertices. Hence D become the two fair dominating set and D' be the inverse of two fair dominating set of the graph 2n T(Cn ). So γ2fd ′ [T(Cn )] = ⌈ 3 ⌉ . In this section we consider the square graph of the cycle Cn . The definition of square graph of the cycle as follows. Let G (V, E) be a simple graph with vertex set V and edge set E. The k-th power Gk of the graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. The Square graph G2 of graph G is the graph that has the vertex set V in which two vertices are adjacent when their distance in G is at most 2. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph. 𝑛 Proposition: Let Cn be cycle with 𝑛 ≥ 3 vertices. Then 𝛾2𝑓𝑑 [(𝐶𝑛 )2 ] = ⌈ 3⌉. 𝑛 Theorem: 𝛾2𝑓𝑑 ′ [(𝐶𝑛 )2 ] = ⌈ 3⌉ for 𝑛 ≥ 3. Proof: Since Cn is two regular, (𝐶𝑛 )2 is a four regular graph. Hence every vertex of (𝐶𝑛 )2 dominates exactly five vertices. Take a set D consisting of any vertex v of (𝐶𝑛 )2 and every third vertex of (𝐶𝑛 )2, starting with v and proceed cyclically in some direction. Then every vertex of http://www.iaeme.com/IJMET/index.asp 1114 editor@iaeme.com
Jayasree T G and Radha Rajamani Iyer the graph is dominated exactly twice by the vertices of D. Same fashion, take another set say D' in such a way that every second vertex u of (𝐶𝑛 )2 and fourth vertex of (𝐶𝑛 )2 in the same direction. Then we get two sets D and D', both are disjoint sets but they dominate in a two fair 𝑛 dominating set of (𝐶𝑛 )2. Hence 𝛾2𝑓𝑑 ′ [(𝐶𝑛 )2 ] = ⌈ 3⌉. 4. INVERSE DOMINATION IN K-FD SETS In this section we try to find the inverse of k-fair domination in corona of graphs. Corona of graphs are defined as follows. Let G and H be graphs of order m and n respectively. The corona of two graphs G and H is the graph 𝐺 𝑜 𝐻 obtained by taking one copy of G and m copies of H, and joining the ith vertex of G to every vertex of the ith copy of H. We refer Emiliano C Maravilla, et.at.,[1] for the following notation. For every 𝑣 ∈ 𝑉(𝐺), denote by H v , the copy of H whose vertices are attached one by one to the vertex v. Denote by 𝑣 + 𝐻 𝑣 , the sub graph of the corona 𝐺 𝑜 𝐻 corresponding to the join 〈{𝑣} + 𝐻 𝑣 〉. Figure 1. Corona Product 𝐾5 𝑜 𝐾3 . Theorem: Let G and H be non-trivial connected graphs of order m and n respectively. m × γkfd (H) for k = 1 Then 𝛾𝑘𝑓𝑑 ′ ( 𝐺 𝑜 𝐻) = { . m × γkfd ′ (v + H v ) for k ≥ 2 Proof: By the definition of 𝐺 𝑜 𝐻, each 𝑣 ∈ 𝑉(𝐺), is enough to form 𝛾1𝑓𝑑 - set, and hence 𝛾1𝑓𝑑 ( 𝐺 𝑜 𝐻) = m . Hence to form 𝛾1𝑓𝑑 ′ - set of minimum cardinality, we require 𝛾1𝑓𝑑 (𝐻) members for each 𝑣 ∈ 𝑉(𝐺). Hence 𝛾1𝑓𝑑 ′ (𝐺 𝑜 𝐻) = 𝑚 × 𝛾1𝑓𝑑 (𝐻). Now suppose, 𝑘 ≥ 2. Consider the sub graph v + H v . As every 𝛾𝑘𝑓𝑑 - set of the graph 𝐺 𝑜 𝐻, contains the vertex 𝑣 ∈ 𝑉(𝐺), the 𝛾𝑘𝑓𝑑 ′ -set depends on v + H v . This is true for all 𝑣 ∈ 𝑉(𝐺). Hence 𝛾𝑘𝑓𝑑 ′ ( 𝐺 𝑜 𝐻) = m × γkfd ′ (v + H v ) for 𝑘 ≥ 2. 𝑛 Corollary: In a graph 𝐺 𝑜 𝐻, 𝛾𝑘𝑓𝑑 ′ exists only when 𝛾𝑘𝑓𝑑 (v + H v ) ≤ 2, for the sub graph v + H v of 𝐺 𝑜 𝐻. 5. CONCLUSION In this work we define the inverse concept for k-fair domination number and find the same for some class of graphs. REFERENCES [1] Emiliano C Maravilla, Rowena T Isla and Sergio R CanoyJr., k-Fair domination in the join, corona, composition and Cartesian product of graphs, Applied Mathematical Sciences, Vol. 8, 2014, no.178, 8863-8874. http://www.iaeme.com/IJMET/index.asp 1115 editor@iaeme.com
New Parameters on Inverse Domination [2] Gabriele Taentzer, Enrico Biermann, et.al., Generation of Sierpinski Triangles: A Case Study for Graph Transformation Tools. Applications of Graph Transformations with Industrial Relevance, pp. 514-539. [3] Hamed Hatami, Pooya Hatami, Perfect dominating sets in the Cartesian products of prime cycles, The Electronic J.Comb., 2007, 14(1). [4] Jayasree T G, Radha R Iyer, The Results on the Inverse domination number of some class of graphs, International Journal of Mechanical Engineering and Technology (IJMET) Volume 9, Issue 1, January 2018, pp. 995 - 1004. [5] M. M. Akbar Ali, S. Panauappan, Cycle multiplicity of total graph of Cn, Pn, and K{1,n}, International Journal of Engineering, Science and Technology, Vol.2, No.2, 2010, pp.54- 58. [6] P.Jeyanthi, G. Hemalatha, B. Davvaz, Total Domination Subdivision Number in Strong Product Graph, American Journal of Applied Mathematics and Statistics, 2014, Vol.2, No.4, 216-219. [7] R. R. Iyer, A. Ganesan, The regular number of a graph, Journal of Discrete Mathematical Sciences and Cryptography, 2012. [8] T. Tamizh Chelvam, Sivagnanam Mutharasu, Efficient domination in Cartesian Products of Cycles. Journal of Advanced Research in Pure Mathematics, Online ISSN 1943-2380, Vol.3, Issue. 3, 2011, pp. 42-49. [9] Yair Caro, Adriana Hansberg, Michael Henning, Fair domination in graphs, Discrete Mathematics 312(2012), 2905-2914. [10] Gary Chartrand, Ping Zhang, Introduction to Graph Theory, Tata McGraw-Hill Edition (2006). [11] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Domination in Graphs: Advanced Topics. Marcel Dekker, New York (2000). [12] T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of Domination in Graphs. Marcel Dekker, New York (2000). http://www.iaeme.com/IJMET/index.asp 1116 editor@iaeme.com