Tree-core and tree-coritivity of graphs

doi:10.1016/j.ipl.2015.02.016

CORC > 北京大学 > 信息科学技术学院

	Tree-core and tree-coritivity of graphs
	Zhu, Enqiang ; Li, Zepeng ; Shao, Zehui ; Xu, Jin ; Liu, Chanjuan
刊名	INFORMATION PROCESSING LETTERS
	2015
关键词	Combinatorial problems Connectivity Tree-coritivity Tree-core NP-complete VERTEX CONNECTIVITY TOUGHNESS
DOI	10.1016/j.ipl.2015.02.016
英文摘要	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 omega(G) be the number of connected components of a graph G. The tree-coritivity of a graph G is the maximum value of omega(G - S) - vertical bar Svertical bar, 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. (C) 2015 Elsevier B.V. All rights reserved.; 973 projects [2013CB329601, 2013CB329602]; National Natural Science Foundation of China [60974112, 61309015, 30970960]; China Postdoctoral Science Foundation [2014M560851]; SCI(E); EI; ARTICLE; chanjuan.pkucs@gmail.com; 10; 754-759; 115
语种	中文
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/416091]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Zhu, Enqiang,Li, Zepeng,Shao, Zehui,et al. Tree-core and tree-coritivity of graphs[J]. INFORMATION PROCESSING LETTERS,2015.
APA	Zhu, Enqiang,Li, Zepeng,Shao, Zehui,Xu, Jin,&Liu, Chanjuan.(2015).Tree-core and tree-coritivity of graphs.INFORMATION PROCESSING LETTERS.
MLA	Zhu, Enqiang,et al."Tree-core and tree-coritivity of graphs".INFORMATION PROCESSING LETTERS (2015).