EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS 2025, Vol. 18, Issue 4, Article Number 6713 ISSN 1307-5543 – ejpam.com Published by New York Business Global Exploring Certified Domination Subdivision Numbers in Graph Theory G. Navamani1, N. Sumathi1,∗, Dharmaraj Mohankumar1, Luminiţa-Ioana Cotîrlă2, Daniel Breaz3,∗ 1 Department of Mathematics, Saveetha School of Engineering, Saveetha Institute of Medical and Technical Sciences, Chennai 602105, Tamil Nadu, India 2 Department of Mathematics, Technical University of Cluj-Napoca, 400114 Cluj-Napoca, Romania 3 Department of Mathematics, “1 Decembrie 1918” University of Alba Iulia, 510009 Alba Iulia, Romania Abstract. A certified dominating set S is a dominating set of a graph G, if every vertex in S has either zero or at least two neighbours in V \S. The minimum cardinality of certified dominating set of G is the certified domination number of G denoted by γcer(G). We defined certified domination subdivision number Sd+γcer (G) [Sd−γcer (G)] of a graph G to be the minimum number of edges that must be subdivided (where no edge in G can be subdivided more than once) in order to construct a graph with a certified domination number larger [lesser] than the certified domination number of G. In this paper, we determine the values of certified domination subdivision number for certain classes of graphs including circulant graphs [Cn(1, 2) and Cn(1, 3)] and petersen graphs [P (n, 1) and P (n, 2)]. 2020 Mathematics Subject Classifications: 05C38, 05C69, 05C75 Key Words and Phrases: Domination number, certified domination number, subdivision num- ber, certified domination subdivision number 1. Introduction Haynes [1] introduced the most fundamental and well studied concepts in graph the- ory called domination in graphs. A dominating set of a graph G is a set S ⊆ V with the property that for each vertex u ∈ V \ S there exists at least a vertex x ∈ S adjacent to u. The minimum cardinality amongst all dominating sets of G is the domination number γ(G) and S is called γ-set of G, if S is minimum. Many advanced researches are going ∗Corresponding author. ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v18i4.6713 Email addresses: navamaniprakash69@gmail.com (G. Navamani), nsumathiphd2022@gmail.com (N. Sumathi), luminita.cotirla@math.utcluj.ro (L. I. Cotîrlă), dbreaz@uab.ro (D. Breaz) https://www.ejpam.com 1 Copyright: © 2025 The Author(s). (CC BY-NC 4.0) G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 2 of 15 on in the variety of domination terminology [2],[3]. One latest among these varieties is certified domination which was introduced by Magda Dettlaff et al [4]. A certified dom- inating set is defined as D ⊆ V is a dominating set of a graph G and every vertex in D has either zero or at least two neighbours in V \D. γcer(G) is the certified domination number of G which is defined as the minimum cardinality of certified dominating set of G and D is the γcer-set of G, if D is minimum. Further results on this parameter seen in [5–9]. An edge uv ∈ E(G) is subdivided if the edge uv is deleted, but a new vertex called subdivision vertex w is added along with two new edges uw and vw. The domination subdivision number Sd(G) of a graph G is the minimum number of edges which must be subdivided (where each edge can be subdivided at most once) in order to increase the domination number. S. Arumugam and J. Paulraj Joseph [10] first defined the domina- tion subdivision number Sd(G) of a graph G and showed that Sd(T ) ≤ 3 for any tree T with at least three vertices. Other results and General bounds of domination subdivision number can be found in [11–16]. Motivated by recent researches focusing on subdivision number, we defined certified domination subdivision number of a graph G denoted by Sd+γcer(G) [Sd−γcer(G)] to be the minimum number of edges which must be subdivided (where each edge can be subdivided at most once) in order to increase [decrease] the certified domination number of G and also we characterised these parameters for trees in [17]. Domination in graphs has ap- plications in a variety of fields. Domination occurs in facility location problems in which the number of facilities (e.g., health centres, police stations) is fixed and an attempt is made to minimize the distance that a person must travel to reach the facility. Certified domination is one such latest parameter, in which a set S is the facility centres and set T is the area of stakeholders. For each area x ∈ T , there must be a facility centre v ∈ S, that can serve for x and whenever such v is serving x, there must also be at least one neighbouring area y ∈ T that uses the facility centre v. We can determine the minimum number of facility centres either to take care of its area (where it situated) or it takes care of more than one neighbouring areas. Here we introduce subdivision certified domination number, which is to determine how the areas are subdivided according to the convenience of the stakeholders in neighbour areas so as to facilitate them to save time and money without increasing the facility centres [some times the number of facility centres can also be reduced due to the subdivision of areas]. In this paper, we determine the values of certified domination subdivision number for certain classes of graphs including circulant graphs [Cn(1, 2) and Cn(1, 3)] and petersen graphs [P (n, 1) and P (n, 2)]. 2. Notation Let G = (V,E) be a connected, simple graph with order |V | = n. We use Harary’s [18] for graph theoretic notation. For any vertex v ∈ V , the open neighbourhood of v is the set N(v) = {u ∈ V : uv ∈ E} and the closed neighbourhood is the set N [v] = N(v) ∪ {v}. For G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 3 of 15 a set S ⊆ V , the open neighbourhood of S is N(S) = ⋃ v∈S N(v), the closed neighbourhood of S is N [S] = N(S) ∪ S and the private neighbourhood pn(v, S) of a vertex u ∈ S is defined by pn(v, S) = {u ∈ V − S : N(u) ∩ S = {v}}. A path is a walk with no repeated vertices. A nontrivial closed path is called a cycle. A graph G is k-partite, k ≥ 1 if it is possible to partition V (G) into k subsets, v1, v2 . . . vk (called partite set) such that every element of E(G) joins a vertex of Vi to a vertex of Vj , i 6= j. If G is a 1-partite graph of order n, then G = Kn. For k = 2, such graphs are called bipartite graphs. A complete bipartite graph is a simple bipartite graph such that every vertex in one of the bipartition subsets is joined to every vertex in the other bipartition subset. Any complete bipartite graph that has m vertices in one of its bipartition subsets and n vertices in the other is denoted Km,n. A wheel graph is a graph formed by connecting all vertices of a cycle to a single universal vertex. 3. Main Results Theorem 1. [5] If Cn is an n-vertex cycle, n ≥ 3, then γcer(Cn) = ⌈ n 3 ⌉ Theorem 2. For any cycle Cn, n ≥ 4 Sd+γcer(Cn) =  1 if n ≡ 0 (mod 3) 2 if n ≡ 2 (mod 3) 3 if n ≡ 1 (mod 3) Proof. By theorem 1, γcer(Cn) = ⌈ n 3 ⌉ , n ≥ 4. Let D be a γcer-set of Cn. Consider the following cases. Case (i) n ≡ 0 (mod 3) In this case, each vertex in D dominates exactly 3 vertices, including itself. Subdividing an edge in Cn results Cn+1. Since γcer(Cn) = ⌈ n 3 ⌉ , for n ≡ 0 (mod 3). So we need to add one more vertex in D to dominate Cn+1. Hence γcer (Cn+1) > γcer (Cn). Therefore Sd+γcer(Cn) = 1. Case (ii) n ≡ 2 (mod 3) In this case, each vertex in D dominates exactly 3 vertices including itself except one which dominates 2 vertices including itself. Subdividing an edge in Cn results Cn+1, where n + 1 ≡ 0 (mod 3). Now by case (i) we notice that γcer(Cn+1) = γcer(Cn). This implies that Sd+γcer(G) > 1. By case (i) we need to subdivide one more edge in Cn+1 results Cn+2. Hence γcer(Cn+2) > γcer(Cn+1). Therefore Sd+γcer(Cn) = 2. Case (iii) n ≡ 1 (mod 3) In this case subdividing an edge in Cn results n ≡ 2 (mod 3). By case (ii) we clearly see that Sd+γcer(G) = 3. Hence the proof. G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 4 of 15 Theorem 3. [4] Let G be a connected graph of order at least three vertices . Then γ(G) = γcer(G)) if and only if G has a γ-set D such that every vertex in D has at least two neighbours in VG −D. Theorem 4. [5] If Km,n is a complete bipartite graph with 1 ≤ m ≤ n, then γcer(Km,n) = { 1 if m = 1 and n > 1 2 otherwise. Theorem 5. For complete bipartite graph G = Km,n, Sd+γcer(G) = { 3 if m = 2 and n ≥ 2 1 otherwise. Proof. Let G = Km,n, Let V1, V2 be the vertex partition of G . Let D be a γcer-set of G. By theorem 3, for all vertex v ∈ D, |N(v)| ≥ 2 , we clearly see that γcer(G) = 2. Consider the following cases. Case (i) m = 2 In this case, we have the following subcases. Subcase (i) n = 2 Here K2,2 = C4, by theorem 2 we have Sd+γcer(C4) = 3. Hence Sd+γcer(K2,2) = 3. Subcase (ii) n > 2 Let v1, v2 ∈ V1 ∩D and u1, u2, . . . un ∈ V2 and let G′ be a graph derived from G through subdividing an edge in G say e = v1ui for some i by a subdivision vertex x1. All vertices in V2 are dominated by v2 and x1 is dominated by v1. We clearly see that D is a γcer-set of G. Hence, γcer(G) = γcer(G ′), this implies Sd+γcer(G) > 1. Let G′′ be the graph obtained from G′, by subdividing an edge in G′ say e = v2ui by a subdivision vertex x2 results D1 = {D − {v2} ∪ {x2}} is a γcer-set of G′′. Hence, Sd+γcer(G) > 2. Let G′′′ be the graph obtained from G′′ by subdividing an edge say e = v2u2 in G′′ by a subdivision vertex x3 results D2 = D1∪{v2} is a γcer-set of G′′′. Here |D2| > |D1| , that is γcer(G) < γcer(G ′′′). Hence Sd+γcer(G) = 3. Case (ii) m = 1 and n > 1 Let v1 ∈ V1 ∩D and u1, u2, u3, . . . un ∈ V2. We know that γcer(G) = 1. Subdividing the edge e = v1ui, for some 1 < i < n by subdivision vertex x results D1 = D − {ui}. Hence Sd+γcer(G) = 1. Case (iii) m > 2 and n > 2 Let v1, v2, v3, . . . vm ∈ V1 and u1, u2, u3, . . . un ∈ V2 and by theorem [4], γcer(G) = 2. Let vi, uj ∈ D for some 1 < i < m and 1 < j < n. Let G′ be a graph obtained by subdividing an edge e in G say e = v1u1 by a subdivision vertex x1, results a new configuration of G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 5 of 15 γcer-set say D1 = {v1, u1} which implies |D| = |D1|. Therefore Sd+γcer(G) > 1. Let G′′ be a graph obtained from G′ by subdividing the edge e = u1v2 by a subdivision vertices x2. Here x1 and x2 are dominated by u1 and v2 /∈ N [v] for all v ∈ D. Now D2 = D1 ∪ {v2}. Hence |D2| > |D1| . Therefore, Sd+γcer(G) = 2. We observe that, for all graphs G which is isomorphic to complete graphs, wheel graphs and grid graphs (P2 × Pn, n ≥ 2), Sd+γcer(G) = 1. 4. Circulant Graphs The circulant graph Cn(Sc) is the graph with the vertex set V (Cn(Sc)) = {vi : 0 ≤ i ≤ n− 1} and the edge set E(Cn(Sc)) = {vivj : 0 ≤ i, j ≤ n− 1, (i− j)(mod n) ∈ Sc}. Here Sc ⊆ {1, 2, 3, . . . , ⌈ n 2 ⌉ } where subscripts are taken modulo n. In this section we find the value of Sd+γcer(G) for the circulant graphs Cn(1, 2) and Cn(1, 3) Theorem 6. [19] For any integer n ≥ 5, γ(Cn(1, 2)) = ⌈ n 5 ⌉ Theorem 7. For any circulant graph G ∼= Cn(1, 2), n ≥ 6, Sd+γcer(G) =  1 if n ≡ 0, 4 (mod 5) 2 if n ≡ 2, 3 (mod 5) 3 if n ≡ 1 (mod 5) Proof. Let G ∼= Cn(1, 2). Let V (G) = {v1, v2, v3, . . . vn} be the vertex set of G and D = {v5k−4 : 1 ≤ k ≤ ⌈ n 5 ⌉ } is a γcer-set of G. For every vertex v ∈ D, N(v) ≥ 2. By theorem 6 and theorem 3 , we clearly see that γ(G) = γcer(G) = ⌈ n 5 ⌉ . Case (i) n ≡ 0, 4 (mod 5) If n ≡ 0 (mod 5) then |pn(v,D)| = 4 for each vertex v ∈ D. If n ≡ 4 (mod 5) then |pn(v,D)| = 4 for all vertex v ∈ D except v1 and vn−3 for which |pn(v1, D)| = 3 and |pn(vn−3, D)| = 3. Here, vn−1 ∈ pn(v1, D) ∩ pn(vn−3, D). For n ≡ 0, 4 (mod 5). Let G′ be a graph obtained from G by subdividing an edge e = v1vn (say) by a subdivision vertex x. Here, we clearly see that vn /∈ NG′(D). Hence D′ = D ∪ {vn} is a γcer-set of G′. Therefore, Sd+γcer(G) = 1. Case (ii) n ≡ 2, 3 (mod 5) If n ≡ 2 (mod 5) then |pn(v,D)| = 4 for all vertex v ∈ D except v1 and vn−1 for which |pn(v1, D)| = 2 and |pn(vn−1, D)| = 2. Here vn is a non-private neighbour of the vertices v1 and vn−1. If n ≡ 3 (mod 5) then |pn(v,D)| = 4 for all vertex v ∈ D except v1 and vn−2 for which |pn(v1, D)| = 2 and |pn(vn−2, D)| = 2. Here, vn /∈ pn(v1, D) and vn−1 /∈ pn(vn−2, D). Let G′ be a graph obtained from G by subdividing an edge e = v1vn [or v1vn−1] by a subdivision vertex x1 (or y1) . Here, D is the γcer-set of G′. Therefore, Sd+γcer(G) > 1. Now G′′ be a graph obtained from G′ by subdividing an edge e = vnvn−1 G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 6 of 15 by a subdivision vertex x2. For n ≡ 2 (mod 5) , we see that vn /∈ NG′′(D). Hence D′ = D ∪ {vn} is a γcer-set of G′′. Therefore, Sd+γcer(G) = 2 . Now for n ≡ 3 (mod 5) x2 /∈ NG′′(D). Hence D′ = D ∪ {x2} is a γcer-set of G′′. Therefore, Sd+γcer(G) = 2, refer Figure 1 . Figure 1: A graph illustrating case (ii) of theorem 7, Sd+γcer (G) = 2 Case (iii) n ≡ 1 (mod 5) If n ≡ 1 (mod 5), then |pn(v,D)| = 4 for all vertex v ∈ D except vn and v1 for which |pn(v1, D)| = 2 and |pn(vn, D)| = 1. Let G′ be a graph obtained from G by subdividing an edge e = v1vn [or v1vn−1] by a subdivision vertex y. Here y is dominated by v1 and vn−1 is dominated by vn. Hence, D is the γcer-set of G′. Therefore, Sd+γcer(G) > 1. Now let G′′ be a graph obtained from G by subdividing the 2 edges e1 and e2 by subdivision vertices x1 and x2 respectively. Now we have the following subcases. Subcase (a) e1 = v1vn and e2 = v1v2 [adjacent edges]. In this subcase, x1, x2 ∈ N(v1) and v2 ∈ N(vn). Hence γcer(G) = γcer(G ′′). Subcase (b) e1 = v1vn and e2 = v6v7 [non adjacent edges in the outer cycle] Here x1 ∈ N(v1) and x2 ∈ N(v6) and to dominate v7, D1 = {D − {(v5k+6) : 1 ≤ k ≤ n−6 5 }} ∪ {v5k+4 : 1 ≤ k ≤ n−6 5 } is the new configuration of the certified dominating set D G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 7 of 15 and |D| = |D1|. Hence γcer(G) = γcer(G ′′). Subcase (c) e1 = v1vn and e2 = v1vn−1 [adjacent edges with one edge in the outer cycle] In this subcase, x1, x2 ∈ N(v1) and vn−1 ∈ N(vn). Hence γcer(G) = γcer(G ′′). Subcase (d) e1 = v1vn and e2 = v6v8 [non adjacent edges with one edge in the outer cycle] In this subcase, x1 ∈ N(v1) and x2 ∈ N(v6) as in subcase (b), D1 is the certified domi- nating set of G′′ and v8 ∈ N(v9). Hence γcer(G) = γcer(G ′′). Subcase (e) e1 = v1vn−1 and e2 = v1v3 [adjacent edges, which are not in the outer cycle] Here, x1, x2 ∈ N(v1). In order to dominate v3, D1 = {v5k : 1 ≤ k ≤ n−1 5 } is the new configuration of the certified dominating set D, and |D| = |D1|. Hence γcer(G) = γcer(G ′′). Subcase (f) e1 = v1v3 and e2 = v4v6 [ Non adjacent edges, which are not in the outer cycle] In this subcase, x1 ∈ N(v1) and x2 ∈ N(v4). Hence γcer(G) = γcer(G ′′). From all the above subcases we see that Sd+γcer(G) > 2. Let G′′′ be the graph obtained from G by subdividing 3 edges e1 = v1vn, e2 = v1v2 and e3 = v2v3 by the subdivision vertices x1, x2 and x3 respectively. Here x3 /∈ N(v) for every vertex v ∈ D. To dominate x3, set D1 = {v5k−2 : 1 ≤ k ≤ n−1 5 } ∪ {v1} which is the new configuration of the certified dominating set D. But {vn, v2} /∈ NG′′′(D1). So D1 is not a certified dominating set of G′′′. Hence D2 = D1 ∪ {vn} is the certified dominating set of G′′′. Therefore, Sd+γcer(G) = 3. Theorem 8. [19] For any integer n ≥ 6, γ(Cn(1, 3)) = {⌈ n 5 ⌉ , n 6∈ 4 (mod 5)⌈ n 5 ⌉ + 1, n ≡ 4 (mod 5) Theorem 9. For any Circulant graph G ∼= Cn(1, 3), n ≥ 6, Sd+γcer(G) = { 1 if n ≡ 0, 3(mod 5) 2 otherwise Proof. Let G ∼= Cn(1, 3). Let V (G) = {v1, v2, v3, . . . vn} be the vertex set of G and D = {v5k−4 : 1 ≤ k ≤ ⌈ n 5 ⌉ } be a γcer-set of G. For every vertex v ∈ D, N(v) ≥ 2. By theorem 3 and theorem 8, we clearly see that γ(G) = γcer(G) = ⌈ n 5 ⌉ . Case (i) n ≡ 0 (mod 5) Here |pn(v,D)| = 4 for each vertex v ∈ D. Let G′ be a graph obtained from G by subdividing an edge e = v1v2 (say) by a subdivision vertex x, Here x is dominated by v1, and v2 /∈ N(v) for all vertex v ∈ D. Hence D1 = D ∪ {v2} is the γcer-set of G′. Therefore, Sd+γcer(G) = 1, refer Figure 2. Case (ii) n ≡ 3 (mod 5) G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 8 of 15 Figure 2: A graph illustrating case (i) of theorem 9, Sd+γcer (G) = 1 Here |pn(v,D)| = 4 for all vertex v ∈ D except the vertices v1 and vn−2 for which |pn(v1, D)| = 3 and |pn(vn−2, D)| =3. Let G′ be a graph obtained from G by subdividing an edge e = v1v2 (say) by a subdivision vertex x, here x ∈ N(v1) in G′ and v2 /∈ N(v), for all v ∈ D. Hence D1 = D ∪ {v2} is the γcer-set of G′. Therefore, Sd+γcer(G) = 1. Case (iii) n ≡ 1 (mod 5) Here |pn(v,D)| = 4 for all vertex v ∈ D except the vertices v1 and vn for which |pn(v1, D)| = 2 and |pn(vn, D)| = 2. Let G′ be a graph obtained from G by subdividing an edge e = v1vn (or e = v1vn−2) by a subdivision vertex x. Here, x ∈ N(v1) , vn−2 ∈ N [vn−5]. Hence γcer(G ′) = γcer(G). Therefore Sd+γcer(G) > 1. Let G′′ be a graph obtained from G′ by subdividing an edge e = v1v2 (say) by a subdivision vertex y and y ∈ N(v1). Now v2 /∈ NG′′(D). Here D1 = D ∪ {v2} is a γcer set of G′′. Hence, γcer(G ′′) > γcer(G ′). Therefore Sd+γcer(G) = 2. Case (iv) n ≡ 2 (mod 5) Here |pn(v,D)| = 4 for all vertex v ∈ D except the vertices v1 and vn−1 for which |pn(v1, D)| = 1 and |pn(vn−1, D)| = 1 and vn is a non-private neighbour. Let G′ be a graph obtained from G by subdividing an edge e = v1vn [or e = v1vn−2] by a subdivision vertex x. Here x ∈ N(v1) ,( or x ∈ N(vn−1)). Hence γcer(G ′) = γcer(G). Therefore, Sd+γcer(G) > 1. Let G′′ be a graph obtained from G by subdividing the edges e1 = v1vn−2 and e2 = v1v4 by a subdivision vertices x and y respectively, and x, y ∈ N(v1). Now G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 9 of 15 D1 = D ∪ {v4} is a γcer set of G′′. Hence γcer(G ′′) > γcer(G ′). That is |D1| > |D|. Therefore, Sd+γcer(G) = 2. Case (v) n ≡ 4 (mod 5) In this case D ∪ {vn−1} is the γcer-set of G . Here |pn(v,D)| = 4 for all vertex v ∈ D except the vertices v1, vn−1 and vn−3 for which |pn(v1, D)| = 2, |pn(vn−1, D)| = 0 and |pn(vn−3, D)| = 2. Here vn, vn−2 /∈ pn(v,D) for all v ∈ D. Let G′ be a graph obtained from G by subdividing an edge e = v1vn (or e = v1vn−2) by a subdivision vertex x. Here x ∈ N(v1), vn ∈ N(vn−1), [vn−2 ∈ N(vn−3)]. Hence γcer(G ′) = γcer(G). Therefore Sd+γcer(G) > 1. Let G′′ be a graph obtained from G by subdividing the edges e1 = v1vn and e2 = v5v6 by a subdivision vertices x and y respectively, x ∈ N(v1), and v4 /∈ N(v) for all v ∈ D. Hence we have D1 = D ∪ {v4} is a γcer set of G′′. So γcer(G ′′) > γcer(G ′). Therefore, Sd+γcer(G) = 2. 5. Generalized Petersen Graphs The generalized Petersen graph P (n, k) is defined to be a graph on 2n vertices with V (P (n, k)) = {vi, ui : 0 ≤ i ≤ n − 1} and E(P (n, k)) = {vi, vi+1,, vi, ui, uiui+k : 0 ≤ i ≤ n − 1} subscipts taken modulo n. The edges uivi for 0 ≤ i ≤ n − 1 are called the spokes. In this section we find the value of Sd+γcer(G) for the generalised Petersen graphs P (n, 1) and P (n, 2) Theorem 10. [20] For n ≥ 3, γ(P (n, 1)) = {⌈ n 2 ⌉ , n ≡ 0, 1, 3 (mod 4)⌈ n 2 ⌉ + 1, n ≡ 2 (mod 4) Theorem 11. For any Petersen graph G ∼= P (n, 1), n ≥ 4, Sd+γcer(G) =  1 if n ≡ 0, 1 (mod 4) 2 if n ≡ 3 (mod 4) 3 if n ≡ 2 (mod 4) Proof. Let G ∼= P (n, 1). Let C ′ and C ′′ be the inner and outer cycles of G respec- tively. Let V (C ′) = {v1, v2, v3, . . . vn} and V (C ′′) = {u1, u2, u3, . . . un}, by theorem 3 and theorem 10, hence, γ(P (n, 1)) = γcer(P (n, 1)). Let D be a γcer-set of G and D = D′ ∪D′′ where D′ = D ∩ V (C ′) and D′′ = D ∩ V (C ′′). Let D′ = {v4k+1 : 0 ≤ k ≤ ⌊ n 4 ⌋ } for all n and D′′ = { u4k+3, 0 ≤ k < ⌈ n 4 ⌉ ∪ {un} for n ≡ 2 (mod 4) u4k+3, 0 ≤ k < ⌈ n 4 ⌉ otherwise Now consider the following cases G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 10 of 15 Case (i) n ≡ 0 (mod 4) In this case each vertex in D dominates exactly 4 vertices including itself. Let G′ be a graph obtained from G by subdividing an edge e = u1un by a subdivision vertex x, we clearly see that x /∈ N(v) for all v ∈ D. Hence D1 = D ∪ {x} is a γcer- set of G′. This implies that γcer(G ′) > γcer(G). Hence Sd+γcer(G) = 1. Case (ii) n ≡ 1 (mod 4) Let G′ be a graph obtained from G by subdividing an edge e = u1v1 by a subdivision vertex x, we clearly see that x ∈ N(v1). In order to dominate u1, the position of the D will be changed to D′ where the dissimilar sets are D′ = {x} ∪ {v4k−2, 1 ≤ k < n+2 4 } ∪ {u4k, 1 ≤ k ≤ n−1 4 }} and D′′ = {{u3k−2, 1 ≤ k ≤ n+2 4 } ∪ {u4k−2, 1 ≤ k ≤ n+1 4 }}. Hence γcer(G ′) > γcer(G). Therefore, Sd+γcer(G) = 1. Case (iii) n ≡ 3 (mod 4) Figure 3: A graph illustrating case (iii) of theorem 11, Sd+γcer (G) = 2 Let G′ be a graph obtained from G by subdividing an edge e = u1un [or e = unvn, or e = v1vn] by a subdivision vertex x, here x ∈ N(un) [or N(un) or N(v1)]. Hence γcer(G ′) = γcer(G). Therefore, Sd+γcer(G) > 1. Let G′′ be a graph obtained from G by G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 11 of 15 subdividing two edges (say) e1 = u1un and e2 = u1u2 by a subdivision vertices x and y respectively, x ∈ N(un) here y /∈ N [D] . Now D′ = D ∪ {y} is a γcer-set of G′′. Hence, Sd+γcer(G) = 2, refer Figure 3. Case (iv) n ≡ 2 (mod 4) Let G′ be a graph obtained from G by subdividing an edge e = u1un [or e = unvn or e = v1vn] by a subdivision vertex x, here x ∈ N(un) and u1 ∈ N(v1) [or N(un) or N(v1)] respectively. Hence γcer(G ′) = γcer(G). Therefore Sd+γcer(G) > 1. Let G′′ be a graph obtained from G by subdividing two edges (say) e1 and e2 by a subdivision vertices x and y respectively. We have the following subcases. Subcase (a) e1 = u1un and e2 = unun−1 (adjacent edges in the outer cycle) In this subcase, x, y ∈ N(un) and un−1 ∈ N(vn−1) and u1 ∈ N(v1), hence γcer(G ′′) = γcer(G). Subcase (b) e1 = unun−1 and e2 = vnvn−1 (an edge in the outer cycle and an edge in the inner cycle) In this subcase, x ∈ N(un) and y ∈ N(vn−1) and vn−1 ∈ N(un−1), hence γcer(G ′′) = γcer(G). Subcase (c) e1 = u1v1 and e2 = unvn (edges in the spokes) In this subcase, x ∈ N(v1) and y ∈ N(un), u1 ∈ N(un) and vn ∈ N(v1). Hence γcer(G ′′) = γcer(G). Subcase (d) e1 = v1vn and e2 = vnvn−1 (adjacent edges in the inner cycles) In this subcase, x ∈ N(v1) and y ∈ N(vn−1), vn ∈ N(un). Hence γcer(G ′′) = γcer(G). Subcase (e) e1 = u1un and e2 = un−1vn−1 (non adjacent edges with one edge in the outer cycle and another edge in the spoke) In this subcase, x ∈ N(un) and y ∈ N(vn−1), un−1 ∈ N(un), u1 ∈ N(v1). Hence γcer(G ′′) = γcer(G). Subcase (f) e1 = unvn and e2 = vn−1vn (an edge in spoke and an edge in inner cycle) In this subcase x ∈ N(un) and y ∈ N(vn−1), un−1 ∈ N(un), vn ∈ N(v1). Hence, γcer(G ′′) = γcer(G). From all the cases mentioned above clearly, we see that Sd+γcer(G) > 2. Let G′′′ be a graph obtained from G by subdividing the edges e1 = unu1, e2 = unun−1 and e3 = u1u2 by the subdivision vertices x, y and z respectively, where x, y ∈ N(un) and z /∈ N(v). Hence, D′ = D ∪ {z} is a γcer-set of G′′′. Therefore, Sd+γcer(G) = 3. Theorem 12. [20] For n ≥ 5, we have γ(P (n, 2)) = ⌈ 3n 5 ⌉ G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 12 of 15 Theorem 13. For any Petersen graph G ∼= P (n, 2), n ≥ 5, Sd+γcer(G) = { 1 if n ≡ 0, 3 (mod 5) 2 otherwise Proof. Let G ∼= P (n, 2), C ′ and C ′′ be the inner and outer cycles of G. Let V (C ′) = {v1, v2, v3, . . . vn} and V (C ′′) = {u1, u2, u3, . . . un} by theorem 3 and theorem 12, γ(P (n, 2)) = γcer(P (n, 2)). Let D be a γcer-set of G and D = D′ ∪ D′′, where D′ = D ∩ V (C ′) and D′′ = D ∩ V (C ′′). Now consider the following cases Case (i) n ≡ 0 (mod 5) Let D′ = {v5k−4 : 1 ≤ k ≤ n 5 } ∪ {v5k−3 : 1 ≤ k ≤ n 5 } and D′′ = {u5k−1 : 1 ≤ k ≤ n 5 } and G′ be a graph obtained from G by subdividing an edge e = u1u2 by a subdivision vertex x, where x /∈ N(v) for all v ∈ D. Now D1 = D ∪ {x} is the γcer-set of G′. We clearly see that |D1| > |D|, Hence γcer(G ′) > γcer(G). Therefore, Sd+γcer(G) = 1. Case (ii) n ≡ 1 (mod 5) Let D′ = {v5k−4 : 1 ≤ k ≤ ⌈ n 5 ⌉ } ∪ {v5k−3 : 1 ≤ k ≤ ⌊ n 5 ⌋ } and D′′ = {u5k−1 : 1 ≤ k ≤ ⌊ n 5 ⌋ } and G′ be a graph obtained from G by subdividing an edge e = u3u4 (or e = v1v3), (or e = u4v4) by a subdivision vertex x, here x ∈ N(u4) or N(v1) or N(v6) respectively. For the first two category in order to dominate u3 (or v3) the configuration of D has to be changed to D1 = D − {v2} ∪ {u3} again |D1| = |D|. Hence γcer(G ′) = γcer(G). There- fore, Sd+γcer(G) > 1. Let G′′ be a graph obtained from G by subdividing the two edges (say) e1 = u3u4 and e2 = u4u5 by a subdivision vertices x and y respectively. Here, x ∈ N(u3), y ∈ N(u4). u5 /∈ N(v) . Now D′ = D ∪ {u5} is the γcer-set of G′′. Hence γcer(G ′′) > γcer(G). Therefore, Sd+γcer(G) = 2. Case (iii) n ≡ 2 (mod 5) Let D′ = {v5k−4 : 1 ≤ k ≤ ⌈ n 5 ⌉ } ∪ {v5k−3 : 1 ≤ k ≤ ⌈ n 5 ⌉ } and D′′ = {u5k−1 : 1 ≤ k ≤ ⌊ n 5 ⌋ } and G′ be a graph obtained from G by subdividing an edge e = u3u4 (or e = u4v4, or e = v2v4) by a subdivision vertex x. Here x ∈ N(u4) and In order to dominate u3 the position of the D is changed to D1, where D1 = (D − {v2}) ∪ {u2}, (or x ∈ N(u4) or x ∈ N(v2)). Hence γcer(G ′) = γcer(G). Therefore, Sd+γcer(G) > 1. Let G′′ be a graph obtained from G by subdividing two edges e1 = u1v1 and e2 = unvn by a subdivision vertices x and y respectively. Here x ∈ N(v1) and y ∈ N(vn). Now u1, un /∈ N [D1] . Now D2 = D1 ∪ {un}. Hence γcer(G ′′) > γcer(G). Therefore, Sd+γcer(G) = 2. Case (iv) n ≡ 4 (mod 5) Let D′ = {v5k−4 : 1 ≤ k ≤ ⌈ n 5 ⌉ } ∪ {v5k−3 : 1 ≤ k ≤ ⌈ n 5 ⌉ } and D′′ = {u5k−1 : 1 ≤ k ≤ ⌈ n 5 ⌉ } and G′ be a graph obtained from G by subdividing an edge e = u3u4 [or e = u4v4, or e = v2v4] by a subdivision vertex x. Here, x ∈ N(u4) and in order to dominate u3 the position of the D is changed to D1, where D1 = (D − {v2}) ∪ {u2},[ or x ∈ N(u4) or x ∈ N(v2) ]. Hence γcer(G ′) = γcer(G). Therefore Sd+γcer(G) > 1. Let G′′ be a graph G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 13 of 15 obtained from G by subdividing two edges e1 = u2u3, e2 = u3u4 by a subdivision ver- tices x and y respectively. Here, x ∈ N(u2) and y ∈ N(u4). Now u3 /∈ N [D1]. Now D2 = D1 ∪ {u3} is a γcer-set of G′. Hence γcer(G ′′) > γcer(G). Therefore, Sd+γcer(G) = 2. Case (v) n ≡ 3 (mod 5) Let D be a γcer-set of G. D = D′∪D′′ and |D| = ⌈ 3n 5 ⌉ , where D′ = {v5k−4, 1 ≤ k ≤ ⌈ n 5 ⌉ } Figure 4: A graph illustrating case (v) of theorem 13, Sd+γcer (G) = 1 and D′′ = {u5i−3, 1 ≤ i ≤ ⌈ n 5 ⌉ } ∪ {u5j , 1 ≤ j ≤ ⌊ n 5 ⌋ }. Let G′ be a graph obtained from G by subdividing an edge e = u2u3 by a subdivision vertex x . Here, x ∈ N(u2), u3 /∈ N [D] . Hence D1 = D ∪ {u3} is the γcer-set of G′. Hence γcer(G ′) > γcer(G). Therefore, Sd+γcer(G) = 1. Acknowledgements The authors thank the readers of European Journal of Pure and Applied Mathematics, for making our journal successful. G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 14 of 15 6. Conclusion In conclusion, this study establishes the certified domination subdivision number as a measure of how the certified domination number of a graph responds to edge subdivisions, revealing distinct behaviors across different graph classes. For circulant graphs Cn(1, 2) and Cn(1, 3), as well as Petersen graphs P (n, 1) and P (n, 2), we identify the precise num- ber of subdivisions required to alter the parameter, thereby offering new insights into structural properties of these graphs with potential applications in network design and optimization. The findings further suggest that strategic edge subdivisions can reduce the number of facility centers without compromising service quality, highlighting their rele- vance to urban planning and resource management. Beyond these results, the concept of certified domination subdivision numbers opens promising avenues for future research, including extensions to bipartite graphs, hypercubes, grid graphs, chordal graphs, and ran- dom graphs, as well as the development of efficient algorithms for computing Sd+γcer(G) and Sd−γcer(G) in large-scale networks. Comparative analyses with related parameters such as bondage, reinforcement, and classical subdivision numbers, along with empirical val- idation on synthetic and real-world networks, may yield deeper theoretical insights and strengthen the practical significance of these concepts in dynamic and weighted network models. References [1] Teresa W Haynes, Stephen Hedetniemi, and Peter Slater. Fundamentals of domination in graphs. CRC press, 2013. [2] Enrico Enriquez, Grace Estrada, Carmelita Loquias, Reuella J Bacalso, and Lanndon Ocampo. Domination in fuzzy directed graphs. Mathematics, 9(17):2143, 2021. [3] Aldwin T Miranda and Rolito G Eballe. Domination defect for the join and corona of graphs. Applied Mathematical Sciences, 15(12):615–623, 2021. [4] Magda Dettlaff, Magdalena Lemańska, Mateusz Miotk, Jerzy Topp, Radosław Zie- mann, and Paweł Żyliński. Graphs with equal domination and certified domination numbers. arXiv preprint arXiv:1710.02059, 2017. [5] Magda Dettlaff, Magdalena Lemańska, Jerzy Topp, Radosław Ziemann, and Paweł Żyliński. Certified domination. AKCE International Journal of Graphs and Combi- natorics, 17(1):86–97, 2020. [6] Vishwajeet S Goswami, Azham ILyass, and Kamaljit Kaur Bhagwat. Certified dom- ination number of some graphs. In AIP Conference Proceedings, volume 2735, page 040029. AIP Publishing LLC, 2023. [7] Mateusz Miotk. On a class of graphs with equal domination and certified domination numbers. Discrete Mathematics Letters, 16, 2025. [8] S Durai Raj and SG Shiji Kumari. Certified domination number in product of graphs. Turkish Journal of Computer and Mathematics Education (TURCOMAT), 11(3):1166–1170, 2020. [9] P Roushini Leely Pushpam, M Kamalam, and B Mahavir. Stability of certified G. Navamani et al. / Eur. J. Pure Appl. Math, 18 (4) (2025), 6713 15 of 15 domination upon edge addition. Discrete Mathematics, Algorithms and Applications, 16(06):2350068, 2024. [10] S Arumugam and J Paulraj Joseph. Domination in subdivision graphs. J. Indian Math. Soc.(NS), 62(1-4):274–282, 1996. [11] Hamideh Aram, Seyed Mahmoud Sheikholeslami, and Odile Favaron. Domination subdivision numbers of trees. Discrete mathematics, 309(4):622–628, 2009. [12] Ammar Babikir, Magda Dettlaff, Michael A Henning, and Magdalena Lemańska. Independent domination subdivision in graphs. Graphs and Combinatorics, 37(3):691–709, 2021. [13] Amitava Bhattacharya and Gurusamy Vijayakumar. Effect of edge-subdivision on vertex-domination in a graph. Discussiones Mathematicae Graph Theory, 22(2):335–347, 2002. [14] Odile Favaron, Teresa W Haynes, and Stephen T Hedetniemi. Domination subdivision numbers in graphs. Utilitas Mathematica, 66:195–209, 2004. [15] Odile Favaron, Hossein Karami, R Khoeilar, and Seyed Mahmoud Sheikholeslami. A new bound on the total domination subdivision number. Graphs and Combinatorics, 25(1):41–47, 2009. [16] Teresa Haynes, Sandra Hedetniemi, Stephen Hedetniemi, David Jacobs, James Knisely, and Lucas van der Merwe. Domination subdivision numbers. Discussiones mathematicae graph theory, 21(2):239–253, 2001. [17] G Navamani and N Sumathi. Certified domination subdivision number of trees. NeuroQuantology, 20(11):6161, 2022. [18] F Harary. Graph theory. addison wesley publishing company. Reading, Massachusetts, 1969. [19] Nader Jafari Rad. Domination in circulant graphs. Analele Stiintifice ale Universitatii Ovidius Constanta, Seria Matematica, 17, 01 2009. [20] B Javad Ebrahimi, Nafiseh Jahanbakht, and Ebadollah S Mahmoodian. Vertex dom- ination of generalized petersen graphs. Discrete mathematics, 309(13):4355–4361, 2009.