The domination and competition graphs of a tournament

Vertices x and y dominate a tournament T if for all vertices z ≠ x, y, either x beats z or y beats z. Let dom(T) be the graph on the vertices of T with edges between pairs of vertices that dominate T. We show that dom(T) is either an odd cycle with possible pendant vertices or a forest of caterpillars. While this is not a characterization, it does lead to considerable information about dom(T). Since dom(T) is the complement of the competition graph of the tournament formed by reversing the arcs of T, complementary results are obtained for the competition graph of a tournament. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 103–110, 1998     

Domination Graphs with Nontrivial Components

 A tournament is an oriented complete graph. Vertices x and y dominate a tournament T if for all vertices z≠x,y, either (x,z) or (y,z) are arcs in T (possibly both). The domination graph of a tournament T is the graph on the vertex set of T containing edge {x,y} if and only if x and y dominate T. In this paper we determine which graphs containing no isolated vertices are domination graphs of tournaments. Received: May 20, 1998 Final version received: May 26, 1999     

Distributive equations of implications based on nilpotent triangular norms

In this paper, we explore the distributive equations of implications, both independently and along with other equations. In detail, we consider three classes of equations. (1) By means of the section of I, we give out the sufficient and necessary conditions of solutions for the distributive equation of implication I(x, T(y, z)) = T(I(x, y), (x, z)) based on a nilpotent triangular norm T and an unknown function I, which indicates that there are no continuous solutions satisfying the boundary conditions of implications. Under the assumptions that I is continuous except the vertical section I(0, y), y ∈ [0, 1), we get its complete characterizations. (2) We prove that there are no solutions for the functional equations I(x, T(y, z)) = T(I(x, y), I(x, z)), I(x, I(y, z)) = I(T(x, y), z). (3) We obtain the sufficient and necessary conditions on T and I to be solutions of the functional equations I(x, T(y, z)) = T(I(x, y), I(x, z)), I(x, y) = I(N(y), N(x)).     

Max-min of polynomials and exponential diophantine equations

In this paper we study the maximum-minimum value of polynomials over the integer ring Z. In particular, we prove the following: Let F(x,y) be a polynomial over Z. Then, maxx∈Z(T)miny∈Z|F(x,y)|=o(T1/2) as T→∞ if and only if there is a positive integer B such that maxx∈Zminy∈Z|F(x,y)|?B. We then apply these results to exponential diophantine equations and obtain that: Let f(x,y), g(x,y) and G(x,y) be polynomials over Q, G(x,y)∈(Q[x,y]−Q[x])∪Q, and b a positive integer. For every α in Z, there is a y in Z such that f(α,y)+g(α,y)bG(α,y)=0 if and only if for every integer α there exists an h(x)∈Q[x] such that f(x,h(x))+g(x,h(x))bG(x,h(x))≡0, and h(α)∈Z.     

Tournois infinis et critiques

Given a tournament T=(V,A), a subset X of V is an interval of T provided that for every a,b∈X and x∈V?X, (a,x)∈A if and only if (b,x)∈A. For example, ?, {x} (x∈V) and V are intervals of T, called trivial intervals. A tournament all the intervals of which are trivial is called indecomposable; otherwise, it is decomposable. An indecomposable tournament T=(V,A) is then said to be critical if for each x∈V, T(V?{x}) is decomposable and if there are x≠y∈V such that T(V?{x,y}) is indecomposable. We introduce the operation of expansion which allows us to describe a process of construction of critical and infinite tournaments. It follows that, for every critical and infinite tournament T=(V,A), there are x≠y∈V such that T and T(V?{x,y}) are isomorphic. To cite this article: I. Boudabbous, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

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.     

Power-series unification and reversion

In analysis, it is sometimes necessary to unite a pair of power series into a single power series. If x = x(z) = Σ_ja_jz^j and y = y(z) = Σ_jb_jz^j are given power series, then by eliminating the common parameter z, the power-series unification is obtained: y = y(x) = Σ_kc_kx^k, where the coefficients c_k are to be determined in terms of the given power-series coefficients a_j and b_j. In a special case that y = z, the power-series reversion is obtained: z = z(x) = Σ_kd_kx^k, where the coefficients d_k are to be expressed in terms of the original power-series coefficients a_j. In this paper, explicit and recurrent formulas for the desired coefficients are derived. A simple technique of matrix formulation is developed for simplicity of computation. Finally, a complete computer program with a typical example is presented.     

