The disconnection number of a graph

The disconnection number d(X) is the least number of points in a connected topological graph X such that removal of d(X) points will disconnect X (Nadler, 1993 [6]). Let D-n denote the set of all homeomorphism classes of topological graphs with disconnection number n. The main result characterizes the members of Dn+1 in terms of four possible operations on members of D-n. In addition, if X and Y are topological graphs and X is a subspace of Y with no endpoints, then d(X) <= d(Y) and Y obtains from X with exactly d(Y) - d(X) operations. Some upper and lower bounds on the size of D-n are discussed. The algorithm of the main result has been implemented to construct the classes D-n for n <= 8, to estimate the size of D-9, and to obtain information on certain subclasses such as non-planar graphs (n <= 9) and regular graphs (n <= 10). (C) 2010 Elsevier B.V. All rights reserved.