Cycles, Paths, Connectivity and Diameter in Distance Graphs

机译：距离图中的循环，路径，连通性和直径

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

For n ∈ N and D (C) N, the distance graph Pnd has vertex set {0,1,... ,n — 1} and edge set {ij | 0 ≤ i, j ≤ n — 1, |j — i| ∈ D}. The class of distance graphs generalizes the important and very well-studied class of circulant graphs which have been proposed for numerous applications concerning networks, distributed systems and chip design. We prove that the class of circulant graphs coincides with the class of regular distance graphs. Extending some of the fundamental results concerning circulant graphs, we study the existence of long cycles and paths in distance graphs and analyse the computational complexity of problems related to their connectivity and diameter.

机译：对于n∈N和D（C）N，距离图Pnd具有顶点集{0,1，...，n_1}和边缘集{ij | 0≤i，j≤n — 1，| j — i | ∈D}。距离图的类别概括了重要且经过充分研究的循环图的类别，循环图已针对网络，分布式系统和芯片设计的众多应用提出。我们证明了循环图的类别与规则距离图的类别一致。扩展了关于循环图的一些基本结果，我们研究了距离图中长周期和路径的存在，并分析了与它们的连通性和直径有关的问题的计算复杂性。

著录项

来源
《Graph-theoretic concepts in computer science》|2009年|p.320-328|共9页
会议地点 Montpellier(FR);Montpellier(FR)
作者
Lucia Draque Penso; Dieter Rautenbach; Jayme Luiz Szwarcfiter;
展开▼
作者单位

Institut fur Theoretische Informatik, Technische Universitat Ilmenau, Postfach100565, D-98684 Ilmenau, Germany;

Institut fur Mathematik, Technische Universitat Ilmenau, Postfach 100565,D-98684 Ilmenau, Germany;

Universidade Federal do Rio de Janeiro, Instituto de Matematica, NCE and COPPE, Caixa Postal 2324, 20001-970 Rio de Janeiro, RJ, Brasil;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算机网络;
关键词
circulant graph; distance graph; multiple loop networks; connectivity; diameter; hamiltonian cycle; hamiltonian path;

机译：循环图距离图;多回路网络；连接性；直径;哈密尔顿周期哈密尔顿路径;

相似文献

外文文献
中文文献
专利

1. A new lower bound on the strong connectivity of an oriented graph. Application to diameters with a particular case related to Caccetta Ha:ggkvist conjecture A new lower bound on the strong connectivity of an oriented graph. Application to diameters with a particular case related to Caccetta Ha:ggkvist conjecture A new lower bound on the strong connectivity of an oriented graph. Application to diameters with a particular case related to Caccetta Ha:ggkvist conjecture [J] . Nicolas Lichiardopol Discrete mathematics . 2008,第22期

机译：定向图的强连通性的新下限。应用于与Caccetta Ha：ggkvist猜想有关的特殊情况的直径定向图的强连通性上的新下界。应用于与Caccetta Ha：ggkvist猜想有关的特殊情况的直径定向图的强连通性上的新下界。适用于与Caccetta Ha：ggkvist猜想有关的特殊情况的直径
2. Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs [J] . Guo L., Yang W., Guo X. Applied mathematics letters . 2013,第1期

机译：分裂图的Kronecker产品，循环的幂，路径的幂和完整图的超连通性
3. On the quotients between the eccentric connectivity index and the eccentric distance sum of graphs with diameter 2 [J] . Hua Hongbo Discrete Applied Mathematics . 2020,第1期

机译：在偏心连接索引与直径2的偏心距离和图之间的标本上
4. Cycles, Paths, Connectivity and Diameter in Distance Graphs [C] . Lucia Draque Penso, Dieter Rautenbach, Jayme Luiz Szwarcfiter International Workshop on Graph-Theoretic Concepts in Computer Science . 2010

机译：距离图中的循环，路径，连接和直径
5. On strong connectivity and cycles in graphs. [D] . Tansey, Gerard R. 2005

机译：在图形中具有强大的连通性和循环性。
6. On the distribution of cycles and paths in multichromosomal breakpoint graphs and the expected value of rearrangement distance [O] . Pedro Feijão, Fábio Viduani Martinez, Annelyse Thévenin 2015

机译：关于多染色体断点图中的循环和路径的分布以及重排距离的期望值
7. Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs [O] . Guo Litao, Yang Weihua, Guo Xiaofeng 2013

机译：分裂图的Kronecker产品，循环的幂，路径的幂和完整图的超连通性
8. A Synopsis of Known Distance-Regular Graphs with Large Diameters [R] . Cohen, A. M. 1982

机译：大直径已知距离 - 正则图的概要

Cycles, Paths, Connectivity and Diameter in Distance Graphs

摘要

著录项

相似文献

相关主题

期刊订阅