×

zbMATH — the first resource for mathematics

The domination numbers of cylindrical grid graphs. (English) Zbl 1223.05214
Summary: Let \(\gamma (P_m \square C_n)\) denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs \(P_m\), the path of length \(m,\, m \geqslant 2\) and the graph \(C_n\), the cycle of length \(n,\, n \geqslant 3\). In this paper, methods to find the domination numbers of graphs of the form \(P_m \square C_n\) with \(n geqslant 3\) and \(m = 2, 3\) and 4 are proposed. Moreover, bounds on domination numbers of the graphs \(P_{5} \square C_n, n \geqslant 3\) are found. The methods that are used to prove that results readily lead to algorithms for finding minimum dominating sets of the above mentioned graphs.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barrett, C.L.; Reidys, C.M., Elements of a theory of computer simulation I: sequential CA over random graphs, Appl. math. comput., 98, 2-3, 241-259, (1999) · Zbl 0927.68114
[2] Biswas, Anjan; Milovic, Daniela, Optical solitons in a parabolic law media with fourth order dispersion, Appl. math. comput., 208, 1, 299-302, (2009) · Zbl 1155.35448
[3] Biswas, Anjan; Ranasinghe, Arjuna, 1-soliton solution of kadomtsev – petviashvili equation with power law nonlinearity, Appl. math. comput., 214, 2, 645-647, (2009) · Zbl 1172.35476
[4] Biswas, Anjan, Soliton-soliton interaction with dual-power law nonlinearity, Appl. math. comput., 198, 2, 605-612, (2008) · Zbl 1166.35365
[5] Chang, T.Y.; Clark, W.E., The domination numbers of the 5×n and 6×n grid graphs, J. graph theor., 17, 81-107, (1993) · Zbl 0780.05030
[6] Clark, B.N.; Colbourn, C.J.; Johnson, D.S., Unit disk graphs, Discrete math., 86, 165-177, (1990) · Zbl 0739.05079
[7] Dehmer, Matthias, Information processing in complex networks: graph entropy and information functionals, Appl. math. comput., 201, 1-2, 82-94, (2008) · Zbl 1152.05361
[8] Dehmer, Matthias; Emmert-Streib, Frank; Kilian, Jrgen, A similarity measure for graphs with low computational complexity, Appl. math. comput., 182, 1, 447-459, (2006) · Zbl 1111.05019
[9] Dunbar, J.E.; Hedetniemi, S.T.; Henning, M.A.; Slater, P.J., Signed domination in graphs, graph theory, combinatorics, and applications, (1995), John Wiley & Sons, pp. 311-322
[10] El-Zahar, M.H.; Pareek, C.M., Domination number of products of graphs, Ars combin., 31, 223-227, (1991) · Zbl 0746.05067
[11] El-Zahar, M.H.; Khamis, S.M.; Nazzal, Kh. M., On the domination number of the Cartesian product of the cycle of length n and any graph, Discrete appl. math., 155, 515-522, (2007) · Zbl 1112.05074
[12] Faudree, R.J.; Schelp, R.H., The domination number for the product of graphs, Congr. numer., 79, 29-33, (1990) · Zbl 0862.05060
[13] Favaron, O., Signed domination in regular graphs, Discrete math., 158, 287-293, (1996) · Zbl 0861.05033
[14] Gravier, S., Total domination number of grid graphs, Discrete appl. math., 121, 119-128, (2002) · Zbl 0995.05109
[15] Harary, F., Graph theory, (1969), Addison Weslay Reading Mass · Zbl 0797.05064
[16] Hartnell, B.L.; Rall, D.F., On vizing’s conjecture, Congr. numer., 82, 87-96, (1991) · Zbl 0764.05092
[17] Haynes, T.; Hedetniemi, S.; Slater, P., Fundamentals of domination in graphs, (1998), Marcel Dekker New York · Zbl 0890.05002
[18] Hedetniemi, S.T.; Laskar, R.C., Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete math., 86, 1-3, 257-277, (1990) · Zbl 0733.05076
[19] Hsieh, Sun-Yuan; Huang, Chao-Wen; Chou, Hsin-Hung, A DNA-based graph encoding scheme with its applications to graph isomorphism problems, Appl. math. comput., 203, 2, 502-512, (2008) · Zbl 1228.68020
[20] Hsieh, Sun-Yuan; Chen, Ming-Yu, A DNA-based solution to the graph isomorphism problem using adlemanlipton model with stickers, Appl. math. comput., 197, 2, 672-686, (2008) · Zbl 1171.68009
[21] Inohara, Takehiro, Characterization of clusterability of signed graph in terms of newcomb’s balance of sentiments, Appl. math. comput., 133, 1, 93-104, (2002) · Zbl 1023.05072
[22] Jacobson, M.S.; Kinch, L.F., On the domination of the products of graphs I, Ars combin., 18, 33-44, (1983) · Zbl 0566.05050
[23] Klavzar, S.; Seifter, N., Dominating Cartesian products of cycles, Discrete appl. math., 59, 129-136, (1995) · Zbl 0824.05037
[24] Mayeda, W., Synthesis of switching functions by linear graph theory, IBM J. res. develop., 4, 3, 321-328, (1960) · Zbl 0111.32104
[25] Morgenstern, O., The collaboration between oskar morgenstern and John von Neumann on the theory of games, J. eco. literat., 14, 805-816, (1976)
[26] Vizing, V.G., The Cartesian product of graphs, Vychisl sistemy, 9, 30-43, (1963) · Zbl 0931.05033
[27] Xu, Xiao-Ge; Meng, Xiang-Hua; Gao, Yi-Tian; Wen, Xiao-Yong, Analytic N-solitary-wave solution of a variable-coefficient gardner equation from fluid dynamics and plasma physics, Appl. math. comput., 210, 2, 313-320, (2009) · Zbl 1162.76013
[28] El-Zahar, M.; Pareek, C.M., Domination number of products of graphs, Ars combinatoria, 31, 223-227, (1991) · Zbl 0746.05067
[29] Zakeri, Gholam-Ali, Analysis of ray tube area in geometrical shock dynamics, Appl. math. comput., 217, 2, 830-836, (2010) · Zbl 1432.76149
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.