THE COST NUMBER AND THE DETERMINING NUMBER OF A GRAPH

Document Type : Original Manuscript

Authors

¹ Department of Mathematics, Yazd University, 89195-741, Yazd, Iran.

² Department of Mathematics, Yazd University, 89195-741, Yazd, Iran

Abstract

The distinguishing number

D (G)

of a graph

G

is the least integer

d

such that

G

has an vertex labeling with

d

labels that is preserved only by a trivial automorphism. The minimum size of a label class in such a labeling of

G

with

D (G) = d

is called the cost of

d

-distinguishing

G

and is denoted by

ρ_{d} (G)

. A set of vertices

S \subseteq V (G)

is a determining set for

G

if every automorphism of

G

is uniquely determined by its action on

S

. The determining number of

G

D e t (G)

, is the minimum cardinality of determining sets of

G

. In this paper we compute the cost and the determining number for the friendship graphs and corona product of two graphs.

Keywords

20.1001.1.23455128.2021.8.2.6.1