کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
428499 686785 2015 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Tree-core and tree-coritivity of graphs
ترجمه فارسی عنوان
درخت و هسته و سازگاری درخت از نمودار
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• A new graph parameter, called tree-coritivity, is introduced.
• We show 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.
• We figure out the bounds of tree-coritivity of graphs.
• We obtain the exact value of tree-coritivities for some special classes of graphs.

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)ω(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⁎|ω(G−S⁎)−|S⁎|, where S⁎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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 115, Issue 10, October 2015, Pages 754–759
نویسندگان
, , , , ,