Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Fractional perfect b-matching polytopes I: General theory

Behrend, Roger E. 2013. Fractional perfect b-matching polytopes I: General theory. Linear Algebra and its Applications 439 (12) , pp. 3822-3858. 10.1016/j.laa.2013.10.001

[img]
Preview
PDF - Accepted Post-Print Version
Download (453kB) | Preview

Abstract

The fractional perfect b-matching polytope of an undirected graph G is the polytope of all assignments of nonnegative real numbers to the edges of G such that the sum of the numbers over all edges incident to any vertex v is a prescribed nonnegative number b_v. General theorems which provide conditions for nonemptiness, give a formula for the dimension, and characterize the vertices, edges and face lattices of such polytopes are obtained. Many of these results are expressed in terms of certain spanning subgraphs of G which are associated with subsets or elements of the polytope. For example, it is shown that an element u of the fractional perfect b-matching polytope of G is a vertex of the polytope if and only if each component of the graph of u either is acyclic or else contains exactly one cycle with that cycle having odd length, where the graph of u is defined to be the spanning subgraph of G whose edges are those at which u is positive.

Item Type: Article
Date Type: Publication
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Uncontrolled Keywords: graphs; polytope; perfect matching
Additional Information: Online publication date: 25 October 2013.
Publisher: Elsevier
ISSN: 0024-3795
Date of First Compliant Deposit: 30 March 2016
Last Modified: 04 Jun 2017 04:42
URI: http://orca.cf.ac.uk/id/eprint/43147

Citation Data

Cited 3 times in Google Scholar. View in Google Scholar

Cited 4 times in Scopus. View in Scopus. Powered By Scopus® Data

Cited 2 times in Web of Science. View in Web of Science.

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics