Score vectors of tournaments

A tournament T on any set X is a dyadic relation such that for any x, y ∈ X (a) (x, x) ? T and (b) if x ≠ y then (x, y) ∈ T iff (y, x) ? T. The score vector of T is the cardinal valued function defined by R(x) = |{y ∈ X : (x, y) ∈ T}|. We present theorems for infinite tournaments analogous to Landau's necessary and sufficient conditions that a vector be the score vector for some finite tournament. Included also is a new proof of Landau's theorem based on a simple application of the “marriage” theorem.     

On nonabelian composition factors of a finite prime spectrum minimal group

Assume that G is a primitive permutation group on a finite set X, x ∈ X, y ∈ X \ {x}, and G _x,y \(\underline \triangleleft \) G _x . P. Cameron raised the question about the validity of the equality G _x,y = 1 in this case. The author proved earlier that, if soc(G) is not a direct power of an exceptional group of Lie type, then G _x,y = 1. In the present paper, we prove that, if soc(G) is a direct power of an exceptional group of Lie type distinct from E ₆(q), ² E ₆(q), E ₇(q), and E ₈(q), then G _x,y = 1.     

On supercompact graphs

A graph G is called a supercompact graph if G is the intersection graph of some family ?? of subsets of a set X such that ?? satisfies the Helly property and for any x≠y in X, there exists S ∈ ?? with x ∈ S, y ? S. Various characterizations of supercompact graphs are given. It is shown that every clique-critical graph is supercompact. Furthermore, for any finite graph, H, there is at most a finite number of different supercompact graphs G such that H is the clique-graph of G.     

On the P4-structure of perfect graphs III. Partner decompositions

Vertices x and y in the same graph are called partners if there is a set S of three vertices such that both S ∪ {x} and S ∪ {y} induce a chordless path. If the vertices of G can be distributed into two disjoint classes in such a way that every two partners belong to the same class and that each class induces in G a perfect graph then G is perfect. This theorem generalizes two theorems that were proved before, one by Chvátal and Hoàng, and the other by Hoàng alone.     

Spectral properties of zeroth-order pseudodifferential operators

Let Q be a self-adjoint, classical, zeroth order pseudodifferential operator on a compact manifold X with a fixed smooth measure dx. We use microlocal techniques to study the spectrum and spectral family, {E_S}_{S∈$\text{R}$} as a bounded operator on L²(X, dx).Using theorems of Weyl (Rend. Circ. Mat. Palermo, 27 (1909), 373–392) and Kato (“Perturbation Theory for Linear Operators,” Springer-Verlag, 1976) on spectra of perturbed operators we observe that the essential spectrum and the absolutely continuous spectrum of Q are determined by a finite number of terms in the symbol expansion. In particular Spec_ESSQ = range(q(x, ξ)) where q is the principal symbol of Q. Turning the attention to the spectral family {E_S}_{S∈$\text{R}$}, it is shown that if $\text{dE}\text{ds}$ is considered as a distribution on $\text{R}$×X×X it is in fact a Lagrangian distribution near the set $\text{{σ=0}?}\text{T}{}^1\text{(}\text{R}\text{×X×X)}\text{0}$ where (s, x, y, σ, ξ,η) are coordinates on T¹($\text{R}$×X×X) induced by the coordinates (s, x, y) on $\text{R}$×X×X. This leads to an easy proof that$\text{?(Q)}$ is a pseudodifferential operator if ?∈C^∞($\text{R}$) and to some results on the microlocal character of E_s. Finally, a look at the wavefront set of $\text{dE}\text{ds}$ leads to a conjecture about the existence of absolutely continuous spectrum in terms of a condition on q(x, ξ).     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

Planar zero divisor graphs of partially ordered sets

We associate a graph G ^?(P) to a partially ordered set (poset, briefly) with the least element?0, as an undirected graph with vertex set P ^?=P?{0} and, for two distinct vertices x and y, x is adjacent to?y in?G ^?(P) if and only if {x,y} ^? ={0}, where, for a subset?S of?P, S ^? is the set of all elements x∈P with x≦s for all s∈S. We study some basic properties of?G ^?(P). Also, we completely investigate the planarity of?G ^?(P).     

Multivalued social choice functions and strategic manipulation with counterthreats

In this paper, we examine the manipulability properties of social decision rules which select a non-empty subset of the set of alternatives. Assuming that if an individual prefers x to y, then he prefers the outcome set {x, y} to {y}, and also {x} to {x, y}, we show that a wide class of scf's which allow ties even in pairwise choice violates one of the weakest notions of strategyproofness — a single individual can profitably misrepresent his preferences, even when he takes into account the possibility of countercoalitions. This class of scf's also violates exact consistency — no equilibrium situation gives the same outcome set as the ‘true profile’.     

Multiobjective programming and penalty functions

This paper generalizes the penalty function method of Zang-will for scalar problems to vector problems. The vector penalty function takes the form $$g(x,\lambda ) = f(x) + \lambda ^{ - 1} P(x)e,$$ wheree ?R ^m, with each component equal to unity;f:R ⁿ →R ^m, represents them objective functions {f ⁱ} defined onX \( \subseteq \) R ⁿ; λ ∈R ¹, λ>0;P:R ⁿ →R ¹ X \( \subseteq \) Z \( \subseteq \) R ⁿ,P(x)≦0, ∨x ∈R ⁿ,P(x) = 0 ?x ∈X. The paper studies properties of {E (Z, λ _r )} for a sequence of positive {λ _r } converging to 0 in relationship toE(X), whereE(Z, λ _r ) is the efficient set ofZ with respect tog(·, λ_r) andE(X) is the efficient set ofX with respect tof. It is seen that some of Zangwill's results do not hold for the vector problem. In addition, some new results are given.     

