A bound on the total size of a cut cover |
| |
Authors: | André Kündgen |
| |
Institution: | a Department of Mathematics, California State University San Marcos, San Marcos, CA 92096, USA b Department of Mathematics, California State University San Marcos, San Marcos, CA 92096, USA |
| |
Abstract: | A cycle cover (cut cover) of a graph G is a collection of cycles (cuts) of G that covers every edge of G at least once. The total size of a cycle cover (cut cover) is the sum of the number of edges of the cycles (cuts) in the cover.We discuss several results for cycle covers and the corresponding results for cut covers. Our main result is that every connected graph on n vertices and e edges has a cut cover of total size at most 2e-n+1 with equality precisely when every block of the graph is an odd cycle or a complete graph (other than K4 or K8). This corresponds to the result of Fan J. Combin. Theory Ser. B 74 (1998) 353-367] that every graph without cut-edges has a cycle cover of total size at most e+n-1. |
| |
Keywords: | Cut Cycle Edge cover |
本文献已被 ScienceDirect 等数据库收录! |
|