关于链不规则图的正则性、平面性和边界的探讨

On the Regularity, Planarity and Edge Bounds of Link-irregular Graphs

摘要 Abstract

若图 \( G \) 的每两个不同顶点的链均互不同构,则称其为链不规则图。图 \( G \) 中顶点 \( v \) 的链是由 \( v \) 的邻域在 \( G \) 中诱导出的子图。Ali、Chartrand 和 Zhang [Discussiones Mathematicae. Graph Theory, 45(1) (2025) 第95页] 猜测不存在正则链不规则图。本文证明了对于足够大的 \( r \),存在 \( r \)-正则链不规则图的可能性非常大。具体而言,我们构造了一个具有 12 个顶点的 7-正则链不规则图,这构成了对上述猜测的反例。此外,我们证明了不存在二分图形式的链不规则图,并且当 \( n \leq 9 \) 时,不存在 \( n \)-顶点上的正则链不规则图。我们还确定了链不规则图的边数的上下界,并证明了 \( n \) 顶点链不规则图的最小边数为 \( \Omega(n\sqrt{\log n}) \)。最后,我们证明除了有限个例外情况外,所有链不规则图均为非平面图,并且不存在正则链不规则平面图。

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 $\Omega(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.

关于链不规则图的正则性、平面性和边界的探讨 - arXiv