The metric dimension of circulant graphs and their Cartesian products

• Autorzy: Chau K. , Gosselin S.

Identyfikatory

DOI

10.7494/OpMath.2017.37.4.509

• Języki publikacji: EN

Abstrakty

EN

Let G = (V, E) be a connected graph (or hypergraph) and let d(x,y) denote the distance between vertices x,y ∈V(G). A subset W ⊆V(G) is called a resolving set for G if for every pair ol distinct vertices x, y ∈ (G), there is w ∈W such that d(x,w) ≠d(y,w). The minimum cardinality of a resolving set for G is called the metric dimension of G, denoted by β (G). The circulant graph Cn(l, 2,... , t) has vertex set {v0, v1 …, vn-1} and edges [formula] where 0 ≤ i ≤ n — 1 and 1 ≤j ≤ t and the indices are taken modulo [formula]. In this paper we determine the exact metric dimension olthe circulant graphs Cn(l, 2,... , t). extending previous results due to Borchert and Gosselin (2013), Grigorious et al. (2014), and Vetrik (2016). In particular, we show that [formula] for large enough n, which implies that the metric dimension ol these circulants is completely determined by the congruence class ol n modulo 2t. We determine the exact value of β Cn (l, 2,.. . , i)) for n ≡ 2 mod 2t and n =≡ (t + 1) mod 2t and we give better bounds on the metric dimension ol these circulants for n ≡ 0 mod 2t and n ≡ 1 mod 2t. In addition, we bound the metric dimension ol Cartesian products ol circulant graphs.

Słowa kluczowe

EN

metric dimension; circulant graph; Cartesian product

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2017
• Tom: Vol. 37, no. 4
• Strony: 509--534
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Chau K.

• University of Winnipeg Department of Mathematics and Statistics 515 Portage Avenue, Winnipeg Manitoba, R3B 2E9, Canada

autor

Gosselin S.

• University of Winnipeg Department of Mathematics and Statistics 515 Portage Avenue, Winnipeg Manitoba, R3B 2E9, Canada

Bibliografia

• [1] R.F. Bailey, P.J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. London Math. Soc. 43 (2011), 209-242.
• [2] A. Borchert, S. Gosselin, The metric dimension of circulant graphs and Gayley hyper-graphs, (2015), to appear.
• [3] M. Buratti, Gayley, Marty and Schreier hypergraphs, Abh. Math. Sem. Univ. Hamburg 64 (1994), 151-162.
• [4] J. Caceres, C. Hernando, M. Mora, I.M. Pelayo, M.L. Puertas, C. Seara, D.R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math. 21 (2007), 423-441.
• [5] G. Chartrand, L. Eroh, M. Johnson, O.R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math. 105 (2000), 99-113.
• [6] C. Grigorious, P. Manuel, M. Miller, B. Rajan, S. Stephen, On the metric dimension of circulant and Harary graphs, Appl. Math. Comput. 248 (2014), 47-54.
• [7] F. Harary, R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195.
• [8] M. Imran, A.Q. Baig, S.A.U.H. Bokhary, I. Javaid, On the metric dimension of circulant graphs, Appl. Math. Let. 25 (2012), 320-325.
• [9] I. Javaid, M.T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21-33.
• [10] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, Technical Report (1994).
• [11] J. Peters-Fransen, O.R. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006), 33-41.
• [12] S.C. Shee, On group hypergraphs, Southeast Asian Bull. Math. 14 (1990), 49-57. [13] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975), 549-559.
• [14] P.J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22 (1988), 445-455.
• [15] T. Vetrik, The metric dimension of circulant graphs, Canad. Math. Bull. (2016), to appear.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).