Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

On minimum degree conditions for supereulerian graphs

Share/Save/Bookmark

Broersma, H.J. and Xiong, L. (1999) On minimum degree conditions for supereulerian graphs. [Report]

[img]
Preview
PDF
137Kb
Abstract:
A graph is called supereulerian if it has a spanning closed trail. Let $G$ be a 2-edge-connected graph of order $n$ such that each minimal edge cut $E \subseteq E (G)$ with $|E| \le 3$ satisfies the property that each component of $G-E$ has order at least $(n-2)/5$. We prove that either $G$ is supereulerian or $G$ belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree $\delta\ge 4$: If $G$ is a 2-edge-connected graph of order $n$ with $\delta (G)\ge 4$ such that for every edge $xy\in E (G)$ , we have $\max \{d(x),d(y)\} \ge (n-7)/5$, then either $G$ is supereulerian or $G$ belongs to one of two classes of exceptional graphs. We show that the condition $\delta(G)\ge 4$ cannot be relaxed.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65695
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page