On link-irregular labelings of graphs (Q6858802)

Let \(G\) be a graph and \(L(v)\) the subgraph induced on the neighbors of \(v\), called the link of \(v\). If for every \(u\neq v\) the links \(L(u)\) and \(L(v)\) are isomorphic, we say that \(G\) is link-regular. If on the other hand for every \(u\neq v\) the links \(L(u)\) and \(L(v)\) are not isomorphic, we say that \(G\) is link-irregular.\N\NFurther, let \(l : E(G)\to Z^+\) be an edge-labeling of \(G\), assigning a positive integer to each edge. For a vertex \(v\in V(G)\), the labeled link of \(v\), denoted \(L_l(v)\), is the induced subgraph of \(G\) on the neighborhood of \(v\), with edge labels coming from labeling \(l\). An isomorphism of labeled graphs is an isomorphism of their underlying graphs that maps edges with a given label onto edges with that same label.\N\NThe labeling \(l\) is link-irregular if for all pairs of distinct vertices \(u, v\in V (G)\), the labeled links are pairwise non-isomorphic.\N\NThe authors observe several conditions for the existence of a link-irregular labeling and show that certain well-known graph families do not admit such a labeling: bipartite graphs, cycles \(C_n\) for \(n\geq4\), complete multipartite graphs with at least one partite set with more than one vertex. On the other hand, they show that complete graphs \(K_n\) for \(n\geq3\) and wheels \(W_n\) for \(n=3\) and \(n\geq5\) admit a link-irregular labeling. They also determine the minimum number \(\eta(G)\) of distinct labels needed for such a labeling of these graphs. In particular, they show that for \(n\) large enough, \(\eta(W_n)\approx\sqrt{2n}\) and \(\eta(K_n)=3\) for \(n=3,4,5\) and \(\eta(K_n)=2\) for \(n\geq 6\).\N\NFinally, they show that for every \(n>0\) there exists a graph \(H_n\) with \(\eta(H_n)=n\).