✦ LIBER ✦

On optimal orientations of Cartesian products of even cycles and paths

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

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 122 KB
Volume: 30
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199708)30:1<1::aid-net1>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 SIMILAR VOLUMES

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

Cartesian products of trees and paths

✍ Bandelt, Hans-J�rgen; Burosch, Gustav; Laborde, Jean-Marie 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

We characterize the (weak) Cartesian products of trees among median graphs by a forbidden 5-vertex convex subgraph. The number of tree factors (if finite) is half the length of a largest isometric cycle. Then a characterization of Cartesian products of n trees obtains in terms of isometric cycles an

On relative length of longest paths and

On relative length of longest paths and cycles

✍ Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract For a graph __G__, __p__(__G__) and __c__(__G__) denote the order of a longest path and a longest cycle of __G__, respectively. In this paper, we prove that if __G__ is a 3 ‐connected graph of order __n__ such that the minimum degree sum of four independent vertices is at least __n__+ 6

Small cycle double covers of products I:

Small cycle double covers of products I: Lexicographic product with paths and cycles

✍ R. J. Nowakowski; K. Seyffarth 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 243 KB

## Abstract Bondy conjectured that every simple bridgeless graph has a small cycle double cover (SCDC). We show that this is the case for the lexicographic products of certain graphs and along the way for the Cartesian product as well. Specifically, if __G__ does not have an isolated vertex then __

On Computability Theoretic Properties of

On Computability Theoretic Properties of Structures and Their Cartesian Products

✍ Bakhadyr Khoussainov 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

A theorem on integer flows on cartesian

A theorem on integer flows on cartesian products of graphs

✍ Wilfried Imrich; Riste Škrekovski 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB

## Abstract It is shown that the Cartesian product of two nontrivial connected graphs admits a nowhere‐zero 4‐flow. If both factors are bipartite, then the product admits a nowhere‐zero 3‐flow. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 93–98, 2003