June 10, 2023
Doost Ali Mojdeh

Doost Ali Mojdeh

Degree: Professor
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Education: Ph.D in Mathematics (Graph Theory and Combinatorics)
Phone: 011-35302448
Faculty: Faculty of Mathematical Sciences


Title A Note on the Strong Defining Numbers in Graphs
Type Article
Defining set, strong defining set, Harary graphs
Journal International Journal of Mathematical Combinatorics
DOI لینک مقاله همین است
Researchers Zahra Tahmasbizadehbaee (First researcher) , Hossein ABDOLLAHZADEH AHANGAR (Second researcher) , Doost Ali Mojdeh (Third researcher)


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.