On link-irregular labelings of graphs
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\).
This page was built for publication: On link-irregular labelings of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858802)
