The disconnection number of a graph

被引：2
|
作者：
Gladdines, Helma [1 ]
van de Vel, Marcel [1 ]
机构：
[1] Vrije Univ Amsterdam, Fac Sci FEW, Amsterdam, Netherlands
来源：
TOPOLOGY AND ITS APPLICATIONS | 2011年 / 158卷 / 03期
关键词：
Disconnection number; Endpoint; Graph with multiple lines and loops; Local degree; Planar graph; Simple graph; Topological graph; Tree;
D O I：
10.1016/j.topol.2010.11.019
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：424 / 431
页数：8
相关论文
共 50 条
  • [31] The resolving number of a graph
    1600, Discrete Mathematics and Theoretical Computer Science (15):
  • [32] On the bondage number of a graph
    Wang, YL
    DISCRETE MATHEMATICS, 1996, 159 (1-3) : 291 - 294
  • [33] The convexity number of a graph
    Chartrand, G
    Wall, CE
    Zhang, P
    GRAPHS AND COMBINATORICS, 2002, 18 (02) : 209 - 217
  • [34] On the intersection number of a graph
    Marenich, E. E.
    Bolshakova, N. S.
    DISCRETE MATHEMATICS AND APPLICATIONS, 2007, 17 (06): : 607 - 617
  • [35] Uniform Number of a Graph
    Elakkiya, M.
    Abhishek, Kumar
    IRANIAN JOURNAL OF MATHEMATICAL SCIENCES AND INFORMATICS, 2020, 15 (02): : 77 - 99
  • [36] Domsaturation number of a graph
    Arumugam, S
    Kala, R
    INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2002, 33 (11): : 1671 - 1676
  • [37] On the hull number of a graph
    Chartrand, G
    Harary, F
    Zhang, P
    ARS COMBINATORIA, 2000, 57 : 129 - 138
  • [38] The number of walks in a graph
    Dress, A
    Gutman, I
    APPLIED MATHEMATICS LETTERS, 2003, 16 (05) : 797 - 801
  • [39] THE BASIS NUMBER OF A GRAPH
    SCHMEICHEL, EF
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 30 (02) : 123 - 129
  • [40] On the Grundy Number of a Graph
    Havet, Frederic
    Sampaio, Leonardo
    PARAMETERIZED AND EXACT COMPUTATION, 2010, 6478 : 170 - 179
12345