Parity Subgraph, Shortest Cycle Cover, and Postman Tour
SIAM Journal on Discrete Mathematics1993Vol. 6(3), pp. 428–431
Abstract
Let $G = ( V,E )$ be a simple graph such that the number of odd vertices of G is $| V_0 |$ and the minimum odd degree is $\delta _0 $. This paper proves that the number of edges in a smallest parity subgraph of G is at most $| V | - {\text{Min}} \{ \delta _{0} , | V | - | V_0 | /2 \}$. Consequently, some results about the shortest cycle cover problem due to Itai and Rodeh, Fan, Zhang, Raspaud, Zhao are generalized. If G is a 2-edge-connected simple graph such that either G admits a nowhere-zero 4-flow or G contains no subdivision of the Petersen graph, then the total length of a shortest cycle cover of G is at most $| E | + | V | - {\text{Min}} \{ \delta _{0} , | V | - | V_0 |/2 \}$.
Related Papers
- → A note on the neighbor sum distinguishing total coloring of planar graphs(2016)12 cited
- → Maximum number of colorings of (2k, k2)‐graphs(2007)9 cited
- → Upper bounds on the signed edge domination number of a graph(2020)3 cited
- → AVD-total-colouring of complete equipartite graphs(2015)3 cited
- Number of colorings of r-partite Turan graphs(2010)