Connectivity of the graph induced by contractible edges of a k-tree

被引:0
|
作者
Qin, Chengfu [1 ]
Guo, Litao [2 ]
Huang, Lexian [1 ]
机构
[1] Nanning Normal Univ, Sch Math & Stat, Nanning 530023, Guangxi, Peoples R China
[2] Xiamen Univ Technol, Sch Appl Math, Xiamen 361024, Fujian, Peoples R China
关键词
k-tree; Edges; Induced graph; Connectivity; ALGORITHMS;
D O I
10.1016/j.amc.2019.01.051
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
A k-tree is a Kk+1 or a graph on at least k + 2 vertices obtained from a smaller k-tree by adding one vertex and joining it to the vertices of a k-clique. Let G be a k-connected graph, and let e be an edge of G. The edge e is said to be contractible if the graph obtained from G by contracting e is again a k-connected graph, otherwise it is said to be non-contractible. Let G be a k-tree, and let G(c) = (V(G), E-C(G)), where E-C(G) denotes the set of all contractible edges of G. In this paper, we prove that kappa(G(c)) - delta(G(c)). Further, G(c) is super connected, whenever 3 <= delta(G(c)) < k. (C) 2019 Elsevier Inc. All rights reserved.
引用
收藏
页码:1 / 6
页数:6
相关论文
共 50 条
  • [21] Document Clustering with K-tree
    De Vries, Christopher M.
    Geva, Shlomo
    ADVANCES IN FOCUSED RETRIEVAL, 2009, 5631 : 420 - 431
  • [22] The Extended k-tree Algorithm
    Minder, Lorenz
    Sinclair, Alistair
    JOURNAL OF CRYPTOLOGY, 2012, 25 (02) : 349 - 382
  • [23] ON THE SPANNING K-TREE PROBLEM
    CAI, LZ
    MAFFRAY, F
    DISCRETE APPLIED MATHEMATICS, 1993, 44 (1-3) : 139 - 156
  • [24] The bandwidth of the complement of a k-tree
    Jinjiang Y.
    Yixun L.
    Applied Mathematics-A Journal of Chinese Universities, 1998, 13 (4) : 451 - 454
  • [25] The Extended k-tree Algorithm
    Lorenz Minder
    Alistair Sinclair
    Journal of Cryptology, 2012, 25 : 349 - 382
  • [26] Random indexing K-tree
    De Vries, Christopher M.
    De Vine, Lance
    Geva, Shlomo
    ADCS 2009 - Proceedings of the Fourteenth Australasian Document Computing Symposium, 2009, : 43 - 50
  • [27] ALGORITHMS FOR A CORE AND K-TREE CORE OF A TREE
    PENG, ST
    STEPHENS, AB
    YESHA, Y
    JOURNAL OF ALGORITHMS, 1993, 15 (01) : 143 - 159
  • [28] On k-tree Containment Graphs of Paths in a Tree
    Liliana Alcón
    Noemí Gudiño
    Marisa Gutierrez
    Order, 2021, 38 : 229 - 244
  • [29] A local condition for k-contractible edges
    Ando, Kiyoshi
    DISCRETE MATHEMATICS, 2019, 342 (12)
  • [30] Edges not contained in triangles and the distribution of contractible edges in a 4-connected graph
    Ando, Kiyoshi
    Egawa, Yoshimi
    DISCRETE MATHEMATICS, 2008, 308 (16) : 3449 - 3460