The cost number and the determining number of a graph

DOI10.22044/JAS.2020.8343.1408MaRDI QIDQ4956581zbMATH OpenOpenAlexFDO

Authors Saeid Alikhani, Samaneh Soltani

Publication date 2 September 2021

Full work available at URL https://arxiv.org/abs/1710.07527

zbMATH Keywords

determining setdistinguishing labelingdistinguishing number

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

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 $h{o}_d(G)$. A set of vertices $SsubseteqV(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 $h{o}_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.

Recommendations

• Distinguishing number and distinguishing index of certain graphs
• The cost of 2-distinguishing Cartesian powers
• The cost of distinguishing graphs
• Paint cost and the frugal distinguishing number
• Infinite graphs with finite 2-distinguishing cost

Cites work

• Bounding the distinguishing number of infinite graphs and permutation groups
• Distinguishing Cartesian products of countable graphs
• Distinguishing graphs with intermediate growth
• Distinguishing number and distinguishing index of natural and fractional powers of graphs
• Handbook of product graphs
• Identifying graph automorphisms using determining sets
• Small label classes in 2-distinguishing labelings
• Symmetry breaking in graphs
• The distinguishing number of the augmented cube and hypercube powers
• THE DISTINGUISHING NUMBERS OF MERGED JOHNSON GRAPHS
• The list distinguishing number equals the distinguishing number for interval graphs
• Using determining sets to distinguish Kneser graphs

Cited in

(3)

• Paint cost and the frugal distinguishing number
• The cost of distinguishing graphs
• Paint cost spectrum of perfect k-ary trees

This page was built for publication: The cost number and the determining number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4956581)