Lexicographic Product and Isoperimetric Number

The isoperimetric number of a graph , denoted by , was introduced by Mohar (1987). A graph and a subset of its vertices are given, and let denote the edge boundary of , the set of edges which connects vertices in to vertices not in . The isoperimetric number of is defined as . In this paper, some results about the isoperimetric number of graphs obtained by graph operations are given. 1. Introduction Given a graph and a subset of its vertices, let denote the edge boundary of that is, the set of edges which connects vertices in with vertices not in . The isoperimetric number is defined as Clearly, can be defined in a more symmetric form by where the minimum runs over all partitions of into nonempty subsets and , and are the edges between and . As examples of isoperimetric numbers, we consider the following.(i)The isoperimetric number of the complete graph with vertices is .(ii)The isoperimetric number of the cycle with vertices is .(iii)The isoperimetric number of the path with vertices is .(iv)The isoperimetric number of the complete bipartite graph with vertices is It can be briefly shown as . The isoperimetric number is also closely related to the notion of bisection width, , of a graph . This is the minimum number of edges that must be removed from in order to split into two equal-sized (within one if the number of vertices in is odd) subsets: where . If known, one can use the isoperimetric number of a graph to establish a lower bound for its bisection width using the fact that See [1]. The importance of lies in various interesting interpretations of this number by Mohar as follows [2].(a)From (2), it is evident that, in trying to determine , we have to find a small edge-cut separating as large a subset (assume ) as possible from the remaining larger part . So, it is evident that can serve as measure of connectivity of graphs. It seems that there might be possible applications in problems concerning connected networks,and the ways to “destroy” them are by removing a large portion of the network by cutting only a few edges.(b)The problem of the partitioning into two equally sized subsets (to within one element), in such a way that the number of the edges in the cut is minimal, is known as the bisectionwidth problem. It is important in VLSI design and some other practical applications. Clearly, it is related to isoperimetric number. Theorem 1 (see [2]). Some of the theorems that Mohar stated are given below.(a) if and only if is disconnected.(b)If is k-edge-connected then .(c)If is the minimal degree of vertices in then .(d)If is an edge of and then