Optimal orientations of products of paths and cycles

被引：17
作者：
Koh, KM
Tay, EG
机构：
[1] Department of Mathematics, National University of Singapore, Lower Kent Ridge Road
来源：
DISCRETE APPLIED MATHEMATICS | 1997年 / 78卷 / 1-3期
关键词：
path; cycle; bipartite graph; diameter; strong orientation;
D O I：
10.1016/S0166-218X(97)00017-6
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
For a graph G, let D(G) be the family of strong orientations of G, d(G) = min{d(D)\D is an element of D (G)) and rho(G) = d(G)-d(G), where d(G) and d(D) are the diameters of G and D respectively. in this paper we show that rho(G)=0 if G is a cartesian product of(1) paths, and (2) paths and cycles, which satisfy some mild conditions.
引用
收藏
页码：163 / 174
页数：12
相关论文
共 50 条
12345