The distinguishing number and the distinguishing index of line and graphoidal graph(s)

Abstract

The distinguishing number (index) () of a graph is the least integer such that has a vertex labeling (edge labeling) with labels that is preserved only by a trivial automorphism. A graphoidal cover of is a collection of (not necessarily open) paths in such that every path in has at least two vertices, every vertex of is an internal vertex of at most one path in and every edge of is in exactly one path in . Let denote the intersection graph of . A graph is called a graphoidal graph, if there exist a graph and a graphoidal cover of such that . 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 .

Keywords

• distinguishing number
• distinguishing index
• line and graphoidal graph(s)