THE PARTITION DIMENSION AND $k$-DOMINATION NUMBER OF TWO SPECIFIC GRAPHS

Document Type : Original Manuscript

Authors

1 Department of Mathematics, Faculty of Science, Payame Noor University, P.O. Box 19395-4697, Tehran, Iran.

2 Department of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran.

10.22044/jas.2024.14317.1816

Abstract

For an ordered $k$-partition $\Omega = \{S_1, S_2, ..., S_k\}$ of vertex set of a connected graph $G$ and a vertex $v$ of $G$, the representation of $v$ with respect to $\Omega$ is defined as the $k$-tuple $r(v |\Omega) = (d(v, S_1), d(v, S_2), ..., d(v, S_k )).$ The partition $\Omega$ is called a resolving partition of $G$, if $r(u|\Omega)\neq r(v|\Omega)$
for all distinct $u, v \in V(G)$. The partition dimension of a graph $G$, denoted by $pd(G)$, is the cardinality of a minimum resolving partition of $G$.
A subset $D\subseteq V(G)$ is $k$-dominating in $G$, if every vertex of $V(G)\setminus D$ has at least $k$ neighbors in $D$. The minimum cardinality among all $k$-dominating sets is called the $k$-domination number of $G$, denoted by $\gamma_k(G)$. In this paper, we determine the partition dimension of cocktail party graph $CP(m+1)$ and corona product $G\circ\overline{K_m}$. Moreover, we obtain $k$-domination numbers for $CP(m+1)$ and corona product $C_n\circ\overline{K_m}$.

Keywords

References

 1. D. Amrullah and E. T. Baskoro, The partition dimension for a homogeneous firecrackers, Far East J. Appl. Math., 90(1) (2015), 77–98. 
 
 2. Z. Beerliova, F. Eberhard, T. Erlebach et al., Network discovery and verification, IEEE Journal on Selected Areas in Communications, 24(12) (2006), 2168–2181.
 
3. M. Borowiecki and M. Kuzak, On the k-stable and k-dominating sets of graphs, in: Graphs, Hypergraphs and Block Systems, Proc. Symp. Zielona Gora, 1976, ed. by M. Borowiecki, Z. Skupieri, L. Szamkolowicz, Zielona Gora, 1976.
 
4. J. Cáceres, C. Hernando, M. Mora et al., On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math., 21(2) (2007), 423–441.
 
5. G. Chartrand, E. Salehi and P. Zhang, The partition dimension of a graph, Aequ. Math., 59(1-2) (2000), 45–54.
 
6. V. Chvátal, Mastermind, Combinatorica, 3(3-4) (1983), 325–329.
 
7. E. J. Cockayne and S. T. Hedetniemi, Towards a theory of domination in graphs, Networks, 7 (1977), 247–261.
 
8. O. Favaron, k-Domination and k-independence in graphs, Ars Combin., 25C (1988), 159–167.
 
9. M. Fehr, S. Gosselin and O. R. Oellermann, The partition dimension of Cayley digraphs, Aequationes Math., 71(1-2) (2006), 1–18.
 
10. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, NY, USA, 1979.
 
11. C. Godsil and G. Royle, Algebraic graph theory, Springer, New York, 2001.
 
12. F. Harary and R. A. Melter, On the metric dimension of a graph, Ars Combin., 2 (1976), 191–195.
 
13. T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
 
14. I. Javaid and S. Shokat, On the partition dimension of some wheel related graphs, J. Prime Res. Math., 4 (2008), 154–164.
 
15. M. A. Johnson, Browsable structure-activity datasets, in: Advances in Molecular Similarity, pp. 153–170, JAI Press Connecticut, Stamford, CT, USA, 1998.
 
16. M. A. Johnson, Structure-activity maps for visualizing the graph variables arising in drug design, J. Biopharm. Stat., 3 (1993), 203–236.
 
17. J.-B. Liu, A. Zafari and H. Zarei, Metric dimension, minimal doubly resolving sets and strong metric dimension for Jellyfish graph and Cocktail party graph, Complexity, (2020), Article ID: 9407456, 1–7.
 
18. N. Mehreen, R. Farooq and S. Akhter, On partition dimension of fullerene graphs, AIMS Math., 3(3) (2018), 343–352.
 
19. R. A. Melter and I. Tomescu, Metric bases in digital geometry, Computer Vision, Graphics, and Image Processing, 25(1) (1984), 113–121.
 
20. S. M. Mirafzal and A. Zafari, On the spectrum of a class of distance-transitive graphs, Electron. J. Graph Theory Appl., 5(1) (2017), 63–69.
 
21. O. Ore, Theory of Graphs, Amer. Math. Soc. Colloq. Publ., 38, Amer. Math. Soc., Providence, RI, 1962.
 
22. B. Rajan, A. William, I. Rajasingh, C. Grigorious and S. Stephen, On certain networks with partition dimension three, in: Proceedings of International Conference on Mathematics Engineering and Business Management, Chengdu, China, March, 2012.
 
23. J. A. Rodríguez-Velázquez, I. G. Yero and H. Fernau, On the partition dimension of unicyclic graphs, Bull. Math. Soc. Sci. Math., 57 (2014), 381–391.
 
 24. J. A. Rodríguez-Velázquez, I. G. Yero and D. Kuziak, The partition dimension of corona product graphs, Ars Combin., 127 (2016), 387–399.
 
25. J. A. Rodríguez-Velázquez, I. G. Yero and M. Lemańska, On the partition dimension of trees, Discrete Appl. Math., 166 (2014), 204–209.
 
26. H. M. A. Siddiqui and M. Imran, Computation of metric dimension and partition dimension of Nanotubes, J. Comput. Theor. Nanosci., 12(2) (2015), 199–203.
 
27. P. J. Slater, Leaves of trees, Congr. Numer., 14 (1975), 549–559.
 
28. C. Wei, M. F. Nadeem, H. M. A. Siddiqui, M. Azeem, J. B Liu and A. Khalil, On Partition Dimension of Some Cycle-Related Graphs, Math. Probl. Eng., 2021 (2021), 1–8.
 
 
 
 
Journal of Algebraic Systems
Volume 14, Issue 2
April 2026
Pages 331-342

Files

Share

How to cite

Statistics