The Simultaneous Metric Dimension of Families Composed by Lexicographic Product Graphs
Tóm tắt
Let
$$\mathcal{G}$$
be a graph family defined on a common (labeled) vertex set V. A set
$$S\subseteq V$$
is said to be a simultaneous metric generator for
$$\mathcal{G}$$
if for every
$$G\in \mathcal{G}$$
and every pair of different vertices
$$u,v\in V$$
there exists
$$s\in S$$
such that
$$d_{G}(s,u)\ne d_{G}(s,v)$$
, where
$$d_{G}$$
denotes the geodesic distance. A simultaneous adjacency generator for
$$\mathcal{G}$$
is a simultaneous metric generator under the metric
$$d_{G,2}(x,y)=\min \{d_{G}(x,y),2\}$$
. A minimum cardinality simultaneous metric (adjacency) generator for
$$\mathcal{G}$$
is a simultaneous metric (adjacency) basis, and its cardinality the simultaneous metric (adjacency) dimension of
$$\mathcal{G}$$
. Based on the simultaneous adjacency dimension, we study the simultaneous metric dimension of families composed by lexicographic product graphs.
Tài liệu tham khảo
Brigham, R.C., Chartrand, G., Dutton, R.D., Zhang, P.: Resolving domination in graphs. Math. Bohem. 128(1), 25–36 (2003). http://mb.math.cas.cz/mb128-1/3.html
Brigham, R.C., Dutton, R.D.: Factor domination in graphs. Discret. Math. 86(1–3), 127–136 (1990). doi:10.1016/0012-365X(90)90355-L. http://www.sciencedirect.com/science/article/pii/0012365X9090355L
Chartrand, G., Saenpholphat, V., Zhang, P.: The independent resolving number of a graph. Math. Bohem. 128(4), 379–393 (2003). http://mb.math.cas.cz/mb128-4/4.html
Estrada-Moreno, A., Ramírez-Cruz, Y., Rodríguez-Velázquez, J.A.: On the adjacency dimension of graphs. Appl. Anal. Discret. Math. 10 (2016) (to appear). doi:10.2298/AADM151109022E
Estrada-Moreno, A., Rodríguez-Velázquez, J.A., Yero, I.G.: The \(k\)-metric dimension of a graph. Appl. Math. Inf. Sci. 9(6), 2829–2840 (2015). http://naturalspublishing.com/files/published/05a21265hsd7y2
Estrada-Moreno, A., Yero, I.G., Rodríguez-Velázquez, J.A.: The \(k\)-metric dimension of corona product graphs. Bull. Malays. Math. Sci. Soc. (2014) (to appear). http://math.usm.my/bulletin/pdf/acceptedpapers/2014-01-033-R1
Fernau, H., Rodríguez-Velázquez, J.A.: On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results (2013). arXiv:1309.2275 [math.CO]. http://arxiv-web3.library.cornell.edu/abs/1309.2275
Fernau, H., Rodríguez-Velázquez, J.A.: Notions of metric dimension of corona products: combinatorial and computational results. In: Computer Science-Theory and Applications. Lecture Notes in Computer Science, vol. 8476, pp. 153–166. Springer, Cham (2014)
Hammack, R., Imrich, W., Klavžar, S.: Handbook of product graphs, 2 edn. In: Discrete Mathematics and its Applications. CRC Press (2011). http://www.crcpress.com/product/isbn/9781439813041
Harary, F., Melter, R.A.: On the metric dimension of a graph. Ars Comb. 2, 191–195 (1976). http://www.ams.org/mathscinet-getitem?mr=0457289
Imran, M., ul Haq Bokhary, S.A., Ahmad, A., Semaničová-Feňovčíková, A.: On classes of regular graphs with constant metric dimension. Acta Math. Sci. 33(1), 187–206 (2013). doi:10.1016/S0252-9602(12)60204-5. http://www.sciencedirect.com/science/article/pii/S0252960212602045
Jannesari, M., Omoomi, B.: The metric dimension of the lexicographic product of graphs. Discret. Math. 312(22), 3349–3356 (2012). doi:10.1016/j.disc.2012.07.025. http://www.sciencedirect.com/science/article/pii/S0012365X12003317
Johnson, M.: Structure-activity maps for visualizing the graph variables arising in drug design. J. Biopharm. Stat. 3(2), 203–236 (1993). doi:10.1080/10543409308835060. http://www.tandfonline.com/doi/abs/10.1080/10543409308835060
Johnson, M.: Browsable structure-activity datasets. In: Carbó-Dorca, R., Mezey, P. (eds.) Advances in Molecular Similarity, chap. 8, pp. 153–170. JAI Press Inc, Stamford (1998). http://books.google.es/books?id=1vvMsHXd2AsC
Khuller, S., Raghavachari, B., Rosenfeld, A.: Landmarks in graphs. Discret. Appl. Math. 70(3), 217–229 (1996). doi:10.1016/0166-218X(95)00106-2. http://www.sciencedirect.com/science/article/pii/0166218X95001062
Okamoto, F., Phinezy, B., Zhang, P.: The local metric dimension of a graph. Math. Bohem. 135(3), 239–255 (2010). http://dml.cz/dmlcz/140702
Ramírez-Cruz, Y., Oellermann, O.R., Rodríguez-Velázquez, J.A.: Simultaneous resolvability in graph families. Electron. Notes Discret. Math. 46, 241–248 (2014). doi:10.1016/j.endm.2014.08.032. http://www.sciencedirect.com/science/article/pii/S157106531400033X
Ramírez-Cruz, Y., Oellermann, O.R., Rodríguez-Velázquez, J.A.: The simultaneous metric dimension of graph families. Discret. Appl. Math. (2015). doi:10.1016/j.dam.2015.06.012. http://www.sciencedirect.com/science/article/pii/S0166218X1500298X
Sebö, A., Tannier, E.: On metric generators of graphs. Math. Oper. Res. 29(2), 383–393 (2004). doi:10.1287/moor.1030.0070
Slater, P.J.: Leaves of trees. Congr. Numerantium 14, 549–559 (1975)