2024 : 4 : 27
Doost Ali Mojdeh

Doost Ali Mojdeh

Academic rank: Professor
ORCID:
Education: PhD.
ScopusId:
Faculty: Faculty of Mathematical Sciences
Address: Department of Mathematics, University of Mazandaran, Babolsar, Iran
Phone: 011-35302448

Research

Title
A Note on the Strong Defining Numbers in Graphs
Type
JournalPaper
Keywords
Defining set, strong defining set, Harary graphs
Year
2016
Journal International Journal of Mathematical Combinatorics
DOI
Researchers Doost Ali Mojdeh ، Zahra Tahmasbizadehbaee ، Hossein ABDOLLAHZADEH AHANGAR

Abstract

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.