Araştırma Makalesi
BibTex RIS Kaynak Göster

On the metric dimension of rotationally-symmetric convex polytopes

Yıl 2016, , 45 - 59, 15.05.2016
https://doi.org/10.13069/jacodesmath.47485

Öz

Metric dimension is
a generalization of affine dimension to arbitrary metric spaces
(provided a resolving set exists). Let $\mathcal{F}$ be a family of connected graphs $G_{n}$ :
$\mathcal{F} = (G_{n})_{n}\geq 1$ depending on $n$ as follows: the
order $|V(G)| = \varphi(n)$ and $\lim\limits_{n\rightarrow
\infty}\varphi(n)=\infty$. If there exists a constant $C > 0$ such
that $dim(G_{n}) \leq C$ for every $n \geq 1$ then we shall say
that $\mathcal{F}$ has bounded metric dimension, otherwise
$\mathcal{F}$ has unbounded metric dimension. If all graphs in
$\mathcal{F}$ have the same metric dimension, then $\mathcal{F}$ is
called a family of graphs with constant metric dimension.

In this paper, we study the metric dimension of some classes of convex
polytopes which are rotationally-symmetric. It is shown that
these classes of convex polytoes have the constant metric dimension
and only three vertices chosen appropriately suffice to resolve
all the vertices of these classes of convex polytopes. It is natural
to ask for the characterization of classes of convex polytopes with
constant metric dimension.

Kaynakça

  • [1] M. Baca, Labelings of two classes of convex polytopes, Utilitas Math. 34 (1988) 24–31.
  • [2] M. Baca, On magic labellings of convex polytopes, Ann. Disc. Math. 51 (1992) 13–16.
  • [3] P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar. 46(1) (2003) 9–15.
  • [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(2) (2007) 423–441.
  • [5] G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and metric dimension of a graph, Discrete Appl. Math. 105(1-3) (2000) 99–113.
  • [6] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, New York: wh freeman, 1979.
  • [7] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria. 2 (1976) 191–195.
  • [8] C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Caceres, M. L. Puertas, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005) 129–133.
  • [9] M. Imran, A. Q. Baig, A. Ahmad, Families of plane graphs with constant metric dimension, Util. Math. 88 (2012) 43–57.
  • [10] M. Imran, A. Q. Baig, M. K. Shafiq, A. Semanicová–Fenovcíková, Classes of convex polytopes with constant metric dimension, Util. Math. 90 (2013) 85–99.
  • [11] I. Javaid, M. T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008) 21–33.
  • [12] M. A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat. 3(2) (1993) 203–236.
  • [13] E. Jucovic, Convex polyhedra, Bratislava:Veda, 1981.
  • [14] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996) 217–229.
  • [15] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, 1998.
  • [16] R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vision Graphics Image Process. 25(1) (1984) 113–121.
  • [17] J. Peters-Fransen, R. O. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006) 33–41.
  • [18] P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
  • [19] P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22(4) (1988) 445–455.
  • [20] I. Tomescu, M. Imran, On metric and partition dimensions of some infinite regular graphs, Bull. Math. Soc. Sci. Math. Roumanie. 52(100)(4) (2009) 461–472.
  • [21] I. Tomescu, I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie. 50(98)(4) (2007) 371–376.
Yıl 2016, , 45 - 59, 15.05.2016
https://doi.org/10.13069/jacodesmath.47485

Öz

