The convex and weak convex domination number of convex polytopes

Authors

  • Zoran Lj. Maksimović Military Academy, University of Defence, Belgrade, Serbia
  • Aleksandar Lj. Savić Faculty of Mathematics, University of Belgrade, Belgrade, Serbia
  • Milena S. Bogdanović Department of Information Technology, Metropolitan University, Belgrade, Serbia

DOI:

https://doi.org/10.33044/revuma.1739

Abstract

This paper is devoted to solving the weakly convex dominating set problem and the convex dominating set problem for some classes of planar graphs-convex polytopes. We consider all classes of convex polytopes known from the literature and present exact values of weakly convex and convex domination number for all classes, namely $A_n$, $B_n$, $C_n$, $D_n$, $E_n$, $R_n$, $R''_n$, $Q_n$, $S_n$, $S''_n$, $T_n$, $T''_n$ and $U_n$. When $n$ is up to 26, the values are confirmed by using the exact method, while for greater values of $n$ theoretical proofs are given.

Downloads

Download data is not yet available.

References

M. Bača, Labelings of two classes of convex polytopes, Utilitas Math. 34 (1988), 24–31. MR 0982242.

M. Bača, On magic labellings of convex polytopes, in Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity (Prachatice, 1990), 13–16, Ann. Discrete Math., 51, North-Holland, Amsterdam, 1992. MR 1206237.

J. Cyman, M. Lemańska and J. Raczek, Graphs with convex domination number close to their order, Discuss. Math. Graph Theory 26 (2006), no. 2, 307–316. MR 2330331.

M. Dettlaff and M. Lemańska, Influence of edge subdivision on the convex domination number, Australas. J. Combin. 53 (2012), 19–30. MR 2962128.

M. Imran, A. Q. Baig and A. Ahmad, Families of plane graphs with constant metric dimension, Util. Math. 88 (2012), 43–57. MR 2975822.

M. Imran, A. Q. Baig, M. K. Shafiq and A. Semaničová-Feňovčíková, Classes of convex polytopes with constant metric dimension, Util. Math. 90 (2013), 85–99. MR 3059386.

M. Imran, S. A. U. H. Bokhary, A. Ahmad and A. Semaničová-Feňovčíková, On classes of regular graphs with constant metric dimension, Acta Math. Sci. Ser. B (Engl. Ed.) 33 (2013), no. 1, 187–206. MR 3003753.

M. Imran, S. A. U. H. Bokhary and A. Q. Baig, On families of convex polytopes with constant metric dimension, Comput. Math. Appl. 60 (2010), no. 9, 2629–2638. MR 2728092.

M. Imran, S. A. U. H. Bokhary and A. Q. Baig, On the metric dimension of rotationally-symmetric convex polytopes, J. Algebra Comb. Discrete Struct. Appl. 3 (2016), no. 2, 45–59. MR 3493642.

T. N. Janakiraman and P. J. A. Alphonse, Weak convex domination in graphs. Int. J. Eng. Sci. Adv. Comput. Biotech. 1 (2010), no. 1, 1–13.

J. Kratica, V. Kovačević-Vujčić, M. Čangalović and M. Stojanović, Minimal doubly resolving sets and the strong metric dimension of some convex polytopes, Appl. Math. Comput. 218 (2012), no. 19, 9790–9801. MR 2916158.

J. Kratica, V. Filipović, D. Matić and A. Kartelj, An integer linear programming formulation for the convex dominating set problems, https://arxiv.org/abs/1904.02541 [math.OC], 2019.

M. A. Labendia and S. R. Canoy, Jr., Convex domination in the composition and Cartesian product of graphs, Czechoslovak Math. J. 62(137) (2012), no. 4, 1003–1009. MR 3010253.

M. Lemańska, Weakly convex and convex domination numbers, Opuscula Math. 24 (2004), no. 2, 181–188. MR 2100881.

M. Lemańska and R. Zuazua, Convex universal fixers, Discuss. Math. Graph Theory 32 (2012), no. 4, 807–812. MR 2993524.

M. Miller, M. Bača and J. A. MacDougall, Vertex-magic total labeling of generalized Petersen graphs and convex polytopes, J. Combin. Math. Combin. Comput. 59 (2006), 89–99. MR 2277342.

N. Polat, On isometric subgraphs of infinite bridged graphs and geodesic convexity, Discrete Math. 244 (2002), no. 1-3, 399–416. MR 1844048.

J. Raczek, NP-completeness of weakly convex and convex dominating set decision problems, Opuscula Math. 24 (2004), no. 2, 189–196. MR 2100882.

Downloads

Published

2022-03-22

Issue

Vol. 63 No. 1 (2022)

Section

Article

License

Copyright (c) 2022 Zoran Lj. Maksimović, Aleksandar Lj. Savić, Milena S. Bogdanović

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.