The disconnection number of a graph |
| |
Authors: | Helma GladdinesMarcel van de Vel |
| |
Affiliation: | Faculty of Sciences (FEW), VU Amsterdam, The Netherlands |
| |
Abstract: | 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 Dn 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 Dn. 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 Dn are discussed.The algorithm of the main result has been implemented to construct the classes Dn for n?8, to estimate the size of D9, and to obtain information on certain subclasses such as non-planar graphs (n?9) and regular graphs (n?10). |
| |
Keywords: | 05C10 05C99 54F20 |
本文献已被 ScienceDirect 等数据库收录! |
|