Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648732 | Discrete Mathematics | 2010 | 6 Pages |
Abstract
Given two nonnegative integers ss and tt, a graph GG is (s,t)(s,t)-supereulerian if for any disjoint sets X,Y⊂E(G)X,Y⊂E(G) with |X|≤s|X|≤s and |Y|≤t|Y|≤t, there is a spanning eulerian subgraph HH of GG that contains XX and avoids YY. We prove that if GG is connected and locally kk-edge-connected, then GG is (s,t)(s,t)-supereulerian, for any pair of nonnegative integers ss and tt with s+t≤k−1s+t≤k−1. We further show that if s+t≤ks+t≤k and GG is a connected, locally kk-edge-connected graph, then for any disjoint sets X,Y⊂E(G)X,Y⊂E(G) with |X|≤s|X|≤s and |Y≤t|Y≤t, there is a spanning eulerian subgraph HH that contains XX and avoids YY, if and only if G−YG−Y is not contractible to K2K2 or to K2,lK2,l with ll odd.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Lan Lei, Xiaomin Li, Bin Wang, Hong-Jian Lai,