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.     

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.     

Intermediate-node initiated reservation (IIR): a new signaling scheme for wavelength-routed networks

A problem of many distributed lightpath provisioning schemes is wavelength contention, which occurs when a connection request attempts to reserve a wavelength channel that is no longer available. This situation results from the lack of updated global link-state information at every node. In networks with highly dynamic traffic loads, wavelength contention may seriously degrade the network performance. To overcome this problem, we propose a new framework for distributed signaling and introduce a class of schemes referred to as intermediate-node initiated reservation. In the new scheme, reservations may be initiated at any set of nodes along the route; in contrast, reservations can only be initiated by the destination node in the classic destination initiated reservation (DIR) scheme. As a result, the possibility of having outdated information due to propagation delay is significantly lowered. Specifically, we consider two schemes within this framework, for networks with no wavelength conversion and for networks with sparse wavelength conversion, respectively. Theoretical and simulation results show that, compared with the classic DIR scheme, the new schemes can significantly improve the network blocking performance. The accuracy of the analytical models is also confirmed by extensive numerical simulations.     

Differential service in high-speed interconnection systems: analgorithm for prioritized access

The requirement to connect high-performance components of supercomputer systems has caused an increasing demand for connection-oriented, high-speed communication in a peer-to-peer environment. The importance of this type of communication is underscored by the advent of the high-performance parallel interface (HIPPI) standard, designed to support the commercial development of interconnection systems for this environment. For such interconnection systems, we present a connection management algorithm that supports priorities to provide preferential access for important classes of traffic, and that assures equitable access for all connections within the same priority class. At the same time, the algorithm utilizes the connection resources efficiently and assures low overhead at the nodes. We demonstrate the algorithm's applicability by outlining a centralized as well as a distributed implementation in an HIPPI-based interconnection system. Furthermore, we introduce an analytic priority model that can be used to evaluate an interconnection system's performance under the algorithm. Using this model, we analyze the efficacy of the nonpreemptive priority discipline and show the load/throughput behavior of a typical system     

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.     

On products of graphs and regular groups

A graphX is called a graphical regular representation (GRR) of a groupG if the automorphism group ofX is regular and isomorphic toG. Watkins and Nowitz have shown that the direct productG×H of two finite groupsG andH has aGRR if both factors have aGRR and if at least one factor is different from the cyclic group of order two. We give a new proof of this result, thereby removing the restriction to finite groups. We further show that the complementX′ of a finite or infinite graphX is prime with respect to cartesian multiplication ifX is composite and not one of six exceptional graphs.