Behrend, Roger E.  ORCID: https://orcid.org/0000-0002-6143-7439
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
|
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: | 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: | 16 May 2023 16:05 |
| URI: | https://orca.cardiff.ac.uk/id/eprint/43147 |
Citation Data
Cited 8 times in Scopus. View in Scopus. Powered By Scopus® Data
Actions (repository staff only)
 |
Edit Item |
Dimensions
Dimensions