Tree-core and tree-coritivity of graphs

Tree-core and tree-coritivity of graphs

0.00 Avg rating0 Votes
Article ID: iaor201527221
Volume: 115
Issue: 10
Start Page Number: 754
End Page Number: 759
Publication Date: Oct 2015
Journal: Information Processing Letters
Authors: , , , ,
Keywords: trees
Abstract:

A new graph parameter, called tree-coritivity, is introduced in this paper. A decycling-cut is a vertex-cut whose removal results in an acyclic graph. Let ω(G) be the number of connected components of a graph G. The tree-coritivity of a graph G is the maximum value of ω(G-S*)-|S*|, where S* takes over all decycling-cuts of G. It is shown that this parameter can be used to measure the vulnerability of a graph. We prove that the problem of computing the tree-coritivity of a graph is NP-complete. Moreover, we figure out the bounds of tree-coritivity of graphs, give a way to compute the tree-coritivity of the join graph, and determine the exact value of tree-coritivities for some special classes of graphs.

Reviews

Required fields are marked *. Your email address will not be published.