A characterization of extremal graphs without matching-cuts

P.S. Bonsma

Research output: Book/ReportReportProfessional

15 Downloads (Pure)

Abstract

A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|\geq \lceil 3(|V|-1)/2\rceil$, and constructed a large class of immune graphs attaining this lower bound for every value of $|V(G)|$, called ABC graphs. In this paper, we prove their conjecture that every immune graph that attains this lower bound is an ABC graph.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Number of pages40
ISBN (Print)0169-2690
Publication statusPublished - 2005

Publication series

NameMemorandum Afdeling TW
PublisherDepartment of Applied Mathematics, University of Twente
No.1769
ISSN (Print)0169-2690

Keywords

  • MSC-05C75
  • MSC-05C35
  • METIS-225440
  • IR-65953
  • EWI-3589

Cite this

Bonsma, P. S. (2005). A characterization of extremal graphs without matching-cuts. (Memorandum Afdeling TW; No. 1769). Enschede: University of Twente.
Bonsma, P.S. / A characterization of extremal graphs without matching-cuts. Enschede : University of Twente, 2005. 40 p. (Memorandum Afdeling TW; 1769).
@book{7c55cc1b5fde427e9f42e63b65bec338,
title = "A characterization of extremal graphs without matching-cuts",
abstract = "A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|\geq \lceil 3(|V|-1)/2\rceil$, and constructed a large class of immune graphs attaining this lower bound for every value of $|V(G)|$, called ABC graphs. In this paper, we prove their conjecture that every immune graph that attains this lower bound is an ABC graph.",
keywords = "MSC-05C75, MSC-05C35, METIS-225440, IR-65953, EWI-3589",
author = "P.S. Bonsma",
note = "Imported from MEMORANDA",
year = "2005",
language = "Undefined",
isbn = "0169-2690",
series = "Memorandum Afdeling TW",
publisher = "University of Twente",
number = "1769",
address = "Netherlands",

}

Bonsma, PS 2005, A characterization of extremal graphs without matching-cuts. Memorandum Afdeling TW, no. 1769, University of Twente, Enschede.

A characterization of extremal graphs without matching-cuts. / Bonsma, P.S.

Enschede : University of Twente, 2005. 40 p. (Memorandum Afdeling TW; No. 1769).

Research output: Book/ReportReportProfessional

TY - BOOK

T1 - A characterization of extremal graphs without matching-cuts

AU - Bonsma, P.S.

N1 - Imported from MEMORANDA

PY - 2005

Y1 - 2005

N2 - A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|\geq \lceil 3(|V|-1)/2\rceil$, and constructed a large class of immune graphs attaining this lower bound for every value of $|V(G)|$, called ABC graphs. In this paper, we prove their conjecture that every immune graph that attains this lower bound is an ABC graph.

AB - A graph is called (matching-)immune if it has no edge cut that is also a matching. Farley and Proskurowski proved that for all immune graphs $G=(V,E)$, $|E|\geq \lceil 3(|V|-1)/2\rceil$, and constructed a large class of immune graphs attaining this lower bound for every value of $|V(G)|$, called ABC graphs. In this paper, we prove their conjecture that every immune graph that attains this lower bound is an ABC graph.

KW - MSC-05C75

KW - MSC-05C35

KW - METIS-225440

KW - IR-65953

KW - EWI-3589

M3 - Report

SN - 0169-2690

T3 - Memorandum Afdeling TW

BT - A characterization of extremal graphs without matching-cuts

PB - University of Twente

CY - Enschede

ER -

Bonsma PS. A characterization of extremal graphs without matching-cuts. Enschede: University of Twente, 2005. 40 p. (Memorandum Afdeling TW; 1769).