On optimal orientations of Cartesian products with a bipartite graph

DOI10.1016/S0166-218X(99)00110-9MaRDI QIDQ1961236zbMATH OpenOpenAlexFDO

Authors E. G. Tay, K. M. Koh

Publication date 22 May 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0166-218x(99)00110-9

zbMATH Keywords

Cartesian products of graphsdiameterorientations of graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20)

Review text

The authors consider strongly connected orientations of the minimum diameter of some graphs with no bridges. They prove that several families of Cartesian products of graphs satisfy the property that every graph of the family can be oriented without any increase in its diameter. This result extends some previously known results on orientations of graphs.

Recommendations

• On optimal orientations of Cartesian products of graphs. I
• Optimal orientations of vertex-multiplications of Cartesian products of graphs
• On optimal orientations of Cartesian products of graphs. II: Complete graphs and even cycles
• Optimal orientations of \(G\)-vertex multiplications of bipartite graphs
• On optimal orientations of Cartesian products of even cycles
• On optimal orientations of Cartesian products of even cycles and paths
• Optimal orientations of subgraphs of complete bipartite graphs
• On optimal orientations of Cartesian products of trees
• On optimal orientations of tensor product of complete graphs.
• Optimal orientations of products of paths and cycles

Cites work

• A Theorem on Graphs, with an Application to a Problem of Traffic Control
• Cycles and paths in semicomplete multipartite digraphs, theorems, and algorithms: a survey
• Diameter-preserving orientations of the torus
• Distances in orientations of graphs
• Every vertex a king
• scientific article; zbMATH DE number 4204370 (Why is no real title available?)
• scientific article; zbMATH DE number 3991530 (Why is no real title available?)
• scientific article; zbMATH DE number 3991541 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3566474 (Why is no real title available?)
• Methods and problems of communication in usual networks
• Minimizing and maximizing the diameter in orientations of graphs
• On optimal orientations of \(G\) vertex-multiplications
• On optimal orientations of Cartesian products of even cycles
• On optimal orientations of Cartesian products of even cycles and paths
• On optimal orientations of Cartesian products of graphs. I
• On optimal orientations of Cartesian products of graphs. II: Complete graphs and even cycles
• On optimal orientations of Cartesian products of trees
• On the Optimal Strongly Connected Orientations of City Street Graphs I: Large Grids
• On the optimal strongly connected orientations of city street graphs. II: Two east-west avenues or North—South Streets
• On the optimal strongly connected orientations of city street graphs. III. Three east–west avenues or north–south streets
• On the optimal strongly connected orientations of city street graphs. IV: Four east-west avenues or north-south streets
• Optimal orientations of products of paths and cycles
• Orientations of the n-cube with minimum diameter
• Robbins's Theorem for Mixed Multigraphs
• Strongly connected orientations of mixed multigraphs
• The diameter of an orientation of a complete multipartite graph
• The minimum diameter of orientations of complete multipartite graphs

Cited in

(15)

• On a conjecture concerning the orientation number of a graph
• On the optimal strongly connected orientations of city street graphs. IV: Four east-west avenues or north-south streets
• Optimal orientations of products of paths and cycles
• On optimal orientations of Cartesian products of graphs. I
• The diameter of strong orientations of Cartesian products of graphs
• A degree condition for diameter two orientability of graphs
• AT-free graphs: Linear bounds for the oriented diameter
• On optimal orientations of Cartesian products of graphs. II: Complete graphs and even cycles
• scientific article; zbMATH DE number 3991541 (Why is no real title available?)
• On optimal orientations of Cartesian products of even cycles and paths
• Oriented hypercubes
• On optimal orientations of Cartesian products of even cycles
• The orientation number of two complete graphs with linkages
• On optimal orientations of Cartesian products of trees
• On a conjecture concerning optimal orientations of the Cartesian product of a triangle and an odd cycle

This page was built for publication: On optimal orientations of Cartesian products with a bipartite graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1961236)