2017/08/19 by Alikhani, Saeid, Soltani, Samaneh · 1 citation
#05C25 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1708.05822
The distinguishing number (index) D(G) (D'(G)) of a graph G is the least integer d such that G has an vertex labeling (edge labeling) with d labels that is preserved only by a trivial automorphism. A graphoidal cover of G is a collection ψ of (not necessarily open) paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. Let Ω(G,ψ) denote the intersection graph of ψ. A graph H is called a graphoidal graph, if there exists a graph G and a graphoidal cover ψ of G such that H≅ Ω(G, ψ). In this paper, we study the distinguishing number and the distinguishing index of the line graph and the graphoidal graph of a simple connected graph G.