|
|||||
|
|
On 3-Edge-Connected Supereulerian Graphs |
|
| Authors: | Hong-Jian Lai Hao Li Yehong Shao Mingquan Zhan |
| Institution: | 1. Department of Mathematics, West Virginia University, Morgantown, WV, 26506, USA 2. Department of Mathematics, Ohio University Southern Campus, Ironton, OH, 45638, USA 3. Department of Mathematics, Millersville University, Millersville, PA, 17551, USA |
| Abstract: | The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d G (u) + d G (v) ≥ 9, then G has a spanning eulerian subgraph. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |