Trees with distinguishing index equal distinguishing number plus one

DOI10.7151/DMGT.2162MaRDI QIDQ2175243zbMATH OpenOpenAlexWikidataFDO

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)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

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)

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)$.

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

Cites work

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

Cited in

(9)

• Trees with distinguishing number two
• scientific article; zbMATH DE number 1472093 (Why is no real title available?)
• On symmetries of edge and vertex colourings of graphs
• The distinguishing number and the distinguishing index of graphs from primary subgraphs
• An upper bound on the distinguishing index of graphs with minimum degree at least two
• Distinguishing geometric graphs
• Distinguishability of locally finite trees
• Equitable distinguishing chromatic number
• Extremal graphs for the distinguishing index

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)