𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The binding numbers of some Cartesian products of graphs

✍ Scribed by Danuta Michalak

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
238 KB
Volume
131
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In the paper we obtain some conditions under which the binding number bind (C) of a Cartesian product graph G is equal to

The concept of the binding number of a graph was introduced by Woodall in 1973 . The main theorem of Woodall's paper is a sufficient condition for the existence of a Hamiltonian circuit in terms of the binding number. Kane et al.

[S] computed the binding number for a variety of graph products. They conjectured that the Cartesian product G = C, x C, of two cycles has binding number (mn -l)/(mn -4) if mn is odd; that is, that G belongs to the class of graphs described in the Abstract. This conjecture was proved in [l, 2,8], and in fact the result holds (contrary to Proposition 3.3 of [S]) provided that at least one of m, n is odd. Using some properties of Hallian graphs, we here obtain some more general conditions under which the Cartesian product of two or more graphs belongs to this class of graphs.

We consider only finite simple graphs. The terminology and notations are the same as in [3] unless otherwise specified.

πŸ“œ 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__β–‘β‹…

On the crossing numbers of Cartesian pro
On the crossing numbers of Cartesian products with trees
✍ Drago Bokal πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 204 KB

## Abstract Zip product was recently used in a note establishing the crossing number of the Cartesian product __K__~1~,__n__ β–‘ __P__~m~. In this article, we further investigate the relations of this graph operation with the crossing numbers of graphs. First, we use a refining of the embedding metho

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