Trade-offs among degree, diameter, and number of paths
Trade-offs among degree, diameter, and number of paths
复制标题
度数、直径和路径数量之间的权衡
DOI：
10.1016/j.dam.2022.12.007
复制
发表时间：
2023
影响因子：
1.1
通讯作者：
Kazuhisa Makino
中科院分区：
文献类型：
--
作者：
Toshimasa Ishii;Akitoshi Kawamura;Yusuke Kobayashi;Kazuhisa Makino
度直径问题是极图理论中的一个基本问题，它涉及三个参数之间的权衡：最大度，直径和图中的顶点数。在本文中，我们引入了另一个参数，代表了网络的鲁棒性，并研究参数之间的权衡。对于正整数r和k，我们说一个图是（r，k）-连通的，如果它包含r个内部顶点不相交的路，其长度至多为k。考虑一个最大度为最小的n阶（r，k）-连通图.我们的贡献是证明了这样一个图的最大度的最小值是Θ（max {rnk，r}），这是一个与常数因子紧密相关的界.
The degree diameter problem is a fundamental and well-studied problem in extremal graph theory, which deals with trade-offs among three parameters: the maximum degree, the diameter, and the number of vertices in a graph. In this paper, we introduce another parameter that represents the robustness of a network and investigate trade-offs among the parameters. For positive integers r and k, we say that a graph is (r, k)-connected if it contains r internally vertex-disjoint paths of length at most k between any pair of vertices. We consider an (r, k)-connected graph with n vertices whose maximum degree is minimized. Our contribution is to show that the minimum of the maximum degree of such a graph is Θ (max {r n k, r}), which is a tight bound up to constant factors.
登录
查看更多内容
渐近大（Delta，D）图
DOI：
10.1016/j.dam.2005.03.008
发表时间：
2005
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
E. Canale;José Gómez
通讯作者：
José Gómez
两个节点不相交的 3 跳约束可生存网络设计和多面体
DOI：
10.1016/j.endm.2013.05.137
发表时间：
2013
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
I. Diarrassouba;H. Kutucu;A. Mahjoub
通讯作者：
A. Mahjoub
DOI：
10.1002/scj.4690170803
发表时间：
1986
期刊：
Systems and Computers in Japan
影响因子：
--
作者：
M. Imase;T. Soneoka;Keiji Okada
通讯作者：
Keiji Okada
小直径网络的鲁棒性和抗攻击能力强
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Alexander Veremyev;V. Boginski
通讯作者：
V. Boginski
3 跳和 4 跳有界不相交路径问题的逼近性
DOI：
10.1007/978-3-642-13036-6_16
发表时间：
2010
期刊：
Conference on Integer Programming and Combinatorial Optimization
影响因子：
--
作者：
A. Bley;José Neto
通讯作者：
José Neto