On the regularity, planarity and edge bounds of link-irregular graphs

A graph G is a link-irregular graph if every two distinct vertices of G have non-isomorphic links.The link of a vertex v in G is the subgraph induced by the neighbors of v in G. Ali, Chartrand and Zhang [On link-irregular graphs, Discuss.Math.Graph Theory 45 (1) (2025) 95-110] conjectured that there exists no regular link-irregular graph.In this paper, we show that the existence of an r-regular link-irregular graph is very likely for large enough r.In particular, we provide a 7-regular link-irregular graph on 12 vertices, which serves as a counterexample to the conjecture.Additionally, we prove that no bipartite link-irregular graphs exist, and there are no regular linkirregular graphs on n-vertices for n ≤ 9. Also, we determine upper and lower bounds for the number of edges of link-irregular graphs.Furthermore, we show the minimum number of edges in a link-irregular graph on the n vertices is Ω(n √ log n).Finally, we prove that all but finitely many linkirregular graphs are non-planar, and there is no regular link-irregular planar graphs.