✦ LIBER ✦

Counting stable sets on Cartesian products of graphs

✍ Scribed by Florence Forbes; Bernard Ycart

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 552 KB
Volume: 186
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00185-4

No coin nor oath required. For personal study only.

✦ Synopsis

We study the generating functions for the number of stable sets of all cardinalities, in the case of graphs which are Cartesian products by paths, cycles, or trees. Explicit results are given for products by cliques. Algorithms based on matrix products are derived for grids, cylinders, toruses and hypercubes.

📜 SIMILAR VOLUMES

Counting representable sets on simple gr

Counting representable sets on simple graphs

✍ Peter G. Jeavons 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 745 KB

On super connectivity of Cartesian produ

On super connectivity of Cartesian product graphs

✍ Min Lü; Chao Wu; Guo-Liang Chen; Cheng Lv 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 176 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

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

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