Article ID Journal Published Year Pages File Type
4648732 Discrete Mathematics 2010 6 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,