The Maximum of the Maximum Rectilinear Crossing Numbers of d-Regular Graphs of Order n
The Maximum of the Maximum Rectilinear Crossing Numbers of d-Regular Graphs of Order n
复制标题
n阶d-正则图的最大直线交叉数的最大值
DOI：
--
复制
发表时间：
2008
影响因子：
0.7
通讯作者：
H. Harborth
中科院分区：
文献类型：
--
作者：
M. Alpert;E. Feder;H. Harborth
我们将已知的关于循环图（$C_n$）和完全图（$K_n$）的最大直线交叉数的结果推广到一般图$d$-正则图$R_{n,d}$的类。给出了阶为$n$的$d$-正则图$S_{n,d}$的广义星图，其中$n+dequiv 1 pmod 2 $，证明了它们使最大直线交叉数最大化。对$n equiv d equiv 0 pmod 2$引入了$S_{n,d}$的星形图，我们推测该图也最大化了最大直线交叉数。我们对最初由Furry和Kleitman证明的两个结果提供了一个更简单的证明，作为这个猜想方向的部分结果。
We extend known results regarding the maximum rectilinear crossing number of the cycle graph ($C_n$) and the complete graph ($K_n$) to the class of general $d$-regular graphs $R_{n,d}$. We present the generalized star drawings of the $d$-regular graphs $S_{n,d}$ of order $n$ where $n+dequiv 1 pmod 2 $ and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of $S_{n,d}$ for $n equiv d equiv 0 pmod 2$ is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by Furry and Kleitman as partial results in the direction of this conjecture.