Top

Journal of Combinatorial Optimization

Published in:

01-07-2013

Metric dimension of some distance-regular graphs

Authors: Jun Guo, Kaishun Wang, Fenggao Li

Published in: Journal of Combinatorial Optimization | Issue 1/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A resolving set of a graph is a set of vertices with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. In this paper, we construct a resolving set of Johnson graphs, doubled Odd graphs, doubled Grassmann graphs and twisted Grassmann graphs, respectively, and obtain the upper bounds on the metric dimension of these graphs.

previous article Critical edges/nodes for the minimum spanning tree problem: complexity and approximation

next article On the optimality of the TLS algorithm for solving the online-list scheduling problem with two job types on a set of multipurpose machines

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Bailey RF, Cameron PJ (2011) Base size, metric dimension an other invariants of groups and graphs. Bull Lond Math Soc 43:209–242 MathSciNetMATHCrossRef

Bailey RF, Meagher K (2011) On the metric dimension of Grassmann graphs. Discrete Math Theor Comput Sci. 13:97–104 MathSciNet

Bailey RF, Cáceres J, Garijo D, González A, Márquez A, Meagher K, Puertas ML (2011) Resolving sets in Johnson and Kneser graphs. Preprint

Beutelspacher A (1978) Partition of finite vector spaces: an application of Frobenius number in geometry. Arch Math 31:202–208 MathSciNetMATHCrossRef

Brouwer AE, Cohen AM, Neumaier A (1989) Distance-regular graphs. Springer, Berlin MATHCrossRef

Chartrand G, Eroh L, Johnson MA, Oellermann OR (2000) Resolvability in graphs and the metric dimension of a graph. Discrete Appl Math 105:99–113 MathSciNetMATHCrossRef

Chvátal V (1983) Mastermind. Combinatorica 3:325–329 MathSciNetMATHCrossRef

Feng M, Wang K (2012) On the metric dimension of bilinear forms graphs. Discrete Math. 312:1266–1268 MathSciNetMATHCrossRef

Harary F, Melter RA (1976) On the metric dimension of a graph. Ars Comb 2:191–195; 4:318 (1977) MathSciNetMATH

Khuller S, Raghavachari B, Rosenfeld A (1996) Landrnarks in graphs. Discrete Appl Math 70:217–229 MathSciNetMATHCrossRef

Sebő A, Tannier (2004) On metric generators of graphs. Math Oper Res 29:383–393 MathSciNetCrossRef

Slater PJ (1975) Leaves of trees. Congr Numer 14:549–559 MathSciNet

van Dam ER, Koolen JH (2005) A new family of distance-regular graphs with unbounded diameter. Invent Math 162:189–193 MathSciNetMATHCrossRef

Title: Metric dimension of some distance-regular graphs
Authors: Jun Guo
Kaishun Wang
Fenggao Li
Publication date: 01-07-2013
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2013
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9459-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2013

On the outer-connected domination in graphs

Optimal key tree structure for two-user replacement and deletion problems

The three-dimensional matching problem in Kalmanson matrices

Critical edges/nodes for the minimum spanning tree problem: complexity and approximation

Independent dominating sets in regular graphs

Parameterized complexity of k-anonymity: hardness and tractability

Premium Partner