𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Capacities of graphs and 2-matchings

✍ Scribed by G. Greco

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
385 KB
Volume
186
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is symmetric with respect to a functional Fc(P) defined on the set of all the probability distributions on its vertex set if the distribution P* maximizing Fa(P) is uniform on V(G). We show that the class of graphs which are symmetric for the functional appearing in the capacity formula of Cohen et al. (1968) andGargano et al. (1993) coincides with the graphs admitting a 2-matching in the sense of Tutte (1947). This has an interesting implication tbr families of qualitatively independent partitions (in the sense of Rfnyi).

πŸ“œ SIMILAR VOLUMES

Collapsible graphs and matchings
Collapsible graphs and matchings
✍ Zhi-Hong Chen; Hong-Jian Lai πŸ“‚ Article πŸ“… 1993 πŸ› John Wiley and Sons 🌐 English βš– 286 KB

## Abstract A graph __G__ is __collapsible__ if for every even subset __R__ βŠ† __V__(__G__), there is a spanning connected subgraph of __G__ whose set of odd degree vertices is __R__. A graph is __reduced__ if it does not have nontrivial collapsible subgraphs. Collapsible and reduced graphs are defi

Disjoint matchings of graphs
Disjoint matchings of graphs
✍ Kenneth Lebensold πŸ“‚ Article πŸ“… 1977 πŸ› Elsevier Science 🌐 English βš– 250 KB
Matchings and walks in graphs
Matchings and walks in graphs
✍ C. D. Godsil πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 527 KB

## Abstract The matching polynomial Ξ±(__G, x__) of a graph __G__ is a form of the generating function for the number of sets of __k__ independent edges of __G__. in this paper we show that if __G__ is a graph with vertex __v__ then there is a tree __T__ with vertex __w__ such that \documentclass{ar