Vertex Bisection Minimization problem (VBMP) consists of partitioning a vertex set into two sets B and B′ where |B|=|V|/2 such that vertex width, VW, is minimized which is defined as the number of vertices in B which are adjacent to at least one vertex in B′. It is an NP-complete problem in general. VBMP has applications in fault tolerance and is related to the complexity of sending messages to processors in interconnection networks via vertex disjoint paths. In this paper, a memetic algorithm has been designed for this problem (MAVBMP) in which four construction heuristics have been proposed to generate the initial population. These heuristics are analyzed statistically and accordingly used in proportion to generate the initial population for MAVBMP. A new crossover type search operator has been proposed for recombination and a local improvement operator has also been developed. Extensive experiments have been conducted on several classes of graphs such as complete bipartite graphs, 2-dimensional ordinary meshes, 2-dimensional toroidal meshes, 3-dimensional toroidal meshes, complete split graph, join of hypercubes and Harwell-boeing graphs which are a subset of public domain Matrix Market library. Trends observed in the experimental results for some of the classes of graphs have led to conjectures for vertex width. © 2016 Elsevier Inc.