Extensions of barrier sets to nonzero roots of the matching polynomial

Document Type

Article

Publication Date

1-1-2010

Abstract

In matching theory, barrier sets (also known as Tutte sets) have been studied extensively due to their connection to maximum matchings in a graph. For a root theta of the matching polynomial, we define theta-barrier and theta-extreme sets. We prove a generalized Berge-Tutte formula and give a characterization for the set of all theta-special vertices in a graph. (C) 2010 Elsevier B.V. All rights reserved.

Keywords

Matching polynomial, Gallai-Edmonds decomposition, Barrier sets, Extreme sets

Publication Title

Discrete Mathematics

Volume

310

Issue

24

Publisher

Elsevier

Publisher Location

PO BOX 211, 1000 AE AMSTERDAM, NETHERLANDS

This document is currently not available here.

Share

COinS