Ratio Mathematica Volume 46, 2023 Transversal eccentric domination in graphs Riyaz Ur Rehman A* A Mohamed Ismayil† Abstract Eccentricity of a vertex vis a maximum among the shortest distances between the vertex v and all other vertices. A set Dis called eccentric dominating if every vertex in its compliment has an eccentric ver- tex in the set D.A dominating set is transversal if the intersection of the set with all the minimum dominating sets is non-empty. In- spired by both the concepts we introduce transversal eccentric domi- nating(TED) set. An eccentric dominating set D is called a TED-set if it intersects with every minimum eccentric dominating set D’. We find the TED-number γted (G) of family of graphs, theorems related to their properties are stated and proved. Keywords: Eccentricity, TED-set, TED-number. 2020 AMS subject classifications: 05C69. 1 *Jamal Mohamed College (Affiliated to Bharathidasan University), Tiruchirappalli, India. fouzanriyaz@gmail.com. †Jamal Mohamed College (Affiliated to Bharathidasan University), Tiruchirappalli, India. amismayil1973@yahoo.co.in. 1Received on September 15, 2022. Accepted on December 15, 2022. Published on March 20, 2023. DOI: 10.23755/rm.v46i0.1043. ISSN: 1592-7415. eISSN: 2282-8214. ©Riyaz Ur Rehman et al. This paper is published under the CC-BY licence agreement. 24 Riyaz Ur Rehman A and A Mohamed Ismayil 1 Introduction The classical queens problem in chess or the study of networks in electronics domination finds its application everywhere and plays a pivotal role in modern day science and technology. Domination is a vast arena in graph theory which is just not limited to adjacency between vertices belonging to the dominating set and its compliment. For a graph G(V,E), a set S ⊆ V is said to be a dominating set, if every vertex in V-S is adjacent to some vertex in S. The domination number γd (G) of a graph G equals the minimum cardinality of an dominating set. There are many different invariants of domination. The concept of transversal domination in graphs was introduced by Nayaka S.R, Anwar Alwardi and Puttaswamy in 2018. A dominating set Dwhich intersects every minimum dominating set in G is called a transversal dominating set. The minimum cardinality of a transversal dominat- ing set is called the transversal domination number denoted by γtd (G). Geodesic being the shortest distance between any two vertices. The concept of shortest path has always intrigued the researchers in graph theory, operation research, computer science and other fields.There are many different types of distances in graphs, one such distance is eccentricity. The concept of eccentricity incorporated with a dominating set yields an eccentric dominating set.Eccentric domination was intro- duced by T. N. Janakiraman et al in 2010. The eccentricitye (v) of v is the distance to a vertex farthest from v. Thus, e(v) = maxd(u,v) : u ∈ V . For a vertex v, each vertex at a distancee (v) from v is an eccentric vertex. Eccentric set of a vertex v is defined as E(v) = u ∈ (G) : d(u,v) = e(v). A set D ⊆ V (G) is an eccentric dominating set if D is a dominating set of G and for every v ∈ V − D, there exists at least one eccentric vertex of v in D. The eccentric domination number γed (G) of a graph G equals the minimum cardinality of an eccentric dominating set. The main motive of this paper is to hybrid two different types of dominations and define a new domination variant. Inspired by this idea we combine transver- sal domination with eccentric domination. In this paper, we introduce transversal eccentric domination and calculate the TED-number of different graphs. Results related to TED-number of family of complete, star, path, cycle and wheel graphs are discussed. The upper TED-set, upper TED-number, lower TED-set and lower TED-number of different standard graphs are tabulated. For undefined terminolo- gies refer the book graph theory by frank harary. 2 Transversal eccentric domination in graphs Definition 2.1. An eccentric dominating(ED) set S ⊆ V (G) is called a transver- sal eccentric dominating set(TED-set) if it intersects with every minimum ED-set D′ ie S ⋂ D′ 6= ∅. 25 Transversal eccentric domination in graphs Definition 2.2. A TED-set S is called a minimal TED-set if no proper subset of S is TED-set. Definition 2.3. The TED-number γted(G) of a graph G is the minimum cardinality among the minimal TED-sets of G. Definition 2.4. The upper TED-number Γted(G) of a graph G is the maximum cardinality among the minimal TED-sets of G. Example 2.1. . ℘2 ℘3 ℘4 ℘1 ℘5 ℘6 Figure 2.1: Graph G Consider the above example where the graph G consists of 6 vertices and 9 edges. (i) The dominating sets are {℘1,℘2}, {℘1,℘3}, {℘1,℘4}, {℘2,℘5}, {℘2,℘6}, {℘3,℘5}, {℘3,℘6}, {℘4,℘5}, {℘4,℘6}. (ii) The minimum ED-sets are {℘1,℘2}, {℘3,℘5}, {℘4,℘6}. (iii) The TED-sets are {℘1,℘5,℘6}, {℘2,℘3,℘4}. Observation 2.1. For any graph G, 1. γ(G) ≤ γed(G) ≤ γted(G) ≤ Γted(G). 2. γted(G) ≤ n and Γted(G) ≤ n. 3. V (G) is also a TED-set. Theorem 2.1. For complete graph Kn, γted(Kn) = n, ∀n ≥ 2. Proof: Let V (Kn) = {℘1,℘2, . . .℘n}. Since deg(℘i) = n− 1 ∀℘i ∈ V (Kn) the eccentric vertex of ℘i is given by E(℘i) = V −{℘i} and every single vertex dominates all other vertices. Since every vertex ℘i ∈ V forms an ED-set of the form D1 = {℘1}, D2 = {℘2}, D3 = {℘3}, . . .Dn = {℘n}. The vertex set V is the only set which forms a TED-set, since V (Kn)∩Di 6= ∅ where i = 1, 2, 3, . . .n and Di is any ED-set. 26 Riyaz Ur Rehman A and A Mohamed Ismayil Theorem 2.2. For star graph Sn, γted(Sn) = 2 ∀ n ≥ 3. Proof: Let V (Sn) = {℘1, . . .℘i, . . .℘n} where deg(℘i) = n− 1 where ℘i is the central vertex and deg(℘j) = 1 where ℘j is a pendant vertex of star graph Sn. E(℘i) = V −{℘i} and E(℘j) = V −{℘i,℘j}. The central vertex ℘i forms a dominating set {℘i} but it is not an ED-set for any ℘j ∈ V − D, E(℘j) /∈ D. But D = {℘i,℘j} forms an ED-set, then for S3 we have 3 ED-sets which forms the minimum ED-sets and for any star graph Sn, ∀ n ≥ 4, we have (n − 1) ED- sets which forms the minimum ED-sets D1 = {℘i,℘1}, D2 = {℘i,℘2}, D3 = {℘i,℘3}, . . .Dn = {℘i,℘n}. Any minimum ED-set D = {℘i,℘j} also forms a TED-set, since D ∩{℘i,℘j} = {℘i} 6= ∅. Therefore γted(Sn) = 2 ∀n ≥ 3. Theorem 2.3. For path graph Pn, γted(Pn) = bn+13 c + 1, ∀ n ≥ 2. Proof: Let the vertices of Pn be given by V (Pn) = {℘1,℘2, . . .℘n}. Every path Pn contains two pendant vertices {℘1,℘n}. For any vertex ℘i ∈ V (Pn) the eccentric vertex of ℘i is E(℘i) = {℘1} or {℘n} where n is even. If n is odd then E(℘i) = {℘1} or {℘n} but if ℘i is a vertex equidistant from both the pendant vertices then ℘i = ℘n+1 2 , E(℘n+1 2 ) = {℘1,℘n}. For any path Pn, dn3e set of vertices can dominate all the vertices of Pn. Similarly a set D whose cardinality is bn+1 3 c + 1 will eccentric dominate all the vertices of Pn. By the definition of TED-set, a set D should intersect all the minimum ED-set. An ED-set D will intersect all the minimum ED-sets. Therefore every minimum ED-set is a TED- set. Therefore γed(Pn) = γted = bn+13 c + 1 Theorem 2.4. For cycle graph Cn where n ≥ 3 γted(Cn) = { 5, for n = 8 dn+1 3 e + 1, otherwise Proof: Case(i): For C8, the set D = {℘i,℘j,℘k,℘l} whose cardinality is dn+1 3 e + 1 = 4 does not form a TED-set which is an exception from case(i). Adding a vertex to D is of the form {℘i,℘j,℘k,℘l,℘m} whose cardinality is five will increasing the cardinality of D. Here every vertex in V (C8) − D has an ec- centric vertex in D and D is also dominating set which intersects all the minimum dominating sets of C8. Therefore γted(C8) = 5. Case(ii): For a cycle graph Cn, if n is even and n 6= 8 then every vertex ℘i ∈ V (Cn) has a unique eccentric vertex ie, E(℘i) = {℘j |℘j ∈ V (Cn)}. E(℘i) is at a distance of n 2 edges from ℘i for an even cycle. If n is odd then every vertex ℘i has two eccentric vertices. E(℘i) = {℘j,℘k |℘j,℘k ∈ V (Cn)}. E(℘i) is at a distance of bn 2 c edges from ℘i for odd cycle. Every single vertex ℘i can domi- nate itself and two vertices adjacent to it. Therefore for any cycle Cn, dn3e set of vertices forms the dominating set. Here we see that any set D = {℘1,℘2, . . .℘i} which has the cardinality of the form dn+1 3 e + 1 forms a dominating set as well 27 Transversal eccentric domination in graphs as an ED-set. Since D whose cardinality is dn+1 3 e + 1 intersects every minimum ED-set of cardinality γed(Cn) = { n 2 , if n is even dn 3 eordn 3 e + 1, if n is odd D forms a TED-set. Hence γted(Cn) = dn+13 e + 1. Theorem 2.5. For wheel graph Wn where n ≥ 4, a ≥ 1 γted(Wn) = { 3, for n = (6a− 1), (6a) or (6a + 1) 4, for n = (6a− 2), (6a + 2) or (6a + 3) Proof: Case(i): If n = 6a − 1, 6a and 6a + 1, the wheel graphs are of the form W5,W6,W7,W11,W12,W13,W17,W18,W19, . . .W6a−1,W6a,W6a+1. Let ℘c be the central vertex of wheel graph, deg(℘c) = n − 1. Therefore ℘c has n − 1 eccentric vertices, |E(℘c)| = n−1. Let ℘i be the non-central vertex, deg(℘i) = 3. Then closed neighbourhood of ℘i ie, N[℘i] = 4. Therefore ℘i has n−4 eccentric vertices, |E(℘i)| = n−4. D = {℘c} forms the only dominating set of cardinality one, but not an ED-set. Other than W5 and W7 every other wheel graph has an ED-set D = {℘c,℘x,℘y} where ℘c,℘x,℘y ∈ V (Wn) forms an ED-set and for every v ∈ V (Wn)−D there exists a vertex ℘c,℘x or ℘y in D such that E(v) = ℘c or ℘x or ℘y and D = {℘c,℘x,℘y} forms a TED-set, since D intersects every minimum ED-set. Therefore |D| = 3, γted(Wn) = 3 for n = 6a− 1, 6a, 6a + 1. Case(ii): If (6a−2), (6a + 2) and (6a + 3), then the wheel graphs are of the form W4,W8,W9,W10,W14,W15,W16, . . .W6a−2,W6a+2,W6a+3. For W4, γted(W4) = 4. Since W4 is K4 which is complete graph (by theorem-2.1). Similar to case(i), ℘c is the central vertex of wheel graph and ℘j is the non-central vertex, |E(℘c)| = n− 1 and |E(℘i)| = n−4. Similar to case(i) the only unique dominating set D = {℘c} whose cardinality is one does not form an ED-set. But a set D = {℘c,℘x,℘y} containing three vertices forms an ED-set, since every vertex ℘i ∈ V (Wn) − D has an eccentric vertex in D ie, E(℘i) = ℘c,℘x or ℘y. But D = {℘c,℘x,℘y} whose cardinality is three does not form a TED-set since it does not intersect every minimum ED-set. But an addition of vertex ℘z to the same set gives us a set D = {℘c,℘x,℘y,℘z} whose cardinality is four forms an ED-set and it intersects every minimum ED-set of cardinality three, thus becoming TED-set. Therefore γted(Wn) = 4 for n = (6a− 2), (6a + 2) and (6a + 3). Proposition 2.1. For any graph G, 1. γted(G) ≥b (2n−q) 4 c. 2. γted(G) ≥ diam(G)+1 3 . 3. γted(G) ≤b p ∆(G) δ c. 28 Riyaz Ur Rehman A and A Mohamed Ismayil 4. γted(G) ≥d p1+∆(G)e. 5. γted(G) ≤dn + ∆(G) − √ 2qe. The transversal eccentric dominating set, γted(G), upper transversal ec- centric dominating set and Γted(G) of standard graphs are tabulated. Graph Figure D - Minimum TED set. |D| = γted(G) γted(G) S - Upper TED set. |S| = Γted(G) Γted(G) Diamond graph ℘1 ℘4 ℘2 ℘3 {℘2,℘3}. 2 {℘2,℘3}. 2 Tetrahedral graph ℘2 ℘1 ℘3 ℘4 {℘1,℘2,℘3,℘4}. 4 {℘1,℘2,℘3,℘4}. 4 Claw graph ℘2 ℘3 ℘1 ℘4 {℘1,℘3}, {℘2,℘3}, {℘3,℘4}. 2 {℘1,℘2,℘4}. 3 (2,3)-King graph ℘2 ℘3℘1 ℘5℘4 ℘6 {℘1,℘2,℘4}, {℘1,℘3,℘4}, {℘1,℘3,℘6}, {℘1,℘4,℘5}, {℘1,℘4,℘6}, {℘2,℘3,℘6}, {℘3,℘4,℘6}, {℘3,℘5,℘6}. 3 {℘1,℘2,℘4}, {℘1,℘3,℘4}, {℘1,℘3,℘6}, {℘1,℘4,℘5}, {℘1,℘4,℘6}, {℘2,℘3,℘6}, {℘3,℘4,℘6}, {℘3,℘5,℘6}. 3 Antenna graph ℘2 ℘1 ℘3 ℘4 ℘5 ℘6 {℘1,℘2,℘5}, {℘1,℘2,℘6}, {℘1,℘3,℘5}, {℘1,℘3,℘6}, {℘1,℘4,℘5}, {℘1,℘4,℘6}, {℘1,℘5,℘6}, {℘2,℘5,℘6}. 3 {℘1,℘2,℘3,℘4}. 4 29 Transversal eccentric domination in graphs Graph Figure D - Minimum TED set. |D| = γted(G) γted(G) S - Upper TED set. |S| = Γted(G) Γted(G) Paw graph ℘2 ℘3 ℘1 ℘4 {℘1,℘3}, {℘2,℘3} {℘3,℘4}. 2 {℘1,℘2,℘4}. 3 Bull graph ℘3 ℘4 ℘5 ℘2℘1 {℘1,℘2,℘3}, {℘1,℘2,℘4}, {℘1,℘2,℘5}, {℘1,℘3,℘4}, {℘2,℘3,℘4}. 3 {℘1,℘2,℘3}, {℘1,℘2,℘4}, {℘1,℘2,℘5}, {℘1,℘3,℘4}, {℘2,℘3,℘4}. 3 Butterfly graph ℘3 ℘2 ℘5 ℘1 ℘4 {℘1,℘2,℘4}, {℘1,℘2,℘5}, {℘1,℘3,℘4}, {℘1,℘4,℘5}, {℘2,℘3,℘5}, {℘2,℘4,℘5}. 3 {℘1,℘2,℘4}, {℘1,℘2,℘5}, {℘1,℘3,℘4}, {℘1,℘4,℘5}, {℘2,℘3,℘5}, {℘2,℘4,℘5}. 3 Banner graph ℘3 ℘4 ℘1 ℘2 ℘5 {℘2,℘5}. 2 {℘2,℘5}. 2 Fork graph ℘2 ℘3 ℘1 ℘4 ℘5 {℘1,℘2,℘5}, {℘1,℘4,℘5}, {℘2,℘3,℘5}, {℘2,℘4,℘5}. 3 {℘1,℘2,℘3,℘4}, {℘1,℘3,℘4,℘5}. 4 (3,2)-Tadpole graph ℘2 ℘3 ℘4 ℘1 ℘5 {℘1,℘4}, {℘4,℘5}. 2 {℘1,℘2,℘3,℘5}. 4 Kite graph ℘3 ℘4 ℘1 ℘5 ℘2 {℘2,℘4}. 2 {℘1,℘2,℘3,℘5}. 4 (4,1)-Lollipop graph ℘3 ℘4 ℘1 ℘5 ℘2 {℘1,℘4}, {℘2,℘4}, {℘3,℘4}, {℘4,℘5}. 2 {℘1,℘2,℘3,℘5}. 4 30 Riyaz Ur Rehman A and A Mohamed Ismayil Graph Figure D - Minimum TED set. |D| = γted(G) γted(G) S - Upper TED set. |S| = Γted(G) Γted(G) House graph ℘2 ℘3 ℘1 ℘4 ℘5 {℘1,℘2,℘3}, {℘1,℘4,℘5}, {℘2,℘3,℘4}, {℘2,℘3,℘5}, {℘2,℘4,℘5}, {℘3,℘4,℘5}. 3 {℘1,℘2,℘3}, {℘1,℘4,℘5}, {℘2,℘3,℘4}, {℘2,℘3,℘5}, {℘2,℘4,℘5}, {℘3,℘4,℘5}. 3 House X graph ℘2 ℘3 ℘1 ℘4 ℘5 {℘1,℘2}, {℘1,℘3}, {℘1,℘4}, {℘1,℘5}. 2 {℘2,℘3,℘4,℘5}. 4 Gem graph ℘1 ℘2 ℘5 ℘3 ℘4 {℘1,℘2,℘3}, {℘1,℘2,℘4}, {℘1,℘3,℘4}, {℘1,℘3,℘5} {℘2,℘3,℘4} {℘2,℘4,℘5}. 3 {℘1,℘2,℘3}, {℘1,℘2,℘4}, {℘1,℘3,℘4}, {℘1,℘3,℘5}, {℘2,℘3,℘4}, {℘2,℘4,℘5}. 3 Dart graph ℘3 ℘4 ℘1 ℘5 ℘2 {℘2,℘3}, {℘2,℘4}. 2 {℘1,℘2,℘5}, {℘1,℘3,℘4}, {℘3,℘4,℘5}. 3 Cricket graph ℘4 ℘5℘3 ℘1 ℘2 {℘3,℘4}, {℘4,℘5}. 2 {℘1,℘2,℘4}, {℘1,℘3,℘5}, {℘2,℘3,℘5}. 3 Pentatope graph ℘1 ℘4 ℘5 ℘2 ℘3 {℘1,℘2,℘3,℘4,℘5}. 5 {℘1,℘2,℘3,℘4,℘5}. 5 Johnson solid skeleton 12 graph ℘2 ℘1 ℘3 ℘4 ℘5 {℘1,℘3}. 2 {℘1,℘2,℘4,℘5}, {℘2,℘3,℘4,℘5}. 4 Cross graph ℘3 ℘1 ℘2 ℘4 ℘5 ℘6 {℘1,℘3,℘6}, {℘2,℘3,℘6}, {℘3,℘4,℘6}, {℘3,℘5,℘6}. 3 {℘1,℘2,℘3,℘4,℘5}, {℘1,℘2,℘4,℘5,℘6}. 5 31 Transversal eccentric domination in graphs Graph Figure D - Minimum TED set. |D| = γted(G) γted(G) S - Upper TED set. |S| = Γted(G) Γted(G) Net graph ℘5 ℘6 ℘3 ℘4 ℘1 ℘2 {℘1,℘2,℘5}, {℘1,℘2,℘6}, {℘1,℘4,℘6}, {℘2,℘3,℘6}. 3 {℘1,℘3,℘4,℘5}, {℘2,℘3,℘4,℘5}, {℘3,℘4,℘5,℘6}. 4 Fish graph ℘4 ℘2 ℘5 ℘1 ℘6 ℘3 {℘2,℘3}, {℘3,℘5}. 2 {℘1,℘2,℘4,℘5,℘6}. 5 A graph ℘3 ℘4 ℘1 ℘5 ℘2 ℘6 {℘1,℘5,℘6}, {℘2,℘5,℘6}. 3 {℘1,℘2,℘3,℘4,℘5}, {℘1,℘2,℘3,℘4,℘6}. 5 R graph ℘3 ℘4 ℘1 ℘5 ℘2 ℘6 {℘1,℘2,℘3}, {℘2,℘3,℘4}, {℘2,℘3,℘5}, {℘2,℘3,℘6}, {℘2,℘5,℘6}. 3 {℘1,℘3,℘4,℘5,℘6}. 5 4-polynomial graph ℘2 ℘3℘1 ℘5℘4 ℘6 {℘3,℘4}. 2 {℘1,℘2,℘3,℘5,℘6}, {℘1,℘2,℘4,℘5,℘6}. 5 Octahedral graph ℘4 ℘3℘2 ℘1 ℘5 ℘6 {℘1,℘2,℘3,℘4}, {℘1,℘2,℘3,℘5}, {℘1,℘2,℘3,℘6}, {℘1,℘2,℘4,℘5}, {℘1,℘2,℘5,℘6}, {℘1,℘3,℘4,℘6}, {℘1,℘3,℘5,℘6}, {℘1,℘4,℘5,℘6}, {℘2,℘3,℘4,℘5}, {℘2,℘3,℘4,℘6}, {℘2,℘4,℘5,℘6}, {℘3,℘4,℘5,℘6}. 4 {℘1,℘2,℘3,℘4}, {℘1,℘2,℘3,℘5}, {℘1,℘2,℘3,℘6}, {℘1,℘2,℘4,℘5}, {℘1,℘2,℘5,℘6}, {℘1,℘3,℘4,℘6}, {℘1,℘3,℘5,℘6}, {℘1,℘4,℘5,℘6}, {℘2,℘3,℘4,℘5}, {℘2,℘3,℘4,℘6}, {℘2,℘4,℘5,℘6}, {℘3,℘4,℘5,℘6}. 4 3 Conclusions In this paper TED-set of a graph is defined. Theorems related to find the TED- number of different family of graphs are stated and proved. The upper and lower 32 Riyaz Ur Rehman A and A Mohamed Ismayil Graph Figure D - Minimum TED set. |D| = γted(G) γted(G) S - Upper TED set. |S| = Γted(G) Γted(G) 3-prism graph ℘2 ℘3 ℘4 ℘1 ℘5 ℘6 {℘1,℘5,℘6}, {℘2,℘3,℘4}. 3 {℘1,℘2,℘3,℘6}, {℘1,℘2,℘4,℘5}, {℘1,℘3,℘4,℘5}, {℘1,℘3,℘4,℘6}, {℘2,℘3,℘5,℘6}, {℘2,℘4,℘5,℘6}. 4 TED-number along with their respective sets of different standard graphs are tab- ulated. In future the comparative study of TED-set with eccentric dominating set will be done. The properties of a TED-set related to graph operations such as union, intersection, join and product of graphs will be explored. References A. Alwardi, S. Nayaka, et al. Transversal domination in graphs. Gulf Journal of Mathematics, 6(2), 2018. E. J. Cockayne and S. T. Hedetniemi. Towards a theory of domination in graphs. Networks, 7(3):247–261, 1977. F. Harary. Graph theory. Narosa Publishing House, New Delhi, 2001. A. M. Ismayil and A. R. U. Rehman. Accurate eccentric domination in graphs. Our Heritage, 68(4)(1, 2020):209–216, 2020a. A. M. Ismayil and A. R. U. Rehman. Equal eccentric domination in graphs. Malaya Journal of Matematik (MJM), 8(1, 2020):159–162, 2020b. T. Janakiraman, M. Bhanumathi, and S. Muthammai. Eccentric domination in graphs. International Journal of Engineering Science, Computing and Bio- Technology, 1(2):1–16, 2010. O. Ore. Theory of graphs. Amer. Math. Soc. Colloq. Publ., 38 (Amer. Math. Soc., Providence, RI), 38, 1996. 33