𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimal complete matchings and negative cycles

✍ Scribed by R. L. Tobin

Publisher
John Wiley and Sons
Year
1975
Tongue
English
Weight
627 KB
Volume
5
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Conditions are developed which relate the existence of negative and nonpositive simple cycles in an undirected network to minimal complete matchings on a derived network. These conditions are then used to develop a test to determine whether or not an undirected network contains nonpositive simple cycles. Also, it is shown that, in certain cases, the solution to the matching problem gives information about the location of the nonpositive cycles.

πŸ“œ SIMILAR VOLUMES

Exact arborescences, matchings and cycle
Exact arborescences, matchings and cycles
✍ Francisco Barahona; William R Pulleyblank πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 531 KB
Bonferroni Inequalities and Negative Cyc
Bonferroni Inequalities and Negative Cycles in Large Complete Signed Graphs
✍ Dragoş Popescu; Ioan Tomescu πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 213 KB

In this paper the problem of characterizing extremal graphs K n relatively to the number of negative p -cycles , when the number of negative edges is fixed , is solved for large n . This number can be expressed as an alternating sum for which the Bonferroni inequalities hold . Finally , the asympto

Cycles containing matchings and pairwise
Cycles containing matchings and pairwise compatible euler tours
✍ Bill Jackson; Nicholas C. Wormald πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 535 KB

## Abstract Let __M__ be a matching in a graph __G__ such that __d__(x) + __d__(y) β‰₯ |__G__| for all pairs of independent vertices x and y of G that are incident with __M.__ We determine a necessary and sufficient condition for __M__ to be contained in a cycle of __G.__ This extends results of HΓ€gg

On large matchings and cycles in sparse
On large matchings and cycles in sparse random graphs
✍ A.M Frieze πŸ“‚ Article πŸ“… 1986 πŸ› Elsevier Science 🌐 English βš– 666 KB

Let k be a fixed positive integer. A graph H has property Mk if it contains [Β½k] edge disjoint hamilton cycles plus a further edge disjoint matching which leaves at most one vertex isolated, if k is odd. Let p = c/n, where c is a large enough constant. We show that G,,p a.s. contains a vertex induce