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 = 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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sciendo
2020-12-01
|
| Series: | Analele Stiintifice ale Universitatii Ovidius Constanta: Seria Matematica |
| Subjects: | |
| Online Access: | https://doi.org/10.2478/auom-2020-0032 |
| _version_ | 1811272283877015552 |
|---|---|
| author | Ahsan Muhammad Zahid Zohaib Zafar Sohail |
| author_facet | Ahsan Muhammad Zahid Zohaib Zafar Sohail |
| author_sort | Ahsan Muhammad |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T22:37:37Z |
| format | Article |
| id | doaj.art-abfe1fe7c416489fabc2c6b57b186332 |
| institution | Directory Open Access Journal |
| issn | 1844-0835 |
| language | English |
| last_indexed | 2024-04-12T22:37:37Z |
| publishDate | 2020-12-01 |
| publisher | Sciendo |
| record_format | Article |
| series | Analele Stiintifice ale Universitatii Ovidius Constanta: Seria Matematica |
| spelling | doaj.art-abfe1fe7c416489fabc2c6b57b1863322022-12-22T03:13:50ZengSciendoAnalele Stiintifice ale Universitatii Ovidius Constanta: Seria Matematica1844-08352020-12-01283153710.2478/auom-2020-0032Edge metric dimension of some classes of circulant graphsAhsan Muhammad0Zahid Zohaib1Zafar Sohail2Department of Mathematics, University of Management and Technology (UMT), LahorePakistanDepartment of Mathematics, University of Management and Technology (UMT), LahorePakistanDepartment of Mathematics, University of Management and Technology (UMT), LahorePakistanLet 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.https://doi.org/10.2478/auom-2020-0032edge metric dimensionedge metric generatorbasisresolving setcirculant graphsprimary 05c12secondary |
| spellingShingle | Ahsan Muhammad Zahid Zohaib Zafar Sohail Edge metric dimension of some classes of circulant graphs Analele Stiintifice ale Universitatii Ovidius Constanta: Seria Matematica edge metric dimension edge metric generator basis resolving set circulant graphs primary 05c12 secondary |
| title | Edge metric dimension of some classes of circulant graphs |
| title_full | Edge metric dimension of some classes of circulant graphs |
| title_fullStr | Edge metric dimension of some classes of circulant graphs |
| title_full_unstemmed | Edge metric dimension of some classes of circulant graphs |
| title_short | Edge metric dimension of some classes of circulant graphs |
| title_sort | edge metric dimension of some classes of circulant graphs |
| topic | edge metric dimension edge metric generator basis resolving set circulant graphs primary 05c12 secondary |
| url | https://doi.org/10.2478/auom-2020-0032 |
| work_keys_str_mv | AT ahsanmuhammad edgemetricdimensionofsomeclassesofcirculantgraphs AT zahidzohaib edgemetricdimensionofsomeclassesofcirculantgraphs AT zafarsohail edgemetricdimensionofsomeclassesofcirculantgraphs |