𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with edge-preserving majority functions

✍ Scribed by Hans-Jürgen Bandelt

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
319 KB
Volume
103
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A majority function m is a ternary operation satisfying the identity m(u, U, u) = m(u, u, u) = m(u, u, u) = u. It is shown that a finite graph G admits an edge-preserving majority function on its vertex set if and only if G is an absolute retract of bipartite graphs. This parallels previous results on absolute retracts of topological spaces, ordered sets, and reflexive graphs, respectively.

📜 SIMILAR VOLUMES

Strict majority functions on graphs
Strict majority functions on graphs
✍ Henning, Michael A.; Hind, Hugh R. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB

An opinion function on a graph G = (V, E) is a function f : V → {-1, +1}. The vote of a vertex v is the sum of these function values over the closed neighborhood of v. A strict majority function on a graph G is an opinion function for which more than half of the vertices have a positive vote. The st

Splitting Off Edges within a Specified S
Splitting Off Edges within a Specified Subset Preserving the Edge-Connectivity of the Graph
✍ Jørgen Bang-Jensen; Tibor Jordán 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 141 KB

Splitting off a pair su sv of edges in a graph G means the operation that deletes su and sv and adds a new edge uv. Given a graph G = V + s E which is kedge-connected (k ≥ 2) between vertices of V and a specified subset R ⊆ V , first we consider the problem of finding a longest possible sequence of

Balanced graphs with edge density constr
Balanced graphs with edge density constraints
✍ John Sheehan 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 400 KB

## Abstract Suppose that __G__ is a finite simple graph with |__V__(__G__)| = 2__n__ (__n__ ≠ 3). a partition (__X,Y__) of __V__(__G__) is balanced if (i) |__X__| = |__Y__| = __n__, (ii) δ(__X__) ≥ 1, δ(__Y__) ≥ 1. Where δ(__X__) is the minimum degree of the induced subgraph 〈X〉 with vertex set

A note on graphs with diameter-preservin
A note on graphs with diameter-preserving spanning trees
✍ Fred Buckley; Martin Lewinter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 182 KB 👁 1 views

The distance between a pair of vertices u, u in a graph G is the length of a shortest path joining u and u. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree Tof G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs th