Trees with distinguishing index equal distinguishing number plus one

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

Authors: Saeid Alikhani, Sandi Klavžar, Florian Lehner, 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

Recommendations

• Trees with distinguishing number two
• Distinguishing number and distinguishing index of certain graphs
• The chromatic distinguishing index of certain graphs
• Distinguishing number and distinguishing index of join of two specific graphs
• Distinguishability of locally finite trees

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 (8)

• An upper bound on the distinguishing index of graphs with minimum degree at least two
• Distinguishability of locally finite trees
• 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)