skip to main content

NEW COUNTING FORMULA FOR DOMINATING SETS IN PATH AND CYCLE GRAPHS

*Leomarich F Casinillo  -  Visayas State University, Philippines

Citation Format:
Abstract

Let G=(V(G), E(G)) be a path or cycle graph. A subset D of V(G) is a dominating set of G if for every u element of V(G)\D, there exists v element of D such that uv element of E(G), that is, N[D]=V(G). The domination number of G, denoted by gamma(G), is the smallest cardinality of a dominating set of G. A set D_1 subset of V(G) is a set containing dominating vertices of degree 2, that is, each vertex is internally stable. A set D_2 subset of V(G) is a set containing dominating vertices where one of the element say a element of D_2,  and the rest are of degree 2. A set  D_3 subset of V(G) is a set containing dominating vertices in which two of the elements say b, c element of D_3, deg(b)=deg(c)=1. This paper developed a new combinatorial formula that determines the number of ways of putting a dominating set in a path and cycle graphs of order n>=1 and n>=3, respectively. Further, a combinatorial function P^1_G(n),  P^2_G(n) and P^3_G(n) that determines the probability of getting the set D_1, D_2, and D_3, respectively in graph G of order n were constructed.

Fulltext View|Download
Keywords: Dominating set, path, cycle, probability

Article Metrics:

  1. Allan, R. B. & Laskar, R., “On domination and independent domination number of a graph,” Discrete Mathematics, vol. 23, pp. 73-76, 1978
  2. Arocha, J. L. & Llano, B., “The number of dominating k-sets of paths, cycles and wheels”, arXiv preprint:1601.01268, 2018
  3. Casinillo, L. F., “A note on Fibonacci and Lucas number of domination in path”, Electronic Journal of Graph Theory and Applications, vol. 6, no. 2, pp. 317–325, 2018
  4. Casinillo, L. F., “Odd and even repetition sequences of independent domination number”, Notes on Number Theory and Discrete Mathematics, vol. 26, no. 1, pp. 8-20, 2020
  5. Casinillo, L. F., Lagumbay, E. T. & Abad, H. R. F., “A note on connected interior domination in join and corona of two graphs,” IOSR Journal of Mathematics, vol. 13, no. 2, pp. 66–69, 2017
  6. Chartrand, G. and Zhang, P., A First Course in Graph Theory, New York: Dover Publication, Inc., 2012
  7. Cockayne, E. J., & Hedetniemi, S. T., “Towards a theory of domination in graph,” Networks Advanced Topics, vol. 7, pp. 247–261, 1977
  8. Goddard, W. & Henning, M. A., “Independent domination in graph: A survey and recent results,” Discrete Mathematics, vol. 313, pp. 839-854, 2013
  9. Haynes, T. W., Hedetniemi, S. T., & Slater, P. J., Fundamentals of Domination in Graphs, New York: Marcel Dekker, 1998
  10. Ore, O., Theory of Graphs, American Mathematical Society Provedence, R. I., 1962
  11. Perderson, A. S., & Vestergaard, P. D., “The number of independent sets in unicyclic graphs,” Discrete Applied Mathematics, vol. 152, pp. 246–256, 2005
  12. Tarr, J. M., Domination in Graphs. Graduate Theses and Dissertations. Retrieved from https://scholarcommons.usf.edu/etd/1786, 2010
  13. Samanmoo, R., Trakultraipruk, N., & Ananchuen, N., “γ-Independent dominating graphs of paths and cycles,” Maejo International Journal of Science and Technology, vol. 13, no. 3, pp. 245-256, 2019

Last update:

No citation recorded.

Last update:

No citation recorded.