Kaynakça

  • [1] M. Baca, Labelings of two classes of convex polytopes, Utilitas Math. 34 (1988) 24–31.
  • [2] M. Baca, On magic labellings of convex polytopes, Ann. Disc. Math. 51 (1992) 13–16.
  • [3] P. S. Buczkowski, G. Chartrand, C. Poisson, P. Zhang, On k-dimensional graphs and their bases, Period. Math. Hungar. 46(1) (2003) 9–15.
  • [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(2) (2007) 423–441.
  • [5] G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oellermann, Resolvability in graphs and metric dimension of a graph, Discrete Appl. Math. 105(1-3) (2000) 99–113.
  • [6] M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPCompleteness, New York: wh freeman, 1979.
  • [7] F. Harary, R. A. Melter, On the metric dimension of a graph, Ars Combinatoria. 2 (1976) 191–195.
  • [8] C. Hernando, M. Mora, I. M. Pelayo, C. Seara, J. Caceres, M. L. Puertas, On the metric dimension of some families of graphs, Electron. Notes Discrete Math. 22 (2005) 129–133.
  • [9] M. Imran, A. Q. Baig, A. Ahmad, Families of plane graphs with constant metric dimension, Util. Math. 88 (2012) 43–57.
  • [10] M. Imran, A. Q. Baig, M. K. Shafiq, A. Semanicová–Fenovcíková, Classes of convex polytopes with constant metric dimension, Util. Math. 90 (2013) 85–99.
  • [11] I. Javaid, M. T. Rahim, K. Ali, Families of regular graphs with constant metric dimension, Util. Math. 75 (2008) 21–33.
  • [12] M. A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat. 3(2) (1993) 203–236.
  • [13] E. Jucovic, Convex polyhedra, Bratislava:Veda, 1981.
  • [14] S. Khuller, B. Raghavachari, A. Rosenfeld, Landmarks in graphs, Discrete Appl. Math. 70(3) (1996) 217–229.
  • [15] S. Khuller, B. Raghavachari, A. Rosenfeld, Localization in graphs, 1998.
  • [16] R. A. Melter, I. Tomescu, Metric bases in digital geometry, Comput. Vision Graphics Image Process. 25(1) (1984) 113–121.
  • [17] J. Peters-Fransen, R. O. Oellermann, The metric dimension of Cartesian products of graphs, Util. Math. 69 (2006) 33–41.
  • [18] P. J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549–559.
  • [19] P. J. Slater, Dominating and reference sets in a graph, J. Math. Phys. Sci. 22(4) (1988) 445–455.
  • [20] I. Tomescu, M. Imran, On metric and partition dimensions of some infinite regular graphs, Bull. Math. Soc. Sci. Math. Roumanie. 52(100)(4) (2009) 461–472.
  • [21] I. Tomescu, I. Javaid, On the metric dimension of the Jahangir graph, Bull. Math. Soc. Sci. Math. Roumanie. 50(98)(4) (2007) 371–376.
Toplam 21 adet kaynakça vardır.

Ayrıntılar

Konular Mühendislik
Bölüm Makaleler
Yazarlar

Muhammad Imran

Syed Ahtsham Ul Haq Bokhary

A. Q. Baig

Yayımlanma Tarihi 15 Mayıs 2016
Yayımlandığı Sayı Yıl 2016

Kaynak Göster

APA Imran, M., Bokhary, S. A. U. H., & Baig, A. Q. (2016). On the metric dimension of rotationally-symmetric convex polytopes. Journal of Algebra Combinatorics Discrete Structures and Applications, 3(2), 45-59. https://doi.org/10.13069/jacodesmath.47485
AMA Imran M, Bokhary SAUH, Baig AQ. On the metric dimension of rotationally-symmetric convex polytopes. Journal of Algebra Combinatorics Discrete Structures and Applications. Mayıs 2016;3(2):45-59. doi:10.13069/jacodesmath.47485
Chicago Imran, Muhammad, Syed Ahtsham Ul Haq Bokhary, ve A. Q. Baig. “On the Metric Dimension of Rotationally-Symmetric Convex Polytopes”. Journal of Algebra Combinatorics Discrete Structures and Applications 3, sy. 2 (Mayıs 2016): 45-59. https://doi.org/10.13069/jacodesmath.47485.
EndNote Imran M, Bokhary SAUH, Baig AQ (01 Mayıs 2016) On the metric dimension of rotationally-symmetric convex polytopes. Journal of Algebra Combinatorics Discrete Structures and Applications 3 2 45–59.
IEEE M. Imran, S. A. U. H. Bokhary, ve A. Q. Baig, “On the metric dimension of rotationally-symmetric convex polytopes”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 3, sy. 2, ss. 45–59, 2016, doi: 10.13069/jacodesmath.47485.
ISNAD Imran, Muhammad vd. “On the Metric Dimension of Rotationally-Symmetric Convex Polytopes”. Journal of Algebra Combinatorics Discrete Structures and Applications 3/2 (Mayıs 2016), 45-59. https://doi.org/10.13069/jacodesmath.47485.
JAMA Imran M, Bokhary SAUH, Baig AQ. On the metric dimension of rotationally-symmetric convex polytopes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2016;3:45–59.
MLA Imran, Muhammad vd. “On the Metric Dimension of Rotationally-Symmetric Convex Polytopes”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 3, sy. 2, 2016, ss. 45-59, doi:10.13069/jacodesmath.47485.
Vancouver Imran M, Bokhary SAUH, Baig AQ. On the metric dimension of rotationally-symmetric convex polytopes. Journal of Algebra Combinatorics Discrete Structures and Applications. 2016;3(2):45-59.