Finding the Domination Number of Amalgamations of Paths and Cycles at Connected Subgraphs

Abstract

Let 𝛾(𝐺) denote the domination number of a graph 𝐺. Let 𝐺_1,𝐺₂ be disjoint graphs with two subgraphs 𝐻₁, 𝐻₂, respectively such that there is a graph isomorphism 𝑓 from 𝐻₁ to 𝐻₂. The amalgamation of 𝐺₁and _𝐺2at 𝐻₁ and 𝐻₂with respect to 𝑓 is the graph 𝐺 = 𝐺₁ ◁▷ 𝐺₂  obtained by forming the disjoint union of 𝐺₁ and 𝐺₂ and then identifying 𝐻₁ and 𝐻₂ with respect to 𝑓 . A graph 𝐻 is called a clone of 𝐺 if 𝐻𝐻₁ 𝐻₂. In this case, 𝐺 is called an amalgamation of 𝐺₁and 𝐺₂at 𝐻. Denote 𝑃_𝑟 and 𝐶_𝑡 the path and cycle of order 𝑟 and 𝑡 ≥ 3, respectively. In this research paper, our primary focus lies in investigating the domination number of the amalgamation 𝑃_𝑟 ◁▷ 𝐶_𝑡, with the condition that 𝐻₁H₂ P_s. We approach this problem by employing congruence properties modulo 3. For cases where 𝑠 ∈ {1, 2, min{𝑟, 𝑡}}, we utilize these congruence properties to identify a minimum dominating set and determine the domination number of  𝑃_𝑟 ◁▷ 𝐶_𝑡 . However, for 𝑠 ∈ {3, 4, . . . , min{𝑟, 𝑡} − 1}, we take a different approach. We construct a graph denoted as 𝑃𝐶(𝛼, 𝛽, 𝜌, 𝜆) using    four paths, namely 𝑃_𝛼, 𝑃_𝛽, 𝑃_𝜌, 𝑃_𝜆. We then establish that 𝑃_𝑟 ◁▷ 𝐶_𝑡 𝑃𝐶(𝛼, 𝛽, 𝜌, 𝜆) for some 𝛼 ∈ {0, 1, . . . , 𝑟}, 𝛽 = 𝑠 − 2, 𝜌 = 𝑡 − 𝑠, and 𝜆 = 𝑟 − (𝛼 + 𝑠). Having established this correspondence, we proceed to determine the domination number 𝛾(𝑃_𝑟 ◁▷ 𝐶_𝑡) using the corresponding value of 𝛾(𝑃𝐶(𝛼, 𝛽, 𝜌, 𝜆)). This approach allows us to gain valuable insights into the domination number of the amalgamation and explore the intricate relationships between these graph structures.