Trees with distinguishing index equal distinguishing number plus one

DOI10.7151/DMGT.2162zbMATH Open1439.05075arXiv1608.03501OpenAlexW2964187151WikidataQ129108949 ScholiaQ129108949MaRDI QIDQ2175243FDOQ2175243

Sandi Klavžar, Florian Lehner, Saeid Alikhani, Samaneh Soltani

Publication date: 28 April 2020

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: The distinguishing number (index) $D(G)$ ($D^{\prime }(G)$) of a graph $G$ is the least integer $d$ such that $G$ has an vertex (edge) labeling with $d$ labels that is preserved only by the trivial automorphism. It is known that for every graph $G$ we have $D^{\prime }(G)leqD(G)+1$. In this note we characterize trees for which this inequality is sharp. We also show that if $G$ is a connected unicyclic graph, then $D^{\prime }(G)=D(G)$.

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

zbMATH Keywords

automorphism groupunicyclic graphdistinguishing numberdistinguishing index

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Group actions on combinatorial structures (05E18)

Cites Work

• Symmetry breaking in graphs
• The distinguishing number of the augmented cube and hypercube powers
• Distinguishing labeling of group actions
• Graphs with large distinguishing chromatic number
• Distinguishing number of countable homogeneous relational structures
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• The distinguishing chromatic number
• Distinguishability of locally finite trees
• Distinguishing labellings of group action on vector spaces and graphs
• Distinguishing graphs by edge-colourings
• On computing the distinguishing numbers of trees and forests
• Bounds for distinguishing invariants of infinite graphs
• Distinguishing Cartesian products of countable graphs
• The list distinguishing number equals the distinguishing number for interval graphs
• Ein Ordnungsbegriff für Graphen ohne unendliche Wege mit einer Anwendung auf n-fach zusammenhaengende Graphen
• Bounding the distinguishing number of infinite graphs and permutation groups
• Breaking graph symmetries by edge colourings
• On symmetries of edge and vertex colourings of graphs
• Distinguishing graphs with intermediate growth
• A New Game Invariant of Graphs: the Game Distinguishing Number
• Distinguishing number and distinguishing index of natural and fractional powers of graphs
• THE DISTINGUISHING NUMBERS OF MERGED JOHNSON GRAPHS

Cited In (7)

• An upper bound on the distinguishing index of graphs with minimum degree at least two
• Title not available (Why is that?)
• Extremal graphs for the distinguishing index
• Equitable distinguishing chromatic number
• Trees with distinguishing number two
• On symmetries of edge and vertex colourings of graphs
• Distinguishing geometric graphs

This page was built for publication: Trees with distinguishing index equal distinguishing number plus one

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