Journals Information
Mathematics and Statistics Vol. 11(3), pp. 574 - 578
DOI: 10.13189/ms.2023.110314
Reprint (PDF) (660Kb)
Upper Bound for Partition Dimension of Comb Product of a Wheel Graph and Tree
Faisal *, Andreas Martin
Mathematics Department, School of Computer Science, Bina Nusantara University, Jakarta, 11480, Indonesia
ABSTRACT
The concept of partition dimension in graph theory was first introduced by Chartrand et al. [1] as a variation of metric dimension. Since then, numerous studies have attempted to determine the partition dimensions of various types of graphs. However, for many types of graphs, their partition dimensions remain unknown as determining a general graph's partition dimension is an NP-complete problem. In this study, we aim to determine the partition dimension of a specific graph, namely the comb product of a wheel and a tree. One approach to finding the partition dimension of a graph is to determine its upper and lower bounds. In this article, we propose an upper bound for the partition dimension of the comb product using number representation for certain bases. We divide the problem into two cases based on the path graph. For the first case, which is the comb product with a path of a single vertex, Tomescu et al. [2] have already provided an upper bound. In the other case, we utilize the bijection property of a number system on the number copy of the tree to find an upper bound. Our results show that the partition dimension of the second case has a smaller upper bound compared to the general upper bound proposed by Chartrand et al. [1].
KEYWORDS
Partition Dimension, Graph Theory, Comb Product, Wheel, Tree, Upper bound, NP-complete Problem
Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Faisal , Andreas Martin , "Upper Bound for Partition Dimension of Comb Product of a Wheel Graph and Tree," Mathematics and Statistics, Vol. 11, No. 3, pp. 574 - 578, 2023. DOI: 10.13189/ms.2023.110314.
(b). APA Format:
Faisal , Andreas Martin (2023). Upper Bound for Partition Dimension of Comb Product of a Wheel Graph and Tree. Mathematics and Statistics, 11(3), 574 - 578. DOI: 10.13189/ms.2023.110314.