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

[摘要] 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.

[发布机构] 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