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

共 19 条

[1] ROBBINS THEOREM FOR MIXED MULTIGRAPHS [J].