Fundamental Sets of Functions on Locally Compact Abelian Groups

Let G be a locally compact Abelian group, and let X be a compact set of G. Given a positive definite function ?: G × G → ? whose real part is continuous at neutral element of G, we research a necessary and sufficient setting for the linear span of the set {x ∈ X → ?(x ? y): y ∈ X} to be dense in C(X) in the topology of uniform convergence. The context treated that is abstract encompasses classical cases of the literature, while other examples are entirely new.     

Spectra of Extended Double Cover Graphs

The construction of the extended double cover was introduced by N. Alon [1] in 1986. For a simple graph G with vertex set V = {v ₁, v ₂, ..., v _n }, the extended double cover of G, denoted G ^*, is the bipartite graph with bipartition (X, Y) where X = {x ₁, x ₂, ..., x _n } and Y = {y ₁, y ₂, ..., y _n }, in which x _i and y _j are adjacent iff i = j or v _i and v _j are adjacent in G.In this paper we obtain formulas for the characteristic polynomial and the spectrum of G ^* in terms of the corresponding information of G. Three formulas are derived for the number of spanning trees in G ^* for a connected regular graph G. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the nth iterared double cover are also presented.     

Behaviour of doubly connected minimal surfaces at the edges of the support surface

This paper is the second part of our investigations on doubly connected minimal surfaces which are stationary in a boundary configuration (G, S) (\Gamma, S) in \Bbb R ³ \Bbb R ^3 . The support surface S is a vertical cylinder above a simple closed polygon P(S) P(S) in the x,y-plane. The surrounding Jordan curve G \Gamma is chosen as a generalized graph above its convex projection curve P(G) P(\Gamma) . In [23] we have proved the existence of nonparametric minimal surfaces X of annulus type spanning such boundary configurations. We study the behaviour of these minimal surfaces at the edges of the support surface S. In particular we discuss the phenomenon of edge-creeping, i. e. the fact that the free trace of X may attach to an edge of S in a full interval. We prove that a solution X cuts any intruding edge of S perpendicularly. On the other hand, we derive a condition which forces X to exhibit the edge-creeping behaviour. Depending on the symmetries of (G, S) (\Gamma, S) we give bounds on the number of edges where edge-creeping occurs. Let (x,y,Z (x,y)) (x,y,\hbox {Z} (x,y)) for (x,y) ? G (x,y)\in G be the nonparametric representation of X. Then at every vertex Q of P(S) P(S) the radial limits of Z from all directions in G exist.     

Internal coverings of sets by asymmetric relations

A non-empty finite collection $\text{C}$ of non-empty finite sets is internally coverable iff there exists an asymmetric binary relation P on ∪{C; C ∈ $\text{C}$} such that C ? {x: yPx for some y ∈ C} for all C ? $\text{C}$. Necessary and sufficient conditions for internal coverability in terms of “bad sets” are specified for all $\text{C}$ with |$\text{C}$| ≤ 5. Relationships between internal coverability and aspects of tournaments are discussed.     

Modes of convergence of Markov chain transition probabilities

Suppose {Pⁿ(x, A)} denotes the transition law of a general state space Markov chain {X_n}. We find conditions under which weak convergence of {X_n} to a random variable X with law L (essentially defined by ∝ Pⁿ(x, dy) g(y) → ∝ L(dy) g(y) for bounded continuous g) implies that {X_n} tends to X in total variation (in the sense that $\text{∥ P}{}^{\mathrm{n}}\text{(x,}{}^{\mathrm{.}}\text{) ? L ∥ → 0)}$, which then shows that L is an invariant measure for {X_n}. The conditions we find involve some irreducibility assumptions on {X_n} and some continuity conditions on the one-step transition law {P(x, A)}.     

Complexity of representation of graphs by set systems

Let $\text{F}$ be a family of subsets of S and let G be a graph with vertex set $\text{V={x}{}_{\mathrm{A}}\text{|A ∈}\text{F}\text{}}$ such that: (x_A, x_B) is an edge iff $\text{A?B≠}\text{0}\text{/}$. The family $\text{F}$ is called a set representation of the graph G.It is proved that the problem of finding minimum k such that G can be represented by a family of sets of cardinality at most k is NP-complete. Moreover, it is NP-complete to decide whether a graph can be represented by a family of distinct 3-element sets.The set representations of random graphs are also considered.     

Solving exponential diophantine equations using lattice Basis Reduction Algorithms

Let S be the set of all positive integers with prime divisors from a fixed finite set of primes. Algorithms are given for solving the diophantine inequality 0< x − y < y^δ in x, y ∈ S for fixed δ ∈ (0, 1), and for the diophantine equation x + y = z in x, y, z ∈ S. The method is based on multi-dimensional diophantine approximation, in the real and p-adic case, respectively. The main computational tool is the L³-Basis Reduction Algorithm. Elaborate examples are presented.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.