Boolean distance for graphs

The boolean distance between two points x and y of a connected graph G is defined as the set of all points on all paths joining x and y in G (Ø if x = y). It is determined in terms of the block-cutpoint graph of G, and shown to satisfy the triangle inequality b(x,y)? b(x, z)∪b(z,y). We denote by B(G) the collection of distinct boolean distances of G and by M(G) the multiset of the distances together with the number of occurrences of each of them. Then $\text{B(G)}\text{= 1+(}{}^{\mathrm{b+1}}{}_2\text{)}$ where b is the number of blocks of G. A combinatorial characterization is given for B(T) where T is a tree. Finally, G is reconstructible from M(G) if and only if every block of G is a line or a triangle.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

Recurrent points and non-wandering points of graph maps

Let G be a graph and f:G→G be a continuous map. Denote by P(f), R(f) and Ω(f) the sets of periodic points, recurrent points and non-wandering points of f, respectively. In this paper we show that: (1) If L=(x,y) is an open arc contained in an edge of G such that {fm(x),fk(y)}⊂(x,y) for some m,k∈N, then R(f)∩(x,y)≠∅; (2) Any isolated point of P(f) is also an isolated point of Ω(f); (3) If x∈Ω(f)−Ω(fn) for some n∈N, then x is an eventually periodic point. These generalize the corresponding results in W. Huang and X. Ye (2001) [9] and J. Xiong (1983, 1986) [17] and [19] on interval maps or tree maps.     

The pexiderized Go?a?b-Schinzel functional equation

Let X be a linear space over a commutative field K. We characterize a general solution f,g,h,k:X→K of the pexiderized Go?a?b-Schinzel equation f(x+g(x)y)=h(x)k(y), as well as real continuous solutions of the equation.     

On the nonvanishing of homogeneous product sums

For integer n ≥ 1 let H_n = H_n(x, y, z) = Σ_{p + q + r = n}x^py^qz^r be the homogeneous product sum of weight n on three letters x, y, z. Morgan Ward conjectured that H_n ≠ 0 for all integers n, x, y, z with n > 1 and xyz ≠ 0. In support of this conjecture he proved that H_n ≠ 0 if n is even or if n + 2 is a prime number greater than 3. This paper adds considerably more evidence in support of Ward's conjecture by showing that in many cases H_n(a, b, c)¬=0 modulo 2, 4, or 16. The parity of H_n(a, b, c) is determined in all cases and, when H_n(a, b, c) is even, further congruences are given modulo 4 or 16.     

Duality for a Class of Multiobjective Control Problems

In this paper, a class of multiobjective control problems is considered, where the objective and constraint functions involved are f(t, x(t), ?(t), y(t), z(t)) with x(t) ∈ Rⁿ, y(t) ∈ Rⁿ, and z(t) ∈ R^m, where x(t) and z(t) are the control variables and y(t) is the state variable. Under the assumption of invexity and its generalization, duality theorems are proved through a parametric approach to related properly efficient solutions of the primal and dual problems.     

Out-arc pancyclicity of vertices in tournaments

Yao, Guo and Zhang [T. Yao, Y. Guo, K. Zhang, Pancyclic out-arcs of a vertex in a tournament, Discrete Appl. Math. 99 (2000) 245-249.] proved that every strong tournament contains a vertex u such that every out-arc of u is pancyclic. In this paper, we prove that every strong tournament with minimum out-degree at least two contains two such vertices. Yeo [A. Yeo, The number of pancyclic arcs in a k-strong tournament, J. Graph Theory 50 (2005) 212-219.] conjectured that every 2-strong tournament has three distinct vertices {x,y,z}, such that every arc out of x,y and z is pancyclic. In this paper, we also prove that Yeo’s conjecture is true.     

A nonlinear evolution system with two subdifferentials and monotone differential games

It is shown that the first order multivalued equation for V = V(t, x, y, z) involving the sum of two subdifferentials composed with the partials of V (V_t +f(t, x, y, z) · ▽_xV + β(V_y) + γ(V_z) + h(t, x, y, z) ? 0 a.e.) has a Lipschitz solution. This solution is shown to be the value of a differential game in which the players are restricted to choosing monotone nondecreasing functions of time. Accordingly, the multivalued equation is interpreted as the corresponding Hamilton-Jacobi equation of the game.     

