论文标题
关于距离平衡图的一些问题
On some problems regarding distance-balanced graphs
论文作者
论文摘要
据说，如果对于任何边缘$ uv $γ$，则据说是距离平衡的，接近$ u $的顶点数量比$ v $等于接近$ v $的顶点的数量，而不是$ v $，并且它被称为距离$ $，如果此外，如果此外，此数字与所选的Edge Edge $ uv $无关。据说，如果任何边缘$ uv $ $γ$和任何整数$ k $，从$ u $ $ u $和距离$ k+1 $的距离$ k+1 $等于$ k+u $ u $ u $ u $ k $的距离$ k+1 $等于$ k $的距离$ k $，则图形$γ$具有强大的距离平衡。 在本文中，我们回答了Kutnar和Miklavič[欧洲J. Combin。 39（2014），57-67]，通过构建几个无限距离距离平衡图的无限族，这些家族并非强烈平衡。我们反驳了关于Balakrishnan等人出现的强距离平衡图的表征的猜想。 [欧洲J. Combin。 30（2009），1048-1053]通过提供无限的反示例，并回答Kutnar等人提出的一个空旷的问题。在[离散数学。 306（2006），1881-1894]关于存在半度对称距离平衡图的存在，这些图并非通过提供无限的此类示例家族而无法强烈距离平衡。我们还表明，对于带有$ n $顶点的图$γ$，如果$γ$持续稳定，并且如果$γ$良好的距离平衡，则可以在$ o（mn）$时间中检查它。
A graph $Γ$ is said to be distance-balanced if for any edge $uv$ of $Γ$, the number of vertices closer to $u$ than to $v$ is equal to the number of vertices closer to $v$ than to $u$, and it is called nicely distance-balanced if in addition this number is independent of the chosen edge $uv$. A graph $Γ$ is said to be strongly distance-balanced if for any edge $uv$ of $Γ$ and any integer $k$, the number of vertices at distance $k$ from $u$ and at distance $k+1$ from $v$ is equal to the number of vertices at distance $k+1$ from $u$ and at distance $k$ from $v$. In this paper we answer an open problem posed by Kutnar and Miklavič [European J. Combin. 39 (2014), 57-67] by constructing several infinite families of nonbipartite nicely distance-balanced graphs which are not strongly distance-balanced. We disprove a conjecture regarding characterization of strongly distance-balanced graphs posed by Balakrishnan et al. [European J. Combin. 30 (2009), 1048-1053] by providing infinitely many counterexamples, and answer an open question posed by Kutnar et al. in [Discrete Math. 306 (2006), 1881-1894] regarding existence of semisymmetric distance-balanced graphs which are not strongly distance-balanced by providing an infinite family of such examples. We also show that for a graph $Γ$ with $n$ vertices and $m$ edges it can be checked in $O(mn)$ time if $Γ$ is strongly-distance balanced and if $Γ$ is nicely distance-balanced.
