×

The domination complexity and related extremal values of large 3D torus. (English) Zbl 1398.05154

Summary: Domination is a structural complexity of chemical molecular graphs. A dominating set in a (molecular) graph \(G = \left(V, E\right)\) is a subset \(S \subseteq V\) such that each vertex in \(V \backslash S\) is adjacent to at least one vertex in \(S\). The domination number \(\gamma \left(G\right)\) of a graph \(G\) is the minimum size of a dominating set in \(G\). In this paper, computer-aided approaches for obtaining bounds for domination number on torus graphs are here considered, and many new exact values and bounds are obtained.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C90 Applications of graph theory
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs, (1998), Marcel Dekker, New York, NY, USA · Zbl 0890.05002
[2] Hedetniemi, S. T.; Laskar, R. C., Bibliography on domination in graphs and some basic definitions of domination parameters, Discrete Mathematics, 86, 1-3, 257-277, (1990) · Zbl 0733.05076 · doi:10.1016/0012-365X(90)90365-O
[3] Hayat, S.; Wang, S.; Liu, J.-B., Valency-based topological descriptors of chemical networks and their applications, Applied Mathematical Modelling, 60, 164-178, (2018) · Zbl 1480.92243 · doi:10.1016/j.apm.2018.03.016
[4] Wang, S.; Wei, B., A note on the independent domination number versus the domination number in bipartite graphs, Czechoslovak Mathematical Journal, 67, 2, 533-536, (2017) · Zbl 1458.05208 · doi:10.21136/CMJ.2017.0068-16
[5] Ji, S.; Wang, S., On the sharp lower bounds of Zagreb indices of graphs with given number of cut vertices, Journal of Mathematical Analysis and Applications, 458, 1, 21-29, (2018) · Zbl 1373.05041 · doi:10.1016/j.jmaa.2017.09.005
[6] Gao, Y.; Zhu, E.; Shao, Z.; Gutman, I.; Klobučar, A., Total domination and open packing in some chemical graphs, Journal of Mathematical Chemistry, 56, 5, 1481-1492, (2018) · Zbl 1390.92162 · doi:10.1007/s10910-018-0877-6
[7] Liu, J.-B.; Pan, X.-F.; Yu, L.; Li, D., Complete characterization of bicyclic graphs with minimal Kirchhoff index, Discrete Applied Mathematics, 200, 95-107, (2016) · Zbl 1329.05159 · doi:10.1016/j.dam.2015.07.001
[8] Javad Ebrahimi, B.; Jahanbakht, N.; Mahmoodian, E. S., Vertex domination of generalized Petersen graphs, Discrete Mathematics, 309, 13, 4355-4361, (2009) · Zbl 1181.05066 · doi:10.1016/j.disc.2009.01.018
[9] Liu, J.; Zhang, X., The exact domination number of generalized Petersen graphs \(P \left(n, k\right)\) with \(n = 2 k\) and \(n = 2 k + 2^\ast\), Computational and Applied Mathematics, 33, 2, 497-506, (2014) · Zbl 1306.05183 · doi:10.1007/s40314-013-0077-8
[10] Fu, X.; Yang, Y.; Jiang, B., On the domination number of generalized Petersen graphs \(P \left(n, 2\right)\), Discrete Mathematics, 309, 8, 2445-2451, (2009) · Zbl 1211.05112 · doi:10.1016/j.disc.2008.05.026
[11] Fu, X.; Yang, Y.; Jiang, B., On the domination number of generalized Petersen graphs P(n,3), Ars Combinatoria, 84, 373-383, (2007) · Zbl 1212.05205
[12] Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A., Covering Codes, (1997), Elsevier, Amsterdam, Netherlands · Zbl 0874.94001
[13] Klavžar, S.; Ma, M., The domination number of exchanged hypercubes, Information Processing Letters, 114, 4, 159-162, (2014) · Zbl 1294.05123 · doi:10.1016/j.ipl.2013.12.005
[14] Castro, A.; Klavžar, S.; Mollard, M.; Rho, Y., On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes, Computers & Mathematcs with Applications, 61, 9, 2655-2660, (2011) · Zbl 1221.05257 · doi:10.1016/j.camwa.2011.03.012
[15] Ivančo, J.; Zelinka, B., Domination in Kneser graphs, Mathematica Bohemica, 118, 2, 147-152, (1993) · Zbl 0778.05043
[16] Gorodezky, I., Domination in Kneser Graphs, [M.S. thesis], (2007), University of Waterloo, Waterloo, Canada
[17] Wang, S.; Wang, C.; Liu, J.-B., On extremal multiplicative Zagreb indices of trees with given domination number, Applied Mathematics and Computation, 332, 338-350, (2018) · Zbl 1427.05081 · doi:10.1016/j.amc.2018.03.058
[18] Östergård, P.; Shao, Z.; Xu, X., Bounds on the domination number of Kneser graphs, Ars Mathematica Contemporanea, 9, 2, 197-205, (2015)
[19] Klavžar, S.; Seifter, N., Dominating Cartesian products of cycles, Discrete Applied Mathematics, 59, 2, 129-136, (1995) · Zbl 0824.05037 · doi:10.1016/0166-218X(93)E0167-W
[20] El-Zahar, M. H.; Shaheen, R. S., On the domination number of the product of two cycles, Ars Combinatoria, 84, 51-64, (2007) · Zbl 1212.05192
[21] Crevals, S.; Östergård, P. R. J., On the domination number of 2-dimensional torus graphs, Utilitas Mathematica, 106, 289-300, (2018) · Zbl 1393.05197
[22] Alanko, S.; Crevals, S.; Isopoussu, A.; Östergård, P.; Pettersson, V., Computing the domination number of grid graphs, The Electronic Journal of Combinatorics, 18, 1, 141, (2011) · Zbl 1222.05194
[23] Gonçalves, D.; Pinlou, A.; Rao, M.; Thomassé, S., The domination number of grids, SIAM Journal on Discrete Mathematics, 25, 3, 1443-1453, (2011) · Zbl 1237.05150 · doi:10.1137/11082574
[24] Zhao, Q.; Li, S., On the maximum Zagreb indices of graphs with k cut vertices, Acta Applicandae Mathematicae, 111, 1, 93-106, (2010) · Zbl 1190.92050 · doi:10.1007/s10440-009-9534-1
[25] Estes, J.; Wei, B., Sharp bounds of the Zagreb indices of k-trees, Journal of Combinatorial Optimization, 27, 2, 271-291, (2014) · Zbl 1318.90070 · doi:10.1007/s10878-012-9515-6
[26] Ma, J.; Shi, Y.; Wang, Z.; Yue, J., On Wiener polarity index of bicyclic networks, Scientific Reports, 6, 1, article 19066, (2016) · doi:10.1038/srep19066
[27] Bertolo, R.; Ostergard, P. R. J.; Weakley, W. D., An updated table of binary/ternary mixed covering codes, Journal of Combinatorial Designs, 12, 3, 157-176, (2004) · Zbl 1054.94022 · doi:10.1002/jcd.20008
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.