๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The Cartesian product of hypergraphs

โœ Scribed by Lydia Ostermeier; Marc Hellmuth; Peter F. Stadler

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
236 KB
Volume
70
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

Abstract

We show that every simple, (weakly) connected, possibly directed and infinite, hypergraph has a unique prime factor decomposition with respect to the (weak) Cartesian product, even if it has infinitely many factors. This generalizes previous results for graphs and undirected hypergraphs to directed and infinite hypergraphs. The proof adopts the strategy outlined by Imrich and ลฝerovnik for the case of graphs and introduces the notion of diagonalโ€free grids as a replacement of the chordโ€free 4โ€cycles that play a crucial role in the case of graphs. This leads to a generalization of relation ฮ” on the arc set, whose convex hull is shown to coincide with the product relation of the prime factorization. ยฉ 2011 Wiley Periodicals, Inc. J Graph Theory

๐Ÿ“œ 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

The determining number of a Cartesian pr
The determining number of a Cartesian product
โœ Debra L. Boutin ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 118 KB

## Abstract A set __S__ of vertices is a determining set for a graph __G__ if every automorphism of __G__ is uniquely determined by its action on __S__. The determining number of __G__, denoted Det(__G__), is the size of a smallest determining set. This paper begins by proving that if __G__=__G__โ–กโ‹…

s-strongly perfect cartesian product of
s-strongly perfect cartesian product of graphs
โœ Elefterie Olaru; Eugen MวŽndrescu ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 308 KB

## 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.

When the cartesian product of directed c
When the cartesian product of directed cycles is Hamiltonian
โœ William T. Trotter Jr.; Paul Erdรถs ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 225 KB

The Cartesian product of two hamiltonian graphs is always hamiltonian. For directed graphs, the analogous statement is false. We show that the Cartesian product C,,, x C, , of directed cycles is hamiltonian if and only if the greatest common divisor (g.c.d.) d of n, and n, is a t least two and there