On the scramble number of graphs
On the scramble number of graphs
复制标题
关于图的置乱数
DOI：
10.1016/j.dam.2021.12.009
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Weber, Ben
中科院分区：
文献类型：
--
作者：
Echavarria, Marino;Everett, Max;Huang, Robin;Jacoby, Liza;Morrison, Ralph;Weber, Ben
图的乱序数是最近发展起来的一个不变量，用于研究图的可除性。本文证明了乱序数是NP-难计算的，同时也证明了即使对于简单图和度量图，计算一致性也是NP-难的。我们还提供了一般的笛卡尔积图的扰码数的下界，并应用这些计算角为许多新的产品图的家庭。
The scramble number of a graph is an invariant recently developed to aid in the study of divisorial gonality. In this paper we prove that scramble number is NP-hard to compute, also providing a proof that computing gonality is NP-hard even for simple graphs, as well as for metric graphs. We also provide general lower bounds for the scramble number of a Cartesian product of graphs, and apply these to compute gonality for many new families of product graphs.
登录
查看更多内容
计算图的连通性很困难
DOI：
10.1016/j.dam.2020.08.013
发表时间：
2015
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
D. Gijswijt;H. Smit;M. V. D. Wegen
通讯作者：
M. V. D. Wegen
粘合网格图的树宽和多角性
影响因子：
1.1
作者：
Ivan Aidun;Frances Dean;Ralph Morrison;Teresa Yu;Julie Yuan
通讯作者：
Julie Yuan
图连通性的新下界
影响因子：
1.1
作者：
Michael T. Harp;Elijah E. S. Jackson;D. Jensen;Noah Speeter
通讯作者：
Noah Speeter
图的调性序列
DOI：
10.1137/20m1323072
发表时间：
2020
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
Ivan Aidun;Frances Dean;Ralph Morrison;Teresa Yu;Julie Yuan
通讯作者：
Julie Yuan
论图的笛卡尔积的Goality
DOI：
10.37236/9307
发表时间：
2019
期刊：
Electron. J. Comb.
影响因子：
--
作者：
Ivan Aidun;Ralph Morrison
通讯作者：
Ralph Morrison