An upper bound on the distinguishing index of graphs with minimum degree at least two

zbMATH Open1463.05244arXiv1702.03524MaRDI QIDQ4969593FDOQ4969593

Authors: Saeid Alikhani, Samaneh Soltani 

Publication date: 13 October 2020

Abstract: The distinguishing index of a simple graph $G$, denoted by $D^{\prime }(G)$, is the least number of labels in an edge labeling of $G$ not preserved by any non-trivial automorphism. It was conjectured by Pil'sniak (2015) that for any 2-connected graph $D^{\prime }(G)leqlceilsqrtDelta(G)ceil+1$. We prove a more general result for the distinguishing index of graphs with minimum degree at least two from which the conjecture follows. Also we present graphs $G$ for which $D^{\prime }(G)leqlceilsqrtDeltaceil$.

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

Recommendations

• The optimal general upper bound for the distinguishing index of infinite graphs
• The distinguishing index of connected graphs without pendant edges
• Improving upper bounds for the distinguishing index
• Extremal graphs for the distinguishing index
• Distinguishing graphs by edge-colourings

zbMATH Keywords

upper bounddistinguishing indexedge-colourings

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Cites Work

• Symmetry breaking in graphs
• Handbook of product graphs
• Title not available (Why is that?)
• The distinguishing number of Cartesian products of complete graphs
• Distinguishing graphs by edge-colourings
• Distinguishing colorings of Cartesian products of complete graphs
• Distinguishing number and distinguishing index of certain graphs
• Trees with distinguishing index equal distinguishing number plus one
• Improving upper bounds for the distinguishing index

Cited In (6)

• 2-distance vertex-distinguishing index of subcubic graphs
• The distinguishing index of connected graphs without pendant edges
• Trees with distinguishing number two
• The optimal general upper bound for the distinguishing index of infinite graphs
• Improving upper bounds for the distinguishing index
• Edge-distinguishing of star-free graphs

This page was built for publication: An upper bound on the distinguishing index of graphs with minimum degree at least two

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