Distinguishing threshold for some graph operations

DOI10.1007/S40995-022-01379-2MaRDI QIDQ6376504zbMATH OpenFDO

Authors Mohammad Hadi Shekarriz, Seyed Alireza Talebpour Shirazi Fard, B. Ahmadi, Mohammad Hassan Shirdareh Haghighi, Saeid Alikhani

Publication date 31 August 2021

Full work available at URL https://doi.org/10.1007/S40995-022-01379-2

Mathematics Subject Classification ID

Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A vertex coloring of a graph $G$ is distinguishing if non-identity automorphisms do not preserve it. The distinguishing number, $D(G)$, is the minimum number of colors required for such a coloring and the distinguishing threshold, $heta(G)$, is the minimum number of colors~$k$ such that any arbitrary $k$-coloring is distinguishing. Moreover, $Ph{i}_k(G)$ is the number of distinguishing coloring of $G$ using at most $k$ colors. In this paper, for some graph operations, namely, vertex-sum, rooted product, corona product and lexicographic product, we find formulae of the distinguishing number and threshold using $Ph{i}_k(G)$.

This page was built for publication: Distinguishing threshold for some graph operations

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