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

Authors

  • Sayan Panma Department of Mathematics, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand
  • Prakassawat Boonmee Department of Mathematics, Faculty of Science and Technology, Muban Chom Bueng Rajabhat University, Ratchaburi 70150, Thailand

Keywords:

Amalgamation, Cycle, Domination Number, Path

Abstract

Let 𝛾(𝐺) denote the domination number of a graph 𝐺. Let 𝐺1,𝐺2 be disjoint graphs with two subgraphs 𝐻1, 𝐻2, respectively such that there is a graph isomorphism 𝑓 from 𝐻1 to 𝐻2. The amalgamation of 𝐺1and 𝐺2at 𝐻1 and 𝐻2with respect to 𝑓 is the graph 𝐺 = 𝐺1 ◁▷ 𝐺2  obtained by forming the disjoint union of 𝐺1 and 𝐺2 and then identifying 𝐻1 and 𝐻2 with respect to 𝑓 . A graph 𝐻 is called a clone of 𝐺 if 𝐻gif.latex?\cong𝐻1gif.latex?\cong 𝐻2. In this case, 𝐺 is called an amalgamation of 𝐺1and 𝐺2at 𝐻. 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 𝐻1gif.latex?\congH2 gif.latex?\congPs. 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 𝑃𝑟 ◁▷ 𝐶𝑡 gif.latex?\cong𝑃𝐶(𝛼, 𝛽, 𝜌, 𝜆) 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.

Downloads

Download data is not yet available.

References

C. Berge, Theory of graphs and its applications, Dunod, Paris, (1958).

O. Ore, Theory of Graphs, Amer. Math. Soc. Colloquium Pub., Amer. Math. Soc.,Providence. Rhode Island, 38(1962), 206-12.

E. Cockayne, S. Hedetniemi, Towards a theory of domination in graphs, Networks Fall, (1977), 247-61.

T. W. Haynes, S. T. Hedetniemi, P. J. Slater, Fundamentals of dominations in graphs, Marcel Dekker, New York, 1998.

S. Klaviar, N. Seifter, Dominating Cartesian products of cycles, Discrete Applied Mathematics, 59 (1995), 129-36.

R. Chérifi, S. Gravier, X. Lagraula, C.Payan, I. Zigham, Domination number of cross products of paths, Discrete Appl. Math., 94(1999), 101-39.

C. Uiyyasathian, Maximal-Clique Partitions, PhD Thesis, University of Colorado at Denver, 2003.

C. Promsakon, C. Uiyyasathian, Chromatic Numbers of Glued Graphs, Thai Journal of Mathematics, Special Issue (Annual Meeting in Mathematics)(2006), 75-81.

P. Boonmee , J. Ma-In , S. Panma , Domination Numbers of Amalgamations of Cycles at Connected Subgraphs, Journal of Mathematics, (2022).

Downloads

Published

2023-09-26

How to Cite

Panma, S., & Boonmee, P. (2023). Finding the Domination Number of Amalgamations of Paths and Cycles at Connected Subgraphs. Science & Technology Asia, 28(3), 59–81. Retrieved from https://ph02.tci-thaijo.org/index.php/SciTechAsia/article/view/248629

Issue

Section

Physical sciences