The cost number and the determining number of a graph

2017/10/20 by ‎Saeid Alikhani, Alikhani, Saeid, Samaneh Soltani +1 · 1 citation
Computer Science · Mathematics · #05C15 #05C2 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1710.07527

openalex publication_date 2017/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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⊆ 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, Det(G), is the minimum cardinality of determining sets of G. In this paper we obtain some general upper and lower bounds for ρ_d(G) based on Det(G). Finally, we compute the cost and the determining number for the friendship graphs and corona product of two graphs.

Cited by

• On Distinguishing Graphs and Cost Number using Automorphism Representations

Related

• Distinguishing number and distinguishing index of certain graphs
• On Distinguishing Graphs and Cost Number using Automorphism Representations
• The Cost of Edge-distinguishing of the Cartesian Product of Connected Graphs
• Stabilizing on the distinguishing number of a graph
• Distinguishing number and distinguishing index of neighbourhood corona of two graphs