<abstract xmlns="http://www.w3.org/1999/xhtml">Let <italic>G</italic> = (<italic>V</italic> (<italic>G</italic>), <italic>E</italic>(<italic>G</italic>)) be a connected graph and <italic>x, y</italic> ∈ <italic>V</italic> (<italic>G</italic>), <italic>d</italic>(<italic>x, y</italic>) = min{ length of <italic>x − y</italic> path } and for <italic>e</italic> ∈ <italic>E</italic>(<italic>G</italic>), <italic>d</italic>(<italic>x, e</italic>) = min{<italic>d</italic>(<italic>x, a</italic>), <italic>d</italic>(<italic>x, b</italic>)}, where <italic>e</italic> = <italic>ab</italic>. A vertex <italic>x</italic> distinguishes two edges <italic>e</italic>1 and <italic>e</italic>2, if <italic>d</italic>(<italic>e</italic>1, <italic>x</italic>) ≠ <italic>d</italic>(<italic>e</italic>2, <italic>x</italic>). Let <italic>WE</italic> = {<italic>w</italic>1, <italic>w</italic>2, . . ., <italic>wk</italic>} be an ordered set in <italic>V</italic> (<italic>G</italic>) and let <italic>e</italic> ∈ <italic>E</italic>(<italic>G</italic>). The representation <italic>r</italic>(<italic>e | WE</italic>) of <italic>e</italic> with respect to <italic>WE</italic> is the <italic>k</italic>-tuple (<italic>d</italic>(<italic>e, w</italic>1), <italic>d</italic>(<italic>e, w</italic>2), . . ., <italic>d</italic>(<italic>e, wk</italic>)). If distinct edges of <italic>G</italic> have distinct representation with respect to <italic>WE</italic>, then <italic>WE</italic> is called an edge metric generator for <italic>G</italic>. An edge metric generator of minimum cardinality is an edge metric basis for <italic>G</italic>, and its cardinality is called edge metric dimension of <italic>G</italic>, denoted by edim(<italic>G</italic>). The circulant graph <italic>Cn</italic>(1, <italic>m</italic>) has vertex set {<italic>v</italic>1, <italic>v</italic>2, . . ., <italic>vn</italic>} and edge set {<italic>vivi</italic>+1 : 1 ≤ <italic>i</italic> ≤ <italic>n−</italic>1}∪{<italic>vnv</italic>1}∪{<italic>vivi+m </italic>: 1 ≤ <italic>i</italic> ≤ <italic>n−m</italic>}∪{<italic>vn−m+ivi</italic> : 1 ≤ <italic>i</italic> ≤ <italic>m</italic>}. In this paper, it is shown that the edge metric dimension of circulant graphs <italic>Cn</italic>(1, 2) and <italic>Cn</italic>(1, 3) is constant.</abstract>

Let G = (V (G), E(G)) be a connected graph and x, y ∈ V (G), d(x, y) = min{ length of x − y path } and for e ∈ E(G), d(x, e) = min{d(x, a), d(x, b)}, where e = ab. A vertex x distinguishes two edges e1 and e2, if d(e1, x) ≠ d(e2, x). Let WE = {w1, w2, . . ., wk} be an ordered set in V (G) and let e ∈ E(G). The representation r(e | WE) of e with respect to WE is the k-tuple (d(e, w1), d(e, w2), . . ., d(e, wk)). If distinct edges of G have distinct representation with respect to WE, then WE is called an edge metric generator for G. An edge metric generator of minimum cardinality is an edge metric basis for G, and its cardinality is called edge metric dimension of G, denoted by edim(G). The circulant graph Cn(1, m) has vertex set {v1, v2, . . ., vn} and edge set {vivi+1 : 1 ≤ i ≤ n−1}∪{vnv1}∪{vivi+m : 1 ≤ i ≤ n−m}∪{vn−m+ivi : 1 ≤ i ≤ m}. In this paper, it is shown that the edge metric dimension of circulant graphs Cn(1, 2) and Cn(1, 3) is constant.

Edge metric dimension of some classes of circulant graphs

University of Management and Technology (UMT)

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

{"article-title":"Edge metric dimension of some classes of circulant graphs"}

Let G = (V (G), E(G)) be a connected graph and x, y ∈ V (G), d(x, y) = min{ length of x − y path } and for e ∈ E(G), d(x, e) = min{d(x, a), d(x, b)}, where e =...

Edge metric dimension of some classes of circulant graphs

Publié en ligne: 28 déc. 2020

Pages: 15 - 37

Reçu: 09 oct. 2019

Accepté: 20 févr. 2020

DOI: https://doi.org/10.2478/auom-2020-0032

Mots clés
Edge metric dimension, edge metric generator, basis, resolving set, circulant graphs

© 2020 Muhammad Ahsan et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Edge metric dimension of some classes of circulant graphs

Publié en ligne: 28 déc. 2020

Pages: 15 - 37

Reçu: 09 oct. 2019

Accepté: 20 févr. 2020

DOI: https://doi.org/10.2478/auom-2020-0032

Mots clésEdge metric dimension, edge metric generator, basis, resolving set, circulant graphs

© 2020 Muhammad Ahsan et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Mots clés
Edge metric dimension, edge metric generator, basis, resolving set, circulant graphs