ON THE METRIC DIMENSIONS FOR SETS OF VERTICES 1

被引:3
作者
Hakanen, Anni [1 ]
Junnila, Ville [1 ]
Laihonen, Tero [1 ]
Puertas, Maria Luz [2 ]
机构
[1] Univ Turku, Dept Math & Stat, Turku, Finland
[2] Univ Almeria, Dept Math, Almeria, Spain
关键词
resolving set; metric dimension; resolving several objects; block; design; rook's graph; flower snark; GRAPHS;
D O I
10.7151/dmgt.2367
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Resolving sets were originally designed to locate vertices of a graph one at a time. For the purpose of locating multiple vertices of the graph si-multaneously, {t} -resolving sets were recently introduced. In this paper, we present new results regarding the {t} -resolving sets of a graph. In addition to proving general results, we consider {2} -resolving sets in rook's graphs and connect them to block designs. We also introduce the concept of t -solid-resolving sets, which is a natural generalisation of solid-resolving sets. We prove some general bounds and characterisations for t-solid-resolving sets and show how t -solid-and {t} -resolving sets are connected to each other. In the last part of the paper, we focus on the infinite graph family of flower snarks. We consider the t -solid-and {t} -metric dimensions of flower snarks. In two proofs regarding flower snarks, we use a new computer-aided reduction-like approach.
引用
收藏
页码:245 / 275
页数:31
相关论文
共 16 条
  • [1] Network discovery and verification
    Beerliova, Zuzana
    Eberhard, Felix
    Erlebach, Thomas
    Hall, Alexander
    Hoffmann, Michael
    Mihal'ak, Matus
    Ram, L. Shankar
    [J]. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2006, 24 (12) : 2168 - 2181
  • [2] On the metric dimension of infinite graphs
    Caceres, J.
    Hernando, C.
    Mora, M.
    Pelayo, I. M.
    Puertas, M. L.
    [J]. DISCRETE APPLIED MATHEMATICS, 2012, 160 (18) : 2618 - 2626
  • [3] On the metric dimension of cartesian products of graphs
    Caceres, Jose
    Hernando, Carmen
    Mora, Merce
    Pelayo, Ignacio M.
    Puertas, Maria L.
    Seara, Carlos
    Wood, David R.
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2007, 21 (02) : 423 - 441
  • [4] Resolvability in graphs and the metric dimension of a graph
    Chartrand, G
    Eroh, L
    Johnson, MA
    Oellermann, OR
    [J]. DISCRETE APPLIED MATHEMATICS, 2000, 105 (1-3) : 99 - 113
  • [5] Colbourn CJ., 2007, CRC HDB COMBINATORIA
  • [6] The k-metric dimension of the lexicographic product of graphs
    Estrada-Moreno, Alejandro
    Yero, Ismael G.
    Rodriguez-Velazquez, Juan A.
    [J]. DISCRETE MATHEMATICS, 2016, 339 (07) : 1924 - 1934
  • [7] The solid-metric dimension
    Hakanen, Anni
    Junnila, Ville
    Laihonen, Tero
    [J]. THEORETICAL COMPUTER SCIENCE, 2020, 806 (806) : 156 - 170
  • [8] On {l}-Metric Dimensions in Graphs
    Hakanen, Anni
    Laihonen, Tero
    [J]. FUNDAMENTA INFORMATICAE, 2018, 162 (2-3) : 143 - 160
  • [9] Harary F., 1976, ARS COMBINATORIA, V2, P191
  • [10] ON CLASSES OF REGULAR GRAPHS WITH CONSTANT METRIC DIMENSION
    Imran, Muhammad
    Bokhary, Syed Ahtsham ul Haq
    Ahmad, Ali
    Semanicova-Fenovcikova, Andrea
    [J]. ACTA MATHEMATICA SCIENTIA, 2013, 33 (01) : 187 - 206