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

MaRDI QIDQ4969593zbMATH OpenFDO

Authors Saeid Alikhani, Samaneh Soltani

Publication date 13 October 2020

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

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)

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

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

Cites work

• scientific article; zbMATH DE number 5054146 (Why is no real title available?)
• Distinguishing colorings of Cartesian products of complete graphs
• Distinguishing graphs by edge-colourings
• Distinguishing number and distinguishing index of certain graphs
• Handbook of product graphs
• Improving upper bounds for the distinguishing index
• Symmetry breaking in graphs
• The distinguishing number of Cartesian products of complete graphs
• Trees with distinguishing index equal distinguishing number plus one

Cited in

(6)

• Trees with distinguishing number two
• Improving upper bounds for the distinguishing index
• Edge-distinguishing of star-free graphs
• The optimal general upper bound for the distinguishing index of infinite graphs
• The distinguishing index of connected graphs without pendant edges
• 2-distance vertex-distinguishing index of subcubic 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)