NEW COUNTING FORMULA FOR DOMINATING SETS IN PATH AND CYCLE GRAPHS

Leomarich F Casinillo


DOI: https://doi.org/10.14710/jfma.v3i2.9325

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.


Keywords


Dominating set, path, cycle, probability

Full Text:

PDF

References


Allan, R. B. & Laskar, R., “On domination and independent domination number of a graph,” Discrete Mathematics, vol. 23, pp. 73-76, 1978.

Arocha, J. L. & Llano, B., “The number of dominating k-sets of paths, cycles and wheels”, arXiv preprint:1601.01268, 2018.

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.

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.

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.

Chartrand, G. and Zhang, P., A First Course in Graph Theory, New York: Dover Publication, Inc., 2012.

Cockayne, E. J., & Hedetniemi, S. T., “Towards a theory of domination in graph,” Networks Advanced Topics, vol. 7, pp. 247–261, 1977.

Goddard, W. & Henning, M. A., “Independent domination in graph: A survey and recent results,” Discrete Mathematics, vol. 313, pp. 839-854, 2013.

Haynes, T. W., Hedetniemi, S. T., & Slater, P. J., Fundamentals of Domination in Graphs, New York: Marcel Dekker, 1998.

Ore, O., Theory of Graphs, American Mathematical Society Provedence, R. I., 1962.

Perderson, A. S., & Vestergaard, P. D., “The number of independent sets in unicyclic graphs,” Discrete Applied Mathematics, vol. 152, pp. 246–256, 2005.

Tarr, J. M., Domination in Graphs. Graduate Theses and Dissertations. Retrieved from https://scholarcommons.usf.edu/etd/1786, 2010.

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.


Refbacks

  • There are currently no refbacks.


Publisher:

Department of Mathematics, Faculty of Science and Mathematics, Diponegoro University

Mailing address: Jl. Prof Soedarto, SH, Tembalang, Semarang, Indonesia 50275

Telp./Fax             : (+6224) 70789493 / (+62224) 76480922

Website              : www.math.fsm.undip.ac.id

E-mail                : admin.math@live.undip.ac.id

 

Indexed in:

GOOGLE SCHOLAR CROSSREF SINTA PORTAL GARUDA SCILIT DIMENSIONS