Abstract
Let G be a graph with vertex set V(G), and let d(u, w) denote the length of a \(u-w\) geodesic in G. For two distinct \(x,y \in V(G)\), let \(R\{x,y\}=\{z \in V(G): d(x,z) \ne d(y,z)\}\). For a function g defined on V(G) and for \(U \subseteq V(G)\), let \(g(U)=\sum _{s\in U}g(s)\). A real-valued function \(g: V(G) \rightarrow [0,1]\) is a resolving function of G if \(g(R\{x,y\}) \ge 1\) for any distinct \(x,y \in V(G)\). In this paper, we introduce the fractional Maker-Breaker resolving game (FMBRG). The game is played on a graph G by Resolver and Spoiler (denoted by \(R^*\) and \(S^*\), respectively) who alternately assigns non-negative real values on V(G) such that its sum is at most one on each turn. Moreover, the total value assigned, by \(R^*\) and \(S^*\), on each vertex over time cannot exceed one. \(R^*\) wins if the total values assigned on V(G) by \(R^*\), after finitely many turns, form a resolving function of G, whereas \(S^*\) wins if \(R^*\) fails to assign values on V(G) to form a resolving function of G. We obtain some general results on the outcome of the FMBRG and determine the outcome of the FMBRG for some graph classes.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Arumugam, S., Mathew, V.: The fractional metric dimension of graphs. Discret. Math. 312, 1584–1590 (2012)
Arumugam, S., Mathew, V., Shen, J.: On fractional metric dimension of graphs. Discrete Math. Algorithms Appl. 5, 1350037 (2013)
Beck, J.: Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, Cambridge (2008)
Beerliova, Z., et al.: Network discovery and verification. IEEE J. Sel. Areas Commun. 24, 2168–2181 (2006)
Brešar, B., Klavžar, S., Rall, D.F.: Domination game and an imagination strategy. SIAM J. Discret. Math. 24, 979–991 (2010)
Currie, J., Oellermann, O.R.: The metric dimension and metric independence of a graph. J. Comb. Math. Comb. Comput. 39, 157–167 (2001)
Duchêne, E., Gledel, V., Parreau, A., Renault, G.: Maker-Breaker domination game. Discret. Math. 343(9) (2020). #111955
Erdös, P., Selfridge, J.L.: On a combinatorial game. J. Comb. Theory Ser. A 14, 298–301 (1973)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976)
Hefetz, D., Krivelevich, M., Stojaković, M., Szabó, T.: The neighborhood conjecture. Positional Games. OS, vol. 44, pp. 113–139. Springer, Basel (2014). https://doi.org/10.1007/978-3-0348-0825-5_9
Hernando, C., Mora, M., Pelayo, I.M., Seara, C., Wood, D.R.: Extremal graph theory for metric dimension and diameter. Electron. J. Comb. (2010). #R30
Kang, C.X.: On the fractional strong metric dimension of graphs. Discret. Appl. Math. 213, 153–161 (2016)
Kang, C.X., Klavžar, S., Yero, I.G., Yi, E.: Maker-Breaker resolving game. arXiv:2005.13242 (2020)
Kang, C.X., Yi, E.: The fractional strong metric dimension of graphs. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 84–95. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03780-6_8
Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discret. Appl. Math. 70, 217–229 (1996)
Klein, D.J., Yi, E.: A comparison on metric dimension of graphs, line graphs, and line graphs of the subdivision graphs. Eur. J. Pure Appl. Math. 5(3), 302–316 (2012)
Nowakawski, R., Winkler, P.: Vertex-to-vertex pursuit in a graph. Discret. Math. 43, 235–239 (1983)
Sebö, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29, 383–393 (2004)
Slater, P.J.: Leaves of trees. Congr. Numer. 14, 549–559 (1975)
Yi, E.: The fractional metric dimension of permutation graphs. Acta Math. Sin. Engl. Ser. 31, 367–382 (2015). https://doi.org/10.1007/s10114-015-4160-5
Acknowledgement
The author thanks the anonymous referees for some helpful comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Yi, E. (2020). Fractional Maker-Breaker Resolving Game. In: Wu, W., Zhang, Z. (eds) Combinatorial Optimization and Applications. COCOA 2020. Lecture Notes in Computer Science(), vol 12577. Springer, Cham. https://doi.org/10.1007/978-3-030-64843-5_39
Download citation
DOI: https://doi.org/10.1007/978-3-030-64843-5_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64842-8
Online ISBN: 978-3-030-64843-5
eBook Packages: Computer ScienceComputer Science (R0)