The difference between the metric dimension and the determining number of a graph. (English) Zbl 1338.05063
Summary: We study the maximum value of the difference between the metric dimension and the determining number of a graph as a function of its order. We develop a technique that uses functions related to locating-dominating sets to obtain lower and upper bounds on that maximum, and exact computations when restricting to some specific families of graphs. Our approach requires very diverse tools and connections with well-known objects in graph theory; among them: a classical result in graph domination by Ore, a Ramsey-type result by Erdos and Szekeres, a polynomial time algorithm to compute distinguishing sets and determining sets of twin-free graphs, \(k\)-dominating sets, and matchings.
MSC:
| 05C12 | Distance in graphs |
Keywords:
resolving set; metric dimension; determining set; determining number; locating-dominating set; locating-domination numberReferences:
| [1] | Babai, L., On the complexity of canonical labeling of strongly regular graphs, SIAM J. Comput., 9, 1, 212-216 (1980) · Zbl 0446.68052 |
| [2] | Bailey, R. F.; Cameron, P. J., Base size, metric dimension and other invariants of groups and graphs, Bull. Lond. Math. Soc., 43, 2, 209-242 (2011) · Zbl 1220.05030 |
| [3] | Bollobás, B.; Cockayne, E. J., Graph-theoretic parameters concerning domination, independence, and irredundance, J. Graph Theory, 3, 3, 241-249 (1979) · Zbl 0418.05049 |
| [4] | Boutin, D. L., Identifying graph automorphisms using determining sets, Electron. J. Combin., 13, 1 (2006), (Research Paper 78, 12) · Zbl 1111.05043 |
| [5] | Cáceres, J.; Garijo, D.; Puertas, M. L.; Seara, C., On the determining number and the metric dimension of graphs, Electron. J. Combin., 17, 1 (2010), (Research Paper 63, 20) · Zbl 1215.05081 |
| [6] | 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), (electronic) · Zbl 1139.05314 |
| [7] | Charon, I.; Honkala, I.; Hudry, O.; Lobstein, A., Structural properties of twin-free graphs, Electron. J. Combin., 14, 1 (2007), (Research Paper 16, 15) · Zbl 1113.05085 |
| [8] | 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 |
| [9] | Chartrand, G.; Zhang, P., Chromatic graph theory, Discrete Mathematics and its Applications (Boca Raton) (2009), CRC Press: CRC Press Boca Raton, FL · Zbl 1169.05001 |
| [10] | Chellali, M.; Favaron, O.; Hansberg, A.; Volkmann, L., k-Domination and k-independence in graphs: a survey, Graphs Combin., 28, 1, 1-55 (2012) · Zbl 1234.05174 |
| [11] | Cockayne, E. J.; Gamble, B.; Shepherd, B., An upper bound for the k-domination number of a graph, J. Graph Theory, 9, 4, 533-534 (1985) · Zbl 0664.05053 |
| [12] | Cockayne, E. J.; Hedetniemi, S. T.; Slater, P. J., Matchings and transversals in hypergraphs, domination and independence in trees, J. Combin. Theory Ser. B, 26, 1, 78-80 (1979) · Zbl 0414.05036 |
| [13] | Colbourn, C. J.; Slater, P. J.; Stewart, L. K., Locating-dominating sets in series parallel networks, Congr. Numer., 56, 135-162 (1987), Sixteenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, Man., 1986) · Zbl 0646.05065 |
| [15] | Edmonds, J., Paths, trees, and flowers, Can. J. Math., 17, 449-467 (1965) · Zbl 0132.20903 |
| [16] | Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compositio Math., 2, 463-470 (1935) · Zbl 0012.27010 |
| [17] | Erwin, D.; Harary, F., Destroying automorphisms by fixing nodes, Discrete Math., 306, 24, 3244-3252 (2006) · Zbl 1109.05050 |
| [18] | Favaron, O.; Hansberg, A.; Volkmann, L., On k-domination and minimum degree in graphs, J. Graph Theory, 57, 1, 33-40 (2008) · Zbl 1211.05110 |
| [19] | Fink, J. F.; Jacobson, M. S., n-domination in graphs, (Graph Theory with Applications to Algorithms and Computer science (Kalamazoo, Mich., 1984), Wiley-Intersci. Publ. (1985), Wiley: Wiley New York), 283-300 · Zbl 0573.05049 |
| [20] | Gibbons, C. R.; Laison, J. D., Fixing numbers of graphs and groups, Electron. J. Combin., 16, 1 (2009), (Research Paper 39, 13) · Zbl 1204.05053 |
| [21] | Harary, F.; Melter, R. A., On the metric dimension of a graph, Ars Combin., 2, 191-195 (1976) · Zbl 0349.05118 |
| [22] | Hatami, H.; Hladký, J.; Král, D.; Norine, S.; Razborov, A., On the number of pentagons in triangle-free graphs, J. Combin. Theory Ser. A, 120, 3, 722-732 (2013) · Zbl 1259.05087 |
| [23] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of domination in graphs, Monographs and Textbooks in Pure and Applied Mathematics, vol. 208 (1998), Marcel Dekker Inc.: Marcel Dekker Inc. New York · Zbl 0890.05002 |
| [24] | Henning, M. A.; Kang, L.; Shan, E.; Yeo, A., On matching and total domination in graphs, Discrete Math., 308, 11, 2313-2318 (2008) · Zbl 1145.05042 |
| [25] | Hernando, C.; Mora, M.; Pelayo, I. M., Nordhaus-Gaddum bounds for locating domination, Eur. J. Combin., 36, 1-6 (2014) · Zbl 1284.05197 |
| [26] | 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 (2010), (Research Paper 30, 28) · Zbl 1219.05051 |
| [27] | Khuller, S.; Raghavachari, B.; Rosenfeld, A., Landmarks in graphs, Discrete Appl. Math., 70, 3, 217-229 (1996) · Zbl 0865.68090 |
| [28] | Ore, O., Theory of Graphs, vol. 38 (1962), American Mathematical Society Colloquium Publications: American Mathematical Society Colloquium Publications Providence, R.I. · Zbl 0105.35401 |
| [29] | Roberts, F. S., Indifference graphs, (Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968) (1969), Academic Press: Academic Press New York), 139-146 · Zbl 0193.24205 |
| [30] | Sims, C. C., Determining the conjugacy classes of a permutation group, (Computers in Algebra and Number Theory (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970). Computers in Algebra and Number Theory (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1970), SIAM-AMS Proceedings, vol. IV (1971), Amer. Math. Soc.: Amer. Math. Soc. Providence, R.I.), 191-195 · Zbl 0253.20001 |
| [31] | Slater, P. J., Leaves of trees, (Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975). Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congressus Numerantium, vol. XIV (1975), Utilitas Math: Utilitas Math Winnipeg, Man.), 549-559 · Zbl 0316.05102 |
| [32] | Slater, P. J., Dominating and reference sets in a graph, J. Math. Phys. Sci., 22, 4, 445-455 (1988) · Zbl 0656.05057 |
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.
