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

## 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 𝐺_{1}*and* _{𝐺2}*at* 𝐻_{1}* and* 𝐻_{2}*with 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 *clon*e of 𝐺 if 𝐻𝐻_{1} 𝐻_{2}. In this case, 𝐺 is called an *amalgamation* of 𝐺_{1}*and* 𝐺_{2}*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 𝐻_{1}*H*_{2 }*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.

### Downloads

## 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

## How to Cite

*Science & Technology Asia*,

*28*(3), 59–81. Retrieved from https://ph02.tci-thaijo.org/index.php/SciTechAsia/article/view/248629

## Issue

## Section

## License

Copyright (c) 2023 Science & Technology Asia

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.