Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.21916 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 [Discussiones Mathematicae. Graph Theory, 45(1) (2025) p.95] 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 link-irregular graphs on $n$-vertices for $n \leq 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\sqrt{\log n})$. Finally, we prove that all but finitely many link-irregular graphs are non-planar, and there is no regular link-irregular planar graphs.