On minimum degree conditions for supereulerian graphs

Research output: Book/ReportReportOther research output

17 Downloads (Pure)

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.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente, Department of Applied Mathematics
Publication statusPublished - 1999

Publication series

Name
PublisherDepartment of Applied Mathematics, University of Twente
No.1507
ISSN (Print)0169-2690

Keywords

  • EWI-3327
  • MSC-05C45
  • MSC-05C35
  • IR-65695

Cite this

Broersma, H. J., & Xiong, L. (1999). On minimum degree conditions for supereulerian graphs. Enschede: University of Twente, Department of Applied Mathematics.
Broersma, Haitze J. ; Xiong, L. / On minimum degree conditions for supereulerian graphs. Enschede : University of Twente, Department of Applied Mathematics, 1999.
@book{1840d509b08146f78c3c8a8c73437a6c,
title = "On minimum degree conditions for supereulerian graphs",
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.",
keywords = "EWI-3327, MSC-05C45, MSC-05C35, IR-65695",
author = "Broersma, {Haitze J.} and L. Xiong",
note = "Imported from MEMORANDA",
year = "1999",
language = "Undefined",
publisher = "University of Twente, Department of Applied Mathematics",
number = "1507",

}

Broersma, HJ & Xiong, L 1999, On minimum degree conditions for supereulerian graphs. University of Twente, Department of Applied Mathematics, Enschede.

On minimum degree conditions for supereulerian graphs. / Broersma, Haitze J.; Xiong, L.

Enschede : University of Twente, Department of Applied Mathematics, 1999.

Research output: Book/ReportReportOther 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 -

Broersma HJ, Xiong L. On minimum degree conditions for supereulerian graphs. Enschede: University of Twente, Department of Applied Mathematics, 1999.