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 条
  • [1] Optimal Orientations of the Generalized Cycles
    孙良
    卜卿
    Journal of Beijing Institute of Technology(English Edition), 2005, (03) : 332 - 335
  • [2] Optimal Identifying Codes in Cycles and Paths
    Junnila, Ville
    Laihonen, Tero
    GRAPHS AND COMBINATORICS, 2012, 28 (04) : 469 - 481
  • [3] Optimal Identifying Codes in Cycles and Paths
    Ville Junnila
    Tero Laihonen
    Graphs and Combinatorics, 2012, 28 : 469 - 481
  • [4] Vertex-neighbor-toughness of the Cartesian Products of paths and cycles
    Wei, Zongtian
    Yang, Jingting
    Li, Yinkui
    Yue, Chao
    ARS COMBINATORIA, 2019, 147 : 63 - 78
  • [5] On the Crossing Numbers of Cartesian Products of Small Graphs with Paths, Cycles and Stars
    Clancy K.
    Haythorpe M.
    Newcombe A.
    Journal of Combinatorial Mathematics and Combinatorial Computing, 2024, 119 : 323 - 333
  • [6] Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity
    Jha, PK
    DISCRETE MATHEMATICS, 1998, 182 (1-3) : 153 - 167
  • [7] On L(2,1)-labelings of Cartesian products of paths and cycles
    Kuo, D
    Yan, JH
    DISCRETE MATHEMATICS, 2004, 283 (1-3) : 137 - 144
  • [8] 2-distance colorings of some direct products of paths and cycles
    Kim, Byeong Moon
    Song, Byung Chul
    Rho, Yoomi
    DISCRETE MATHEMATICS, 2015, 338 (10) : 1730 - 1739
  • [9] Classification of l(2, 1)-labeling of cartesian products of paths and cycles
    Zhao T.
    Zhou X.
    Zhao, Taiyin, 1600, American Scientific Publishers (13): : 388 - 393
  • [10] The Crossing Numbers of Join Products of Paths and Cycles with Four Graphs of Order Five
    Stas, Michal
    MATHEMATICS, 2021, 9 (11)
12345