✦ LIBER ✦

Optimal orientations of products of paths and cycles

✍ Scribed by K.M. Koh; E.G. Tay

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 656 KB
Volume: 78
Category: Article
ISSN: 0166-218X
DOI: 10.1016/s0166-218x(97)00017-6

No coin nor oath required. For personal study only.

✦ Synopsis

For a graph G, let 9(G) be the family of strong orientations of G, d(G) = min{d(D) / D t 9' (G)} and p(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 p(G) = 0 if G is a Cartesian product of (I ) paths, and (2) paths and cycles, which satisfy some mild conditions.

📜 SIMILAR VOLUMES

On optimal orientations of Cartesian pro

On optimal orientations of Cartesian products of even cycles and paths

✍ Koh, K. M.; Tay, E. G. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

For a graph G , let D ( G ) be the family of strong orientations of G , and define d ៝ ( G ) Å min{d(D)ÉD √ D(G)}, where d(D) is the diameter of the digraph D. In this paper, we evaluate the values of d ៝ (C 2n 1

On optimal orientations of Cartesian pro

On optimal orientations of Cartesian products of even cycles

✍ Koh, K. M.; Tay, E. G. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 220 KB

For a graph G, let D(G) be the family of strong orientations of G. Define d ៝ (G) Å min {d(D)ÉD √ D(G)} and r(G) Å d ៝ (G) 0 d(G), where d(D) [respectively, d(G)] denotes the diameter of the digraph D (respectively, graph G). Let G 1 H denote the Cartesian product of the graphs G and H, and C p , th

On Optimal Orientations of Cartesian Pro

On Optimal Orientations of Cartesian Products of Trees

✍ Khee Meng Koh; E. G. Tay 📂 Article 📅 2001 🏛 Springer Japan 🌐 English ⚖ 220 KB

On optimal orientations of cartesian pro

On optimal orientations of cartesian products of graphs (I)

✍ K.M. Koh; E.G. Tay 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 807 KB

Kronecker products of paths and cycles:

Kronecker products of paths and cycles: Decomposition, factorization and bi-pancyclicity

✍ Pranava K. Jha 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 690 KB

Let G x H denote the Kronecker product of graphs G and H. Principal results are as follows: (a) If m is even and n-0 (mod 4), then one component of P,.+l x P,+1, and each component of each of CA x Pn+l, Pm+l x (7, and Cm x C, are edge decomposable into cycles of uniform length rs, where r and s are

Paths and cycles of hypergraphs

✍ Jianfang Wang; Tony T. Lee 📂 Article 📅 1999 🏛 SP Science China Press 🌐 English ⚖ 638 KB