Abstract
Isoperimetric Number of the Cartesian Product of Graphs and Paths
by: M. Cemil Azizoglu and Omer Egecioglu
Abstract:
We prove that the isoperimetric number of P_k x G_k, the Cartesian product ofthe path P_k and a connected graph with k vertices, is equal to theisoperimetric number of P_k itself. At the same time we construct an infinitefamily of graphs that shows that this is not true for P_k x G where G has morethan k vertices, even if G is a tree.
Keywords:
Isoperimetric number, bisection width, path, array, Cartesianproduct graph.
Date:
May 1998
Document: 1998-15
