Let v(n) be the minimum number of voters with transitive preferences which are needed to generate any strong preference pattern (ties not allowed) on n candidates. Let k = [logn]. Then it is shown that v(n) ≤ n-k if n and k have different parity, and v(n) ≤ n-k+1 otherwise.
From a natural generalization to Z2 of the concept of congruence, it is possible to define a family of 2-regular digraphs that we call commutative-step networks. Particular examples of such digraphs are the cartesian product of two directed cycles, C1 x Ch, and the fixed-step network (or 2-step circulant digraph) DN,a,b. In this paper the theory of congruences in Z2 is applied to derive...
From two graphs G1 and G2 on N1 and N2 vertices respectively, the compound graph G1[G2] on N1N2 vertices is obtained by connecting in some way N2 copies of G1. We present in this paper methods of compounding that result in families of graphs with large number of vertices for given values...
This paper studies some diameter-related properties of the 3-step circulant digraphs with set of vertices V≡Z and steps (± a,b). More precisely, it concentrates upon maximizing their order N for any fixed value of their diameter k. In the proposed geometrical approach, each digraph is fully represented by a T-shape tile which tessellates periodically the plane. The study of these tiles leads to the optimal solutions.
Page 1