The disconnection number of a graph

作者：Gladdines Helma; van de Vel Marcel^*

来源：Topology and Its Applications, 2011, 158(3): 424-431.

DOI：10.1016/j.topol.2010.11.019

• Disconnection number
• Endpoint
• Graph with multiple lines and loops
• Local degree
• Planar graph
• Simple graph
• Topological graph
• Tree

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 D(n+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).

• 出版日期2011-2-15