THE EXTREME POINTS OF SEVERAL CLASSES OF ANALYTIC FUNCTIONS

1Intr0ducti0nLetAden0tethesetofallfunctionsanalyticinA={z:Izl<1}.LetB={W:WEAandIW(z)l51}.Aisalocallyconvexlineaztop0l0gicalspacewithrespecttothetopologyofuniformconvergenceon`c0mpact8ubsetsofA-LetTh(c1,'tc.-1)={p(z):p(z)EA,Rop(z)>0,p(z)=1 clz czzz ' c.-lz"-l 4z" ',wherecl,',cn-1areforedcomplexconstants}.LetTh,.(b,,-..,b,-,)={p(z):P(z)'EAwithReP(z)>Oandp(z)=1 blz ' b.-lz"-l 4z" '-,wherebl,-'-jbu-1areffeedrealconstantsanddkarerealnumbersf0rk=n,n 1,'--}-LetTu(l1,'i'tI.-1)={…     

Stability interval for explicit difference schemes for multi-dimensional second-order hyperbolic equations with significant first-order space derivative terms

In this piece of work, we introduce a new idea and obtain stability interval for explicit difference schemes of O(k²+h²) for one, two and three space dimensional second-order hyperbolic equations u_tt=a(x,t)u_xx+α(x,t)u_x-2η²(x,t)u,u_tt=a(x,y,t)u_xx+b(x,y,t)u_yy+α(x,y,t)u_x+β(x,y,t)u_y-2η²(x,y,t)u, and u_tt=a(x,y,z,t)u_xx+b(x,y,z,t)u_yy+c(x,y,z,t)u_zz+α(x,y,z,t)u_x+β(x,y,z,t)u_y+γ(x,y,z,t)u_z-2η²(x,y,z,t)u,0<x,y,z<1,t>0 subject to appropriate initial and Dirichlet boundary conditions, where h>0 and k>0 are grid sizes in space and time coordinates, respectively. A new idea is also introduced to obtain explicit difference schemes of O(k²) in order to obtain numerical solution of u at first time step in a different manner.     

Control problems for parabolic equations on controlled domains

Given the one-dimensional heat equation v_t = v_xx on the controlled domain Q(y) = {(t, x); 0 < x < y(t), 0 < t < T} subject to some initial-boundary conditions, we study the problem of optimally selecting y(·) from some admissible class so as to maximize a given payoff of fixed duration. Q(y) is thus a controlled domain. We also study the problem in which the heat equation holds in Q(y, z) = {z(t) < x < y(t), 0 < t < T}; z minimizing, y maximizing, i.e., the differential game. The principle techniques involved are (i) transforming the controlled domain to an uncontrolled domain and then (ii) using the method of lines for parabolic equations to enable us to use known results for control systems governed by ordinary differential equations. Sufficient conditions for existence in an admissible class is given and the method of lines allows numerical techniques to be applied to determine the optimal control in our class.     

Identification of the unknown diffusion coefficient in a linear parabolic equation by the semigroup approach

In this article, we study the semigroup approach for the mathematical analysis of the inverse coefficient problems of identifying the unknown coefficient k(x) in the linear parabolic equation ut(x,t)=(k(x)uxx(x,t)), with Dirichlet boundary conditions u(0,t)=ψ₀, u(1,t)=ψ₁. Main goal of this study is to investigate the distinguishability of the input-output mappings Φ[⋅]:K→C¹[0,T], Ψ[⋅]:K→C¹[0,T] via semigroup theory. In this paper, we show that if the null space of the semigroup T(t) consists of only zero function, then the input-output mappings Φ[⋅] and Ψ[⋅] have the distinguishability property. Moreover, the values k(0) and k(1) of the unknown diffusion coefficient k(x) at x=0 and x=1, respectively, can be determined explicitly by making use of measured output data (boundary observations) f(t):=k(0)ux(0,t) or/and h(t):=k(1)ux(1,t). In addition to these, the values k^′(0) and k^′(1) of the unknown coefficient k(x) at x=0 and x=1, respectively, are also determined via the input data. Furthermore, it is shown that measured output dataf(t) and h(t) can be determined analytically, by an integral representation. Hence the input-output mappings Φ[⋅]:K→C¹[0,T], Ψ[⋅]:K→C¹[0,T] are given explicitly in terms of the semigroup. Finally by using all these results, we construct the local representations of the unknown coefficient k(x) at the end points x=0 and x=1.