𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Strict majority functions on graphs

✍ Scribed by Henning, Michael A.; Hind, Hugh R.

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
212 KB
Volume
28
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 strict majority number of G is the minimum sum of the values in a strict majority function of G. We prove the conjecture of Cockayne and Mynhardt (Ars. Combin. 43 (1996), 235-245) that every tree has strict majority number at most 2. We also prove that every graph has strict majority number at most 4. Both bounds are sharp.

πŸ“œ SIMILAR VOLUMES

Graphs with edge-preserving majority fun
Graphs with edge-preserving majority functions
✍ Hans-JΓΌrgen Bandelt πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 319 KB

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

Majority-vote on directed ErdΕ‘s–RΓ©nyi ra
Majority-vote on directed ErdΕ‘s–RΓ©nyi random graphs
✍ F.W.S. Lima; A.O. Sousa; M.A. Sumuor πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 551 KB

Through Monte Carlo Simulation, the well-known majority-vote model has been studied with noise on directed random graphs. In order to characterize completely the observed order-disorder phase transition, the critical noise parameter q c , as well as the critical exponents Ξ²/Ξ½, Ξ³ /Ξ½ and 1/Ξ½ have been

Strict and Mixed Topologies on Function
Strict and Mixed Topologies on Function Spaces
✍ Angeles Prieto πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 257 KB

## Abstract In this paper we prove that the strict topology on spaces of continuous and holomorphic functions on a BANACH space can be considered a mixed topology. Using this fact, we obtain new results about the strict topology, as an application of the general properties of mixed topologies.

Bounded color functions on graphs
Bounded color functions on graphs
✍ D. W. Matula πŸ“‚ Article πŸ“… 1972 πŸ› John Wiley and Sons 🌐 English βš– 753 KB