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 条
  • [41] THE INFLUENCE OF SEPARATING CYCLES IN DRAWINGS OF K5 \ ε IN THE JOIN PRODUCT WITH PATHS AND CYCLES
    Stas, Michal
    Timkova, Maria
    MATHEMATICA SLOVACA, 2024, 74 (05) : 1089 - 1106
  • [42] Decomposition of Product Graphs into Paths and Cycles of Length Four
    S. Jeevadoss
    A. Muthusamy
    Graphs and Combinatorics, 2016, 32 : 199 - 223
  • [43] Decomposition of Product Graphs into Paths and Cycles of Length Four
    Jeevadoss, S.
    Muthusamy, A.
    GRAPHS AND COMBINATORICS, 2016, 32 (01) : 199 - 223
  • [44] Cycles and Paths Related Vertex-Equitable Graphs
    Nazeer S.
    Sultana N.
    Bonyah E.
    J. Comb. Math. Comb. Comp., 2023, (15-24): : 15 - 24
  • [45] Spectral conditions for the existence of specified paths and cycles in graphs
    Zhai, Mingqing
    Lin, Huiqiu
    Gong, Shicai
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2015, 471 : 21 - 27
  • [46] b-chromatic numbers of powers of paths and cycles
    Lin, Wu-Hsiung
    Chang, Gerard J.
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (16-17) : 2532 - 2536
  • [47] Global defensive alliances in the lexicographic product of paths and cycles
    Barbosa, Rommel M.
    Dourado, Mitre C.
    da Silva, Leila R. S.
    DISCRETE APPLIED MATHEMATICS, 2020, 283 : 168 - 188
  • [48] Decomposition of hypercube graphs into paths and cycles of length four
    Saranya, D.
    Jeevadoss, S.
    AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2022, 19 (02) : 141 - 145
  • [49] Optimal L(2,1)-labeling of strong products of cycles
    Jha, PK
    IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-FUNDAMENTAL THEORY AND APPLICATIONS, 2001, 48 (04): : 498 - 500
  • [50] Distance restricted optimal pebbling in paths
    Shiue, Chin-Lin
    DISCRETE APPLIED MATHEMATICS, 2021, 297 : 46 - 54
12345