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 条
  • [21] On the domination number of a graph
    Pruchnewski, A
    DISCRETE MATHEMATICS, 2002, 251 (1-3) : 129 - 136
  • [22] On the toll number of a graph
    Dravec, Tanja
    DISCRETE APPLIED MATHEMATICS, 2022, 321 : 250 - 257
  • [23] The Alcuin Number of a Graph
    Csorba, Peter
    Hurkens, Cor A. J.
    Woeginger, Gerhard J.
    ALGORITHMS - ESA 2008, 2008, 5193 : 320 - 331
  • [24] The Steiner number of a graph
    Chartrand, G
    Zhang, P
    DISCRETE MATHEMATICS, 2002, 242 (1-3) : 41 - 54
  • [25] PRIME NUMBER GRAPH
    POMERANCE, C
    MATHEMATICS OF COMPUTATION, 1979, 33 (145) : 399 - 408
  • [26] THE BONDAGE NUMBER OF A GRAPH
    FINK, JF
    JACOBSON, MS
    KINCH, LF
    ROBERTS, J
    DISCRETE MATHEMATICS, 1990, 86 (1-3) : 47 - 57
  • [27] The Hoffman number of a graph
    Teranishi, Y
    DISCRETE MATHEMATICS, 2003, 260 (1-3) : 255 - 265
  • [28] The Binding Number of a Graph
    Taian
    数学研究与评论, 1991, (02) : 297 - 298
  • [29] THE SUBCHROMATIC NUMBER OF A GRAPH
    ALBERTSON, MO
    JAMISON, RE
    HEDETNIEMI, ST
    LOCKE, SC
    DISCRETE MATHEMATICS, 1989, 74 (1-2) : 33 - 49
  • [30] ON THE NUMBER OF CYCLES IN A GRAPH
    AlBdaiwi, Bader F.
    MATHEMATICA SLOVACA, 2018, 68 (01) : 1 - 10
12345