Paper Info
Title
Subgraph coverings and edge switchings
Abstract
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 ⌊ 2 n −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 Erdös, Goodman, and Pósa. References REFERENCES 1 J.A. Bondy Small cycle double covers of graphs G. Hahn G. Sabidussi R. Woodrow Cycles and Rays NATO ASI Ser. C 1990 Kluwer Academic Dordrecht 21 40 2 J.A. Bondy U.S.R. Murty Graph Theory with Application 1976 Macmillan & Co London 3 F.R.K. Chung On the coverings of graphs Discrete Math. 30 1980 89 93 4 A. Donald An upper bound for the path number of a graph J. Graph Theory 4 1980 189 201 5 P. Erdös A.W. Goodman L. Pósa The representation of graphs by set intersections Canad. J. Math. 18 1966 106 112 6 L. Lovász On covering of graphs P. Erdös G. Katona Theory of Graphs 1968 Academic Press New York 231 236 7 L. Pyber An Erdös–Gallai conjecture Combinatorica 5 1985 67 79 8 L. Pyber Covering the edges of a connected graph by paths J. Combin. Theory Ser. B 66 1996 152 159 9 L. Yan On Path Decompositions of Graphs 1998 Arizona State University
Year
DOI
Venue
2002
10.1006/jctb.2001.2063
J. Comb. Theory, Ser. B
Keywords
Field
DocType
subgraph covering,edge switchings,connected graph
Pseudoforest,Discrete mathematics,Combinatorics,Multigraph,Path (graph theory),k-vertex-connected graph,Cycle graph,Multiple edges,Mathematics,Path graph,Complement graph
Journal
Volume
Issue
ISSN
84
1
Journal of Combinatorial Theory, Series B
Citations 
PageRank 
References 
7
1.93
3
Authors
1
Name
Order
Citations
PageRank
Genghua Fan141265.22