On the star partition dimension of comb product of cycle and complete graph

International Conference on Mathematics: Education, Theory and Application

数学;教育

Alfarisi, Ridho^1 ; Darmaji^1 ; Dafik^2

Department of Mathematics, Sepuluh Nopember Institute of Technology, Surabaya, Indonesia^1

CGANT-University of Jember, Indonesia^2

关键词: comb product;    Complete graphs;    cycle;    Partition dimensions;    Resolving partitions;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/855/1/012005/pdf
DOI  :  10.1088/1742-6596/855/1/012005

学科分类：发展心理学和教育心理学

来源: IOP

【 摘 要 】

Let G = (V, E) be a connected graphs with vertex set V (G), edge set E(G) and S ⊆ V (G). For an ordered partition Π = {S1, S2, S3, , Sk} of V (G), the representation of a vertex v ∈ V (G) with respect to Π is the k-vectors r(v|Π) = (d(v, S1), d(v, S2), , d(v, Sk)), where d(v, Sk) represents the distance between the vertex v and the set Sk, defined by d(v, Sk) = min{d(v, x)|x ∈ Sk}. The partition Π of V (G) is a resolving partition if the k-vektors r(v|Π), v ∈ V (G) are distinct. The minimum resolving partition Π is a partition dimension of G, denoted by pd(G). The resolving partition Π = {S1, S2, S3, , Sk} is called a star resolving partition for G if it is a resolving partition and each subgraph induced by Si, 1 ≤ i ≤ k, is a star. The minimum k for which there exists a star resolving partition of V (G) is the star partition dimension of G, denoted by spd(G). Finding a star partition dimension of G is classified to be a NP-Hard problem. Furthermore, the comb product between G and H, denoted by G H, is a graph obtained by taking one copy of G and |V (G)| copies of H and grafting the i-th copy of H at the vertex o to the i-th vertex of G. By definition of comb product, we can say that V (GH) = {(a, u)|a ∈ V (G), u ∈ V (H)} and (a, u)(b, v) ∈ E(GH) whenever a = b and uv ∈ E(H), or ab ∈ E(G) and u = v = o. In this paper, we will study the star partition dimension of comb product of cycle and complete graph, namely CnKmand KmCnfor n ≥ 3 and m ≥ 3.