Resolving sets of directed Cayley graphs for the direct product of cyclic groups

Demelash Ashagrie Mengesha; Tomáš Vetrík

Czechoslovak Mathematical Journal (2019)

  • Volume: 69, Issue: 3, page 621-636
  • ISSN: 0011-4642

Abstract

top
A directed Cayley graph C ( Γ , X ) is specified by a group Γ and an identity-free generating set X for this group. Vertices of C ( Γ , X ) are elements of Γ and there is a directed edge from the vertex u to the vertex v in C ( Γ , X ) if and only if there is a generator x ∈ X such that u x = v . We study graphs C ( Γ , X ) for the direct product Z m × Z n of two cyclic groups Z m and Z n , and the generating set X = { ( 0 , 1 ) , ( 1 , 0 ) , ( 2 , 0 ) , ⋯ , ( p , 0 ) } . We present resolving sets which yield upper bounds on the metric dimension of these graphs for p = 2 and 3 .

How to cite

top

Mengesha, Demelash Ashagrie, and Vetrík, Tomáš. "Resolving sets of directed Cayley graphs for the direct product of cyclic groups." Czechoslovak Mathematical Journal 69.3 (2019): 621-636. <http://eudml.org/doc/294201>.

@article{Mengesha2019,
abstract = {A directed Cayley graph $C(\Gamma ,X)$ is specified by a group $\Gamma $ and an identity-free generating set $X$ for this group. Vertices of $C(\Gamma ,X)$ are elements of $\Gamma $ and there is a directed edge from the vertex $u$ to the vertex $v$ in $C(\Gamma ,X)$ if and only if there is a generator $x \in X$ such that $ux = v$. We study graphs $C(\Gamma ,X)$ for the direct product $Z_m \times Z_n$ of two cyclic groups $Z_m$ and $Z_n$, and the generating set $X = \lbrace (0,1), (1, 0), (2,0), \dots , (p,0) \rbrace $. We present resolving sets which yield upper bounds on the metric dimension of these graphs for $p = 2$ and $3$.},
author = {Mengesha, Demelash Ashagrie, Vetrík, Tomáš},
journal = {Czechoslovak Mathematical Journal},
keywords = {metric dimension; resolving set; Cayley graph; direct product; cyclic group},
language = {eng},
number = {3},
pages = {621-636},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Resolving sets of directed Cayley graphs for the direct product of cyclic groups},
url = {http://eudml.org/doc/294201},
volume = {69},
year = {2019},
}

TY - JOUR
AU - Mengesha, Demelash Ashagrie
AU - Vetrík, Tomáš
TI - Resolving sets of directed Cayley graphs for the direct product of cyclic groups
JO - Czechoslovak Mathematical Journal
PY - 2019
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 69
IS - 3
SP - 621
EP - 636
AB - A directed Cayley graph $C(\Gamma ,X)$ is specified by a group $\Gamma $ and an identity-free generating set $X$ for this group. Vertices of $C(\Gamma ,X)$ are elements of $\Gamma $ and there is a directed edge from the vertex $u$ to the vertex $v$ in $C(\Gamma ,X)$ if and only if there is a generator $x \in X$ such that $ux = v$. We study graphs $C(\Gamma ,X)$ for the direct product $Z_m \times Z_n$ of two cyclic groups $Z_m$ and $Z_n$, and the generating set $X = \lbrace (0,1), (1, 0), (2,0), \dots , (p,0) \rbrace $. We present resolving sets which yield upper bounds on the metric dimension of these graphs for $p = 2$ and $3$.
LA - eng
KW - metric dimension; resolving set; Cayley graph; direct product; cyclic group
UR - http://eudml.org/doc/294201
ER -

References

top
  1. Ahmad, A., Imran, M., Al-Mushayt, O., Bokhary, S. A. U. H., 10.18514/MMN.2015.1192, Miskolc Math. Notes 16 (2016), 637-646. (2016) Zbl1349.05082MR3454129DOI10.18514/MMN.2015.1192
  2. Chartrand, G., Eroh, L., Johnson, M. A., Oellermann, O. R., 10.1016/S0166-218X(00)00198-0, Discrete Appl. Math. 105 (2000), 99-113. (2000) Zbl0958.05042MR1780464DOI10.1016/S0166-218X(00)00198-0
  3. Fehr, M., Gosselin, S., Oellermann, O. R., 10.1016/j.disc.2005.09.015, Discrete Math. 306 (2006), 31-41. (2006) Zbl1085.05034MR2202072DOI10.1016/j.disc.2005.09.015
  4. Harary, F., Melter, R. A., On the metric dimension of a graph, Ars Comb. 2 (1976), 191-195. (1976) Zbl0349.05118MR0457289
  5. Imran, M., 10.1007/s10255-016-0627-0, Acta Math. Appl. Sin. Engl. Ser. 32 (2016), 1067-1072. (2016) Zbl06700451MR3552871DOI10.1007/s10255-016-0627-0
  6. Imran, M., Baig, A. Q., Bokhary, S. A. U. H., Javaid, I., 10.1016/j.aml.2011.09.008, Appl. Math. Lett. 25 (2012), 320-325. (2012) Zbl1243.05072MR2855980DOI10.1016/j.aml.2011.09.008
  7. Javaid, I., Rahim, M. T., Ali, K., Families of regular graphs with constant metric dimension, Util. Math. 75 (2008), 21-33. (2008) Zbl1178.05037MR2389696
  8. Khuller, S., Raghavachari, B., Rosenfeld, A., 10.1016/0166-218X(95)00106-2, Discrete Appl. Math. 70 (1996), 217-229. (1996) Zbl0865.68090MR1410574DOI10.1016/0166-218X(95)00106-2
  9. Melter, R. A., Tomescu, I., 10.1016/0734-189X(84)90051-3, Comput. Vision Graphics Image Process 25 (1984), 113-121. (1984) Zbl0591.51023MR0752034DOI10.1016/0734-189X(84)90051-3
  10. Oellermann, O. R., Pawluck, C. D., Stokke, A., The metric dimension of Cayley digraphs of Abelian groups, Ars Comb. 81 (2006), 97-111. (2006) Zbl1189.05055MR2267805
  11. Slater, P. J., Leaves of trees, Proc. 6th Southeast. Conf. Combinatorics, Graph Theory and Computing Congressus Numerantium 14, Utilitas Mathematica, Winnipeg (1975), 549-559. (1975) Zbl0316.05102MR0422062

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.