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

2017/02/12 by ‎Saeid Alikhani, Alikhani, Saeid, Samaneh Soltani +1
Computer Science · #05C15 #05C25 #Caching and Content Delivery #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1702.03524

openalex publication_date 2017/02/12 · openalex created_date 2017/04/28 · openalex updated_date 2026/07/28

Abstract

The distinguishing index of a simple graph G, denoted by D'(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śniak (2015) that for any 2-connected graph D'(G) ≤ \lceil √(Δ(G))\rceil +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'(G)≤ \lceil √(Δ)\rceil.

Related

• Relationship between the distinguishing index, minimum degree and maximum degree of graphs
• The distinguishing index of graphs with infinite minimum degree
• Distinguishing number and distinguishing index of certain graphs
• The distinguishing index of graphs with at least one cycle is not more than its distinguishing number
• Trees with distinguishing index equal distinguishing number plus one