Resolving dominating partitions in graphs. (English) Zbl 1464.05290
Summary: A partition \(\Pi = \{ S_1 , \ldots , S_k \}\) of the vertex set of a connected graph \(G\) is called a resolving partition of \(G\) if for every pair of vertices \(u\) and \(v\), \(d ( u , S_j ) \neq d ( v , S_j )\), for some part \(S_j\). The partition dimension \(\beta_p ( G )\) is the minimum cardinality of a resolving partition of \(G\). A resolving partition \(\Pi\) is called resolving dominating if for every vertex \(v\) of \(G\), \(d ( v , S_j ) = 1\), for some part \(S_j\) of \(\Pi \). The dominating partition dimension \( \eta_p ( G )\) is the minimum cardinality of a resolving dominating partition of \(G\).
In this paper we show, among other results, that \(\beta_p ( G ) \leq \eta_p ( G ) \leq \beta_p ( G ) + 1\). We also characterize all connected graphs of order \(n \geq 7\) satisfying any of the following conditions: \( \eta_p ( G ) = n\), \(\eta_p ( G ) = n - 1\), \(\eta_p ( G ) = n - 2\) and \(\beta_p ( G ) = n - 2\). Finally, we present some tight Nordhaus-Gaddum bounds for both the partition dimension \(\beta_p ( G )\) and the dominating partition dimension \(\eta_p ( G )\).
In this paper we show, among other results, that \(\beta_p ( G ) \leq \eta_p ( G ) \leq \beta_p ( G ) + 1\). We also characterize all connected graphs of order \(n \geq 7\) satisfying any of the following conditions: \( \eta_p ( G ) = n\), \(\eta_p ( G ) = n - 1\), \(\eta_p ( G ) = n - 2\) and \(\beta_p ( G ) = n - 2\). Finally, we present some tight Nordhaus-Gaddum bounds for both the partition dimension \(\beta_p ( G )\) and the dominating partition dimension \(\eta_p ( G )\).
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.) |
Keywords:
resolving partition; resolving dominating partition; metric location; resolving domination; partition dimension; dominating partition dimensionReferences:
| [1] | Brigham, R. C.; Chartrand, G.; Dutton, R. D.; Zhang, P., Resolving domination in graphs, Math. Bohem., 128, 1, 25-36 (2003) · Zbl 1010.05048 |
| [2] | Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L., On the metric dimension of infinite graphs, Discrete Appl. Math., 160, 18, 2618-2626 (2012) · Zbl 1254.05051 |
| [3] | Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L., Locating-dominating codes: bounds and extremal cardinalities, Appl. Math. Comput., 220, 38-45 (2013) · Zbl 1329.94021 |
| [4] | Cáceres, J.; Hernando, C.; Mora, M.; Pelayo, I. M.; Puertas, M. L.; Seara, C.; Wood, D. R., On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math., 21, 2, 423-441 (2007) · Zbl 1139.05314 |
| [5] | Chappell, G. G.; Gimbel, J.; Hartman, C., Bounds on the metric and partition dimensions of a graph, Ars Combin., 88, 349-366 (2008) · Zbl 1224.05133 |
| [6] | Chartrand, G.; Eroh, L.; Johnson, M. A.; Oellermann, O. R., Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105, 1-3, 99-113 (2000) · Zbl 0958.05042 |
| [7] | Chartrand, G.; Salehi, E.; Zhang, P., The partition dimension of a graph, Aequationes Math., 59, 45-54 (2000) · Zbl 0939.05029 |
| [8] | Cockayne, E. J.; Hedetniemi, S. T., Towards a theory of domination in graphs, Networks, 7, 3, 247-261 (1977) · Zbl 0384.05051 |
| [9] | Fehr, M.; Gosselin, S.; Oellermann, O. R., The partition dimension of Cayley digraphs, Aequationes Math., 71, 1-2, 1-18 (2006) · Zbl 1086.05024 |
| [10] | Goddard, W., Mastermind revised, J. Combin. Math. Combin. Comput. Sci., 51, 215-220 (2004) · Zbl 1082.91003 |
| [11] | González, A.; Hernando, C.; Mora, M., Metric-locating-dominating sets of graphs for constructing related subsets of vertices, Appl. Math. Comput., 332, 449-456 (2018) · Zbl 1427.05158 |
| [12] | González Yero, I.; Jakovac, M.; Kuziak, D.; Taranenko, A., The partition dimension of strong product graphs and Cartesian product graphs, Discrete Math., 331, 43-52 (2014) · Zbl 1297.05187 |
| [13] | Grigorious, C.; Stephen, S.; Rajan, B.; Miller, M.; William, A., On the partition dimension of a class of circulant graphs, Inform. Process. Lett., 114, 353-356 (2014) · Zbl 1284.05081 |
| [14] | Harary, F.; Melter, R., On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118 |
| [15] | Haynes, T. W.; Henning, M. A.; Howard, J., Locating and total dominating sets in trees, Discrete Appl. Math., 154, 1293-1300 (2006) · Zbl 1091.05051 |
| [16] | Haynes, T.; Knisley, D.; Seier, E.; Zou, Y., A quantitative analysis of secondary RNA structure using domination based parameters on trees, BMC Bioinf., 7, 1, 108 (2006) |
| [17] | Henning, M. A.; Oellermann, O. R., Metric-locating-dominating sets in graphs, Ars Combin., 73, 129-141 (2004) · Zbl 1073.05051 |
| [18] | Hernando, C.; Mora, M.; Pelayo, I. M., Nordhaus-Gaddum bounds for locating-domination, European J. Combin., 36, 1-6 (2014) · Zbl 1284.05197 |
| [19] | Hernando, C.; Mora, M.; Pelayo, I. M.; Seara, C.; Wood, D. R., Extremal graph theory for metric dimension and diameter, Electron. J. Combin., 17, 1, R30 (2010) · Zbl 1219.05051 |
| [20] | McCoy, J.; Henning, M. A., Locating and paired-dominating sets in graphs, Discrete Appl. Math., 157, 15, 3268-3280 (2009) · Zbl 1213.05196 |
| [21] | Ore, O., (Theory of Graphs. Theory of Graphs, American Mathematical Society Colloquium Publications, vol. 38 (1962), American Mathematical Society: American Mathematical Society Providence, RI) · Zbl 0105.35401 |
| [22] | Rodríguez-Velázquez, J. A.; González Yero, I.; Lemanska, M., On the partition dimension of trees, Discrete Appl. Math., 166, 204-209 (2014) · Zbl 1283.05225 |
| [23] | Saenpholphat, V.; Zhang, P., Conditional resolvability in graphs: a survey, Int. J. Math. Math. Sci., 38, 1997-2017 (2004) · Zbl 1061.05028 |
| [24] | Sasireka, A.; Nandhukishore, A. H., Applications of dominating set of graph in computer networks, Int. J. Eng. Sci. Res. Technol., 3, 1, 170-173 (2014) |
| [25] | Sebo, A.; Tannier, E., On metric generators of graphs, Math. Oper. Res., 29, 2, 383-393 (2004) · Zbl 1082.05032 |
| [26] | Slater, P. J., Leaves of trees, (Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing. Proc. 6th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Congr. Numer., vol. 14 (1975)), 549-559 · Zbl 0316.05102 |
| [27] | Stephen, S.; Rajan, B.; Grigorious, C.; William, A., Resolving-power dominating sets, Appl. Math. Comput., 256, 778-785 (2015) · Zbl 1338.05218 |
| [28] | Tomescu, I., Discrepancies between metric dimension and partition dimension of a connected graph, Discrete Math., 308, 5026-5031 (2008) · Zbl 1184.05033 |
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.
