Subgraph coverings and edge switchings

doi:10.1006/jctb.2001.2063

CSpace

	Subgraph coverings and edge switchings
	Fan, GH
	2002
发表期刊	JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN	0095-8956
卷号	84 期号:1 页码:54-83
摘要	By using the so-defined circuit/path transformations together with an edge-switching method, the following conjectures are proved in this paper. (i) The edges of a connected graph on n vertices can be covered by at most [n/2] paths, which was conjectured by Chung. (ii) The edges of a 2-connected graph on n vertices can be covered by at most [2n-1/3] circuits, which was conjectured by Bondy. An immediate consequence of (ii) is a theorem of Pyber that the edges of a graph on n vertices can be covered by at most n-1 edges and circuits, which was conjectured by Erdos, Goodman, and Posa. (C) 2001 Elsevier Science.
DOI	10.1006/jctb.2001.2063
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000173623200003
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/17559
专题	中国科学院数学与系统科学研究院
通讯作者	Fan, GH
作者单位	Chinese Acad Sci, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Fan, GH. Subgraph coverings and edge switchings[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B,2002,84(1):54-83.
APA	Fan, GH.(2002).Subgraph coverings and edge switchings.JOURNAL OF COMBINATORIAL THEORY SERIES B,84(1),54-83.
MLA	Fan, GH."Subgraph coverings and edge switchings".JOURNAL OF COMBINATORIAL THEORY SERIES B 84.1(2002):54-83.