Abstract

The linear node arrangement of a graph G on n nodes is the embedding of the nodes of the graph onto the line topology L in such a way that the sum of the distance between adjacent nodes in G is optimized. The cyclic node arrangement is the embedding of the nodes of G onto a cycle C in such a way that the optimization is preserved. In this paper we obtain general results to compute the cyclic and linear node arrangement of a class of Cartesian product graphs with C_k and P_k respectively, where C_k, k ≥2, is a cycle on k nodes and P_k is a path on k nodes and their conditional edge faulty graphs.

Keywords and Phrases

Embedding, optimal ordering, edge faulty graph.

A.M.S. subject classification

05C78, 05C85

.....