𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distinguishing Cartesian powers of graphs

✍ Scribed by Wilfried Imrich; Sandi Klavžar

Publisher
John Wiley and Sons
Year
2006
Tongue
English
Weight
132 KB
Volume
53
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

The distinguishing number D(G) of a graph is the least integer d such that there is a d-labeling of the vertices of G that is not preserved by any nontrivial automorphism of G. We show that the distinguishing number of the square and higher powers of a connected graph G = K 2 , K 3 with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 (2005), #N17] on powers of prime graphs, and results of Klavžar and Zhu [Eu J Combin, to appear]. More generally, we also prove that d(G H) = 2 if G and H are relatively prime and |H| ≤ |G| < 2 |H| -|H|. Under additional conditions similar results hold for powers of graphs with respect to the strong and the direct product.

📜 SIMILAR VOLUMES

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

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

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.

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