Affordable Access

Access to the full text

Connected Resolvability of Graphs

Authors
  • Saenpholphat, Varaporn1
  • Zhang, Ping1
  • 1 Western Michigan University, Department of Mathematics and Statistics, Kalamazoo, MI, 49008, USA , Kalamazoo
Type
Published Article
Journal
Czechoslovak Mathematical Journal
Publisher
Kluwer Academic Publishers-Plenum Publishers
Publication Date
Dec 01, 2003
Volume
53
Issue
4
Pages
827–840
Identifiers
DOI: 10.1023/B:CMAJ.0000024524.43125.cd
Source
Springer Nature
Keywords
License
Yellow

Abstract

For an ordered set W = {w1, w2,..., wk} of vertices and a vertex v in a connected graph G, the representation of v with respect to W is the k-vector r(v|W) = (d(v, w1), d(v, w2),... d(v, wk)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W. A resolving set for G containing a minimum number of vertices is a basis for G. The dimension dim(G) is the number of vertices in a basis for G. A resolving set W of G is connected if the subgraph 〈W〉 induced by W is a nontrivial connected subgraph of G. The minimum cardinality of a connected resolving set in a graph G is its connected resolving number cr(G). Thus 1 ≤ dim(G) ≤ cr(G) ≤ n−1 for every connected graph G of order n ≥ 3. The connected resolving numbers of some well-known graphs are determined. It is shown that if G is a connected graph of order n ≥ 3, then cr(G) = n−1 if and only if G = Kn or G = K1,n−1. It is also shown that for positive integers a, b with a ≤ b, there exists a connected graph G with dim(G) = a and cr(G) = b if and only if \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\left( {a,b} \right) \notin \left\{ {\left( {1,k} \right):k = 1\;{\text{or}}\;k \geqslant 3} \right\}$$ \end{document} Several other realization results are present. The connected resolving numbers of the Cartesian products G × K2 for connected graphs G are studied.

Report this publication

Statistics

Seen <100 times