𝔖 Bobbio Scriptorium
✦   LIBER   ✦

s-strongly perfect cartesian product of graphs

✍ Scribed by Elefterie Olaru; Eugen Mǎndrescu

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
308 KB
Volume
16
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

The study of perfectness, via the strong perfect graph conjecture, has given rise to numerous investigations concerning the structure of many particular classes of perfect graphs. In “Perfect Product Graphs” (Discrete Mathematics, Vol. 20, 1977, pp. 177‐‐186), G. Ravindra and K. R. Parthasarathy tried, but unfortunately without success, to characterize the perfectness of the cartesian product of graphs (see also MR No. 58‐‐10567, 1979). In this paper we completely characterize the graphs that are both nontrivial cartesian products and s‐strongly perfect.

📜 SIMILAR VOLUMES

Game coloring the Cartesian product of g
Game coloring the Cartesian product of graphs
✍ Xuding Zhu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB

## Abstract This article proves the following result: Let __G__ and __G__′ be graphs of orders __n__ and __n__′, respectively. Let __G__^\*^ be obtained from __G__ by adding to each vertex a set of __n__′ degree 1 neighbors. If __G__^\*^ has game coloring number __m__ and __G__′ has acyclic chromat

Embedding Cartesian Products of Graphs i
Embedding Cartesian Products of Graphs into de Bruijn Graphs
✍ Thomas Andreae; Michael Nölle; Gerald Schreiber 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 172 KB

## Given a Cartesian product G of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D = D B (n), it is investigated whether or not G is a spanning subgraph of D. Special attention is given to graphs G 1 × • • • × G m which are relevant for parallel computing, namely, to

Cartesian Products of Graphs and Metric
Cartesian Products of Graphs and Metric Spaces
✍ S. Avgustinovich; D. Fon-Der-Flaass 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We prove uniqueness of decomposition of a finite metric space into a product of metric spaces for a wide class of product operations. In particular, this gives the positive answer to the long-standing question of S. Ulam: 'If U × U V × V with U , V compact metric spaces, will then U and V be isometr

Circular chromatic index of Cartesian pr
Circular chromatic index of Cartesian products of graphs
✍ Douglas B. West; Xuding Zhu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract The __circular chromatic index__ of a graph __G__, written $\chi\_{c}'(G)$, is the minimum __r__ permitting a function $f : E(G)\rightarrow [0,r)$ such that $1 \le | f(e)-f(e')|\le r - 1$ whenever __e__ and $e'$ are incident. Let $G = H$ □ $C\_{2m +1}$, where □ denotes Cartesian product