|
چکیده
|
A defining set (of vertex coloring) of a graph G = (V,E) is a set of vertices S with an assignment of colors to its elements which has a unique extension to a proper coloring of G. A defining set S is called a strong defining set if there exists an ordering set {v1, v2, · · · , v|V |−|S|} of the vertices of G−S such that in the induced list of colors in each of the subgraphs G−S,G−(S [{v1}),G−(S [{v1, v2}), · · · ,G−(S [{v1, v2, · · · , v|V |−|S|−1}) there exists at least one vertex whose list of colors is of cardinality 1. The strong defining number, denoted sd(G, k), of G is the cardinality of its smallest strong defining set, where k > (G). In the paper, [D.A. Mojdeh and A.P. Kazemi, Defining numbers in some of the Harary graphs, Appl. Math. Lett. 22 (2009), 922-926], the authors have studied the strong defining number in Harary graphs and posed the following problem: sd(H2m,3m+2, ) = 2m if m is even and sd(H2m,3m+2, ) = 2m + 1 when m is odd. In this note we prove this problem.
|