Partial Star Products: A Local Covering Approach for the Recognition of Approximate Cartesian Product Graphs

This paper is concerned with the recognition of approximate graph products with respect to the Cartesian product. Most graphs are prime, although they can have a rich product-like structure. The proposed algorithms are based on a local approach that covers a graph by small subgraphs, so-called partial star products, and then utilizes this information to derive the global factors and an embedding of the graph under investigation into Cartesian product graphs.     

Distinguishing Cartesian powers of graphs

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₂, K₃ with respect to the Cartesian product is 2. This result strengthens results of Albertson [Electron J Combin, 12 ( 1 ), #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. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 250–260, 2006     

Factoring cartesian-product graphs

In a fundamental paper, G. Sabidussi [“Graph Multiplication,” Mathematische Zeitschrift, Vol. 72 (1960), pp. 446–457] used a tower of equivalence relations on the edge set E(G) of a connected graph G to decompose G into a Cartesian product of prime graphs. Later, a method by R.L. Graham and P.M. Winkler [“On Isometric Embeddings of Graphs,” Transactions of the American Mathematics Society, Vol. 288 (1985), pp. 527–533] of embedding a connected graph isometrically into Cartesian products opened another approach to this problem. In both approaches an equivalence relation σ that determines the prime factorization is constructed. The methods differ by the starting relations used. We show that σ can be obtained as the convex hull of the starting relation used by Sabidussi. Our result also holds for the relation determining the prime decomposition of infinite connected graphs with respect to the weak Cartesian product. Moreover, we show that this relation is the transitive closure of the union of the starting relations of Sabidussi and Winkler [“Factoring a Graph in Polynomial Time,” European Journal of Combinatorics, Vol. 8 (1987), pp. 209–212], thereby generalizing the result of T. Feder [“Product Graph Representations,” Journal of Graph Theory, Vol 16 (1993), pp. 467–488] from finite to infinite graphs.     

A note on bounded automorphisms of infinite graphs

LetX be a connected locally finite graph with vertex-transitive automorphism group. IfX has polynomial growth then the set of all bounded automorphisms of finite order is a locally finite, periodic normal subgroup ofAUT(X) and the action ofAUT(X) onV(X) is imprimitive ifX is not finite. IfX has infinitely many ends, the group of bounded automorphisms itself is locally finite and periodic.     

On the weak reconstruction of Cartesian-product graphs

In this paper we reconstruct nontrivial connected Cartesian-product graphs from single vertex deleted subgraphs. We show that all one-vertex extensions of a given connected graph H, finite or infinite, to a nontrivial Cartesian product are isomorphic.     

Cartesian products of directed graphs with loops

We show that every nontrivial finite or infinite connected directed graph with loops and at least one vertex without a loop is uniquely representable as a Cartesian or weak Cartesian product of prime graphs. For finite graphs the factorization can be computed in linear time and space.     

Antibandwidth of three-dimensional meshes

The antibandwidth problem is to label vertices of a graph G=(V,E) bijectively by 0,1,2,…,|V|−1 so that the minimal difference of labels of adjacent vertices is maximised. In this paper we prove an almost exact result for the antibandwidth of three-dimensional meshes. Provided results are extensions of the two-dimensional case and an analogue of the result for the bandwidth of three-dimensional meshes obtained by FitzGerald.