𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Metric characterization of parity graphs

✍ Scribed by Hans-Jürgen Bandelt; Henry Martyn Mulder

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
636 KB
Volume
91
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Metric characterizations of proper inter
Metric characterizations of proper interval graphs and tree-clique graphs
✍ Gutierrez, M.; Oubi�a, L. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 2 views

A connected graph G is a tree-clique graph if there exists a spanning tree T (a compatible tree) such that every clique of G is a subtree of T. When Tis a path the connected graph G is a proper interval graph which is usually defined as intersection graph of a family of closed intervals of the real

Minimum 0-Extensions of Graph Metrics
Minimum 0-Extensions of Graph Metrics
✍ Alexander V. Karzanov 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 510 KB

Let H = (T, U ) be a connected graph, V ⊇ T a set, and c a non-negative function on the unordered pairs of elements of V . In the minimum 0-extension problem ( \* ), one is asked to minimize the inner product c • m over all metrics m on V such that (i) m coincides with the distance function of H wit

Metric ends, fibers and automorphisms of
Metric ends, fibers and automorphisms of graphs
✍ Bernhard Krön; Rögnvaldur G. Möller 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

## Abstract Several results on the action of graph automorphisms on ends and fibers are generalized for the case of metric ends. This includes results on the action of the automorphisms on the end space, directions of automorphisms, double rays which are invariant under a power of an automorphism a

Cartesian Products of Graphs and Metric
Cartesian Products of Graphs and Metric Spaces
✍ S. Avgustinovich; D. Fon-Der-Flaass 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We prove uniqueness of decomposition of a finite metric space into a product of metric spaces for a wide class of product operations. In particular, this gives the positive answer to the long-standing question of S. Ulam: 'If U × U V × V with U , V compact metric spaces, will then U and V be isometr

Special parity of perfect matchings in b
Special parity of perfect matchings in bipartite graphs
✍ Ron Aharoni; Rachel Manber; Bronislaw Wajnryb 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 527 KB

Let G be a bipartite graph in which every edge belongs to some perfect matching, and let D be a subset of its edge set. It is shown that M fl D has the same parity for every perfect matching M if and only if D is a cut, and equivalently if and only. if (G, D) is a balanced signed-graph. This gives n

The Largest Parity Demigenus of a Simple
The Largest Parity Demigenus of a Simple Graph
✍ Thomas Zaslavsky 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 421 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according as its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is Euler characteristic) over all surfaces S in which 1 can be parity embedded. We calcul