论文标题
亚立管图中的指数独立性
Exponential Independence in Subcubic Graphs
论文作者
论文摘要
图$ g $的顶点的$ s $是指数独立的，如果对于$ s $中的每个顶点$ u $，$ s $ \ sum \ limits_ { dist} _ {（g，s）}（u，v）-1} <1，$$其中$ {\ rm dist} _ {（g，s）}（u，v）$是图形$ g-（s \ setMinus \ \ \ v \ v \ f \ f \ f \ f \}）$ u $和$ v $之间的距离。 $ g $的指数独立数$α_e（g）$是$ g $的指数独立设置的最大订单。在本文中，我们介绍了有关此参数的几个范围，并突出了许多相关的开放问题中的一些。特别是，我们证明了$ n $的亚地下图具有指数独立的订单$ω（n/\ log^2（n）$的订单集，无限立方树没有呈指数性独立的正密度集，并且$ n $的亚立管树具有指数独立的订单订单集合$（n+3）/4 $ 4 $。
A set $S$ of vertices of a graph $G$ is exponentially independent if, for every vertex $u$ in $S$, $$\sum\limits_{v\in S\setminus \{ u\}}\left(\frac{1}{2}\right)^{{\rm dist}_{(G,S)}(u,v)-1}<1,$$ where ${\rm dist}_{(G,S)}(u,v)$ is the distance between $u$ and $v$ in the graph $G-(S\setminus \{ u,v\})$. The exponential independence number $α_e(G)$ of $G$ is the maximum order of an exponentially independent set in $G$. In the present paper we present several bounds on this parameter and highlight some of the many related open problems. In particular, we prove that subcubic graphs of order $n$ have exponentially independent sets of order $Ω(n/\log^2(n))$, that the infinite cubic tree has no exponentially independent set of positive density, and that subcubic trees of order $n$ have exponentially independent sets of order $(n+3)/4$.
