Abstract
| Original language | Undefined |
|---|---|
| Place of Publication | Enschede |
| Publisher | University of Twente, Department of Applied Mathematics |
| Publication status | Published - 1999 |
Publication series
| Name | |
|---|---|
| Publisher | Department of Applied Mathematics, University of Twente |
| No. | 1507 |
| ISSN (Print) | 0169-2690 |
Keywords
- EWI-3327
- MSC-05C45
- MSC-05C35
- IR-65695
Cite this
}
On minimum degree conditions for supereulerian graphs. / Broersma, Haitze J.; Xiong, L.
Enschede : University of Twente, Department of Applied Mathematics, 1999.Research output: Book/Report › Report › Other research output
TY - BOOK
T1 - On minimum degree conditions for supereulerian graphs
AU - Broersma, Haitze J.
AU - Xiong, L.
N1 - Imported from MEMORANDA
PY - 1999
Y1 - 1999
N2 - 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.
AB - 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.
KW - EWI-3327
KW - MSC-05C45
KW - MSC-05C35
KW - IR-65695
M3 - Report
BT - On minimum degree conditions for supereulerian graphs
PB - University of Twente, Department of Applied Mathematics
CY - Enschede
ER -