A note on vertex pancyclic oriented graphs

Let D be an oriented graph of order n ≥ 9, minimum degree at least n − 2, such that, for the choice of distinct vertices x and y, either xy ∈ E(D) or d⁺(x) + d⁻(y) ≥ n − 3. Song (J. Graph Theory 18 (1994), 461–468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also generalizes a result of Jackson (J. Graph Theory 5 (1981), 147–157) for the existence of a hamiltonian cycle in oriented graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 313–318, 1999     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

A lower bound for the circumference of a graph

Let G=(V, E) be a block of order n, different from K_n. Let m=min {d(x)+d(y): [x, y]?E}. We show that if m?n then G contains a cycle of length at least m.     

Sur les arborescences dans un graphe oriente

The main result of this paper is the following theorem: Let G = (X,E) be a digraph without loops or multiple edges, |X| ?3, and h be an integer ?1, if G contains a spanning arborescence and if d⁺_G(x)+d^?_G(x)+d^?_G(y)+d^?_G(y)? 2|X |?2h?1 for all x, y?X, x ≠ y, non adjacent in G, then G contains a spanning arborescence with ?h terminal vertices. A strengthening of Gallai-Milgram's theorem is also proved.     

Positive Cubature Formulas and Marcinkiewicz–Zygmund Inequalities on Spherical Caps

Let Π _n ^d denote the space of all spherical polynomials of degree at most n on the unit sphere $\mathbb{S}^{d}Let Π _n ^d denote the space of all spherical polynomials of degree at most n on the unit sphere \mathbbS^d\mathbb{S}^{d} of ℝ ^d+1, and let d(x,y) denote the geodesic distance arccos x⋅y between x,y ? \mathbbS^dx,y\in\mathbb{S}^{d} . Given a spherical cap

B(e,a)={x ? \mathbbSd:d(x,e) ￡ a}    (e ? \mathbbSd, a ? (0,p) is bounded awayfrom p),B(e,\alpha)=\big\{x\in\mathbb{S}^{d}:d(x,e)\leq\alpha\big\}\quad \bigl(e\in\mathbb{S}^{d},\ \alpha\in(0,\pi)\ \mbox{is bounded awayfrom}\ \pi\bigr),      6. COMPUTING THE SPREADING AND COVERING NUMBERS      《代数通讯》2013,41(12):5687-5699 Let S = k[x 1,…,x n ], d a positive integer, and suppose that S D is the vector space of all polynomials of degree d in S. Define α n (d) ? max { dim k V| V monomial subspace of S d , dim k S 1 V = n dim k V} and ρ n (d +1) ? min {dim k V | V monomial subspace of S d , S 1 V = S d+1}. The numbers α n (d) and ρ n (d+ 1) are called the spreading numbers and covering numbers, respectively. We describe an approach to calculate these numbers that uses simplicial complexes.      7. A degree condition for the circumference of a graph      Nathaniel Dean  Pierre Fraisse 《Journal of Graph Theory》1989,13(3):331-334 We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x1,…,xn and edge set E that satisfies the property that, for any two integers j and k with j < k, xjxk ? E, d(xi) ? j and d(xk) ? K - 1, we have (1) d(xi) + d(xk ? m if j + k ? n and (2) if j + k < n, either m ? n or d(xj) + d(xk) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.      8. On the Boundary Behaviour of Poisson Integrals of Finite Measures in (n + 1)-dimensional Half Space      《复变函数与椭圆型方程》2012,57(9):769-785 It is well known that the harmonic functions u on the Euclidean upper (n + 1)-dimensional half-space E+ n+1 = {(x, y) = (x 1,…,xn,y) ? E n+1: y > 0} satisfying sup y>0 ||u(·,y)||1 < ∞ are precisely the Poisson-integrals u(x,y) = ∫ En P(x - t,y)dμ(t) with respect to a measure μ of finite variation on En , and that (Fatou's theorem in E+ n+1) in almost every point x ? En the non-tangential boundary limit of u exists and coincides with du/dλ. While this is a special case of a general assertion in potential theory, it is shown that the proof of Fatou's theorem for harmonic functions on a ball may readily be transferred to the given setup and that the influence of a singular component of μ on the boundary behaviour of u may also be established without recourse to the existence of the derivative dμ/dλ. Finally the C 0-property of u is characterized by suitable conditions on μ.      9. A note on Z 3-connected graphs with degree sum condition      Xin Min Hou 《数学学报(英文版)》2012,28(11):2161-2168 A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al.      10. Dynamics of a family of piecewise-linear area-preserving plane maps III. Cantor set spectra      Jeffrey C. Lagarias  Eric Rains 《Journal of Difference Equations and Applications》2013,19(14):1205-1224 This paper studies the behavior under iteration of the maps T ab (x,y) = (F ab (x) ? y, x) of the plane ?2, in which F ab (x) = ax if x ≥ 0 and bx if x < 0. These maps are area-preserving homeomorphisms of ?2 that map rays from the origin to rays from the origin. Orbits of the map correspond to solutions of the nonlinear difference equation x n+2 = 1/2(a ? b)|x n+1|+1/2(a+b)x n+1 ? x n . This difference equation can be rewritten in an eigenvalue form for a nonlinear difference operator of Schrödinger type ? x n+2+2x n+1 ? x n +V μ(x n+1)x n+1 = Ex n+1, in which μ = (1/2)(a ? b) is fixed, and V μ(x) = μ(sgn(x)) is an antisymmetric step function potential, and the energy E = 2 ? 1/2(a+b). We study the set Ω SB of parameter values where the map T ab has at least one bounded orbit, which correspond to l ∞-eigenfunctions of this difference operator. The paper shows that for transcendental μ the set Spec∞[μ] of energy values E having a bounded solution is a Cantor set. Numerical simulations suggest the possibility that these Cantor sets have positive (one-dimensional) measure for all real values of μ.      11. Multiple recurrence and nilsequences      Vitaly Bergelson  Bernard Host  Bryna Kra  Imre Ruzsa 《Inventiones Mathematicae》2005,160(2):261-303 Aiming at a simultaneous extension of Khintchine(X,X,m,T)(X,\mathcal{X},\mu,T) and a set A ? XA\in\mathcal{X} of positive measure, the set of integers n such that A T^2nA T^knA)(A)^k+1-\mu(A{\cap} T^{n}A{\cap} T^{2n}A{\cap} \ldots{\cap} T^{kn}A)>\mu(A)^{k+1}-\epsilon is syndetic. The size of this set, surprisingly enough, depends on the length (k+1) of the arithmetic progression under consideration. In an ergodic system, for k=2 and k=3, this set is syndetic, while for kòf(x)f(Tnx)f(T2nx)? f(Tknx)  dm(x)\int{f(x)f(T^{n}x)f(T^{2n}x){\ldots} f(T^{kn}x) \,d\mu(x)} , where k and n are positive integers and f is a bounded measurable function. We also derive combinatorial consequences of these results, for example showing that for a set of integers E with upper Banach density d*(E)>0 and for all {n ? \mathbbZ\colon d*(E?(E+n)?(E+2n)?(E+3n)) > d*(E)4-e}\big\{n\in\mathbb{Z}{\colon} d^*\big(E\cap(E+n)\cap(E+2n)\cap(E+3n)\big) > d^*(E)^4-\epsilon\big\}      12. On exponential sums over primes in short intervals      Guangshi Lü  Huixue Lao 《Monatshefte für Mathematik》2007,49(5):153-164 Let Λ(n) be the von Mangoldt function, x real and y small compared with x. This paper gives a non-trivial estimate on the exponential sum over primes in short intervals S2(x,y;a)=?x < n ￡ x+yL(n)e(n2 a)S_2(x,y;{\alpha})=\sum_{x < n \le x+y}\Lambda(n)e(n^2 {\alpha}) for all α ∈ [0,1] whenever x\frac23+e ￡ y ￡ xx^{\frac{2}{3}+{\varepsilon}}\le y \le x . This result is as good as what was previously derived from the Generalized Riemann Hypothesis.      13. Sphere coverings and identifying codes      David Auger  Gérard Cohen  Sihem Mesnager 《Designs, Codes and Cryptography》2014,70(1-2):3-7 In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S r (x) = {y ∈ V : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ≥ 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.      14. Functional equations on semigroups      P. Sinopoulos 《Aequationes Mathematicae》2000,59(3):255-261 Summary. We determine the general solution g:S? F g:S\to F of the d'Alembert equation¶¶g(x+y)+g(x+sy)=2g(x)g(y)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)g(y)\qquad (x,y\in S) ,¶the general solution g:S? G g:S\to G of the Jensen equation¶¶g(x+y)+g(x+sy)=2g(x)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)\qquad (x,y\in S) ,¶and the general solution g:S? H g:S\to H of the quadratic equation¶¶g(x+y)+g(x+sy)=2g(x)+2g(y)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)+2g(y)\qquad (x,y\in S) ,¶ where S is a commutative semigroup, F is a quadratically closed commutative field of characteristic different from 2, G is a 2-cancellative abelian group, H is an abelian group uniquely divisible by 2, and s \sigma is an endomorphism of S with s(s(x)) = x \sigma(\sigma(x)) = x .      15. On Enomoto’s problems in a bipartite graph      Jin Yan  YunShu Gao 《中国科学A辑(英文版)》2009,52(9):1947-1954 In this paper, we obtain the following result: Let k, n 1 and n 2 be three positive integers, and let G = (V 1,V 2;E) be a bipartite graph with |V1| = n 1 and |V 2| = n 2 such that n 1 ⩾ 2k + 1, n 2 ⩾ 2k + 1 and |n 1 − n 2| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V 1 and y ∈ V 2 with xy $ \notin $ \notin E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.      16. Strong consistency of kernel estimators for Markov transition densities      C. C.Y. Dorea 《Bulletin of the Brazilian Mathematical Society》2002,33(3):409-418 Let P(x, dy) = t (x, y)ν(d y) be the transition kernel of a Markov chain, where t (x, y) is a density with respect to a σ-finite measure ν on (E,ℰ), with E ⊂ R d . In this note, we propose a general class of estimates for t (x, y) that are strongly consistent and that extend the classical results for continuous densities on R d . Received: 2 June 2002      17. Linear preservers of orthogonal decomposable Tensors      M. H. Lim 《Linear and Multilinear Algebra》2013,61(4):333-354 Let G be a subgroup of the symmetric group Sm and V be an n-dimensional unitary space where nm. Let V(G) be the symmetry class of tensors over V associated with G and the identity character. Let D(G) be the set of all decomposable elements of V(G) and O(G) be its subset consisting of all nonzero decomposable tensors x 1 ?…? xm such that {x 1,…,xm } is an orthogonal set. In this paper we study the structure of linear mappings on V(G) that preserve one of the following subsets: (i)O(G), (ii) D(G)\(O(G)?{0}).      18. A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees      Yoshimi Egawa  Kenta Ozeki 《Combinatorica》2014,34(1):47-60 Let G be a connected simple graph, let X?V (G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d T (x) for all x ∈ X, where d T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N G (S) ? S| ? f(S) + 2|S| ? ω G (S) ≥, where ω G (S) is the number of components of the subgraph induced by S.      19. Largest cliques in connected supermagic graphs      A. Llad 《European Journal of Combinatorics》2007,28(8):2240 A graph G=(V,E) is said to be magic if there exists an integer labeling f:VE[1,|VE|] such that f(x)+f(y)+f(xy) is constant for all edges xyE.Enomoto, Masuda and Nakamigawa proved that there are magic graphs of order at most 3n2+o(n2) which contain a complete graph of order n. Bounds on Sidon sets show that the order of such a graph is at least n2+o(n2). We close the gap between those two bounds by showing that, for any given connected graph H of order n, there is a connected magic graph G of order n2+o(n2) containing H as an induced subgraph. Moreover G admits a supermagic labeling f, which satisfies the additional condition f(V)=[1,|V|].      20. An Extremal Problem on Degree Sequences of Graphs      Nathan Linial  Eyal Rozenman 《Graphs and Combinatorics》2002,18(3):573-582  Let G=(I n ,E) be the graph of the n-dimensional cube. Namely, I n ={0,1} n and [x,y]∈E whenever ||x−y||1=1. For A⊆I n and x∈A define h A (x) =#{y∈I n A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I n of size 2 n−1 we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices. Received: January 7, 2000 RID="*" ID="*" Supported in part by BSF and by the Israeli academy of sciences

COMPUTING THE SPREADING AND COVERING NUMBERS

Let S = k[x ₁,…,x _n ], d a positive integer, and suppose that S _D is the vector space of all polynomials of degree d in S. Define α _n (d) ? max { dim _k V| V monomial subspace of S _d , dim _k S ₁ V = n dim _k V} and ρ _n (d +1) ? min {dim _k V | V monomial subspace of S _d , S ₁ V = S _d+1}. The numbers α _n (d) and ρ _n (d+ 1) are called the spreading numbers and covering numbers, respectively. We describe an approach to calculate these numbers that uses simplicial complexes.     

A degree condition for the circumference of a graph

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x₁,…,x_n and edge set E that satisfies the property that, for any two integers j and k with j < k, x_jx_k ? E, d(x_i) ? j and d(x_k) ? K - 1, we have (1) d(x_i) + d(x_k ? m if j + k ? n and (2) if j + k < n, either m ? n or d(x_j) + d(x_k) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.     

On the Boundary Behaviour of Poisson Integrals of Finite Measures in (n + 1)-dimensional Half Space

It is well known that the harmonic functions u on the Euclidean upper (n + 1)-dimensional half-space E⁺ _n+1 = {(x, y) = (x ₁,…,x_n,y) ? E _n+1: y > 0} satisfying sup _y>0 ||u(·,y)||₁ < ∞ are precisely the Poisson-integrals u(x,y) = ∫ _En P(x - t,y)dμ(t) with respect to a measure μ of finite variation on E_n , and that (Fatou's theorem in E⁺ _n+1) in almost every point x ? E_n the non-tangential boundary limit of u exists and coincides with du/dλ. While this is a special case of a general assertion in potential theory, it is shown that the proof of Fatou's theorem for harmonic functions on a ball may readily be transferred to the given setup and that the influence of a singular component of μ on the boundary behaviour of u may also be established without recourse to the existence of the derivative dμ/dλ. Finally the C ₀-property of u is characterized by suitable conditions on μ.     

A note on Z 3-connected graphs with degree sum condition

A graph G satisfies the Ore-condition if d(x) + d(y) ≥ | V (G) | for any xy ■ E(G). Luo et al. [European J. Combin., 2008] characterized the simple Z3-connected graphs satisfying the Ore-condition. In this paper, we characterize the simple Z3-connected graphs G satisfying d(x) + d(y) ≥ | V (G) |-1 for any xy ■ E(G), which improves the results of Luo et al.     

Dynamics of a family of piecewise-linear area-preserving plane maps III. Cantor set spectra

This paper studies the behavior under iteration of the maps T _ab (x,y) = (F _ab (x) ? y, x) of the plane ?², in which F _ab (x) = ax if x ≥ 0 and bx if x < 0. These maps are area-preserving homeomorphisms of ?² that map rays from the origin to rays from the origin. Orbits of the map correspond to solutions of the nonlinear difference equation x _n+2 = 1/2(a ? b)|x _n+1|+1/2(a+b)x _n+1 ? x _n . This difference equation can be rewritten in an eigenvalue form for a nonlinear difference operator of Schrödinger type ? x _n+2+2x _n+1 ? x _n +V _μ(x _n+1)x _n+1 = Ex _n+1, in which μ = (1/2)(a ? b) is fixed, and V _μ(x) = μ(sgn(x)) is an antisymmetric step function potential, and the energy E = 2 ? 1/2(a+b). We study the set Ω _SB of parameter values where the map T _ab has at least one bounded orbit, which correspond to l _∞-eigenfunctions of this difference operator. The paper shows that for transcendental μ the set Spec_∞[μ] of energy values E having a bounded solution is a Cantor set. Numerical simulations suggest the possibility that these Cantor sets have positive (one-dimensional) measure for all real values of μ.     

Multiple recurrence and nilsequences

Aiming at a simultaneous extension of Khintchine(X,X,m,T)(X,\mathcal{X},\mu,T) and a set A ? XA\in\mathcal{X} of positive measure, the set of integers n such that A T^2nA T^knA)(A)^k+1-\mu(A{\cap} T^{n}A{\cap} T^{2n}A{\cap} \ldots{\cap} T^{kn}A)>\mu(A)^{k+1}-\epsilon is syndetic. The size of this set, surprisingly enough, depends on the length (k+1) of the arithmetic progression under consideration. In an ergodic system, for k=2 and k=3, this set is syndetic, while for kòf(x)f(Tⁿx)f(T²ⁿx)? f(T^knx)  dm(x)\int{f(x)f(T^{n}x)f(T^{2n}x){\ldots} f(T^{kn}x) \,d\mu(x)} , where k and n are positive integers and f is a bounded measurable function. We also derive combinatorial consequences of these results, for example showing that for a set of integers E with upper Banach density d^*(E)>0 and for all {n ? \mathbbZ\colon d^*(E?(E+n)?(E+2n)?(E+3n)) > d^*(E)⁴-e}\big\{n\in\mathbb{Z}{\colon} d^*\big(E\cap(E+n)\cap(E+2n)\cap(E+3n)\big) > d^*(E)^4-\epsilon\big\}     

On exponential sums over primes in short intervals

Let Λ(n) be the von Mangoldt function, x real and y small compared with x. This paper gives a non-trivial estimate on the exponential sum over primes in short intervals S₂(x,y;a)=?_{x < n ￡ x+y}L(n)e(n² a)S_2(x,y;{\alpha})=\sum_{x < n \le x+y}\Lambda(n)e(n^2 {\alpha}) for all α ∈ [0,1] whenever x^\frac23+e ￡ y ￡ xx^{\frac{2}{3}+{\varepsilon}}\le y \le x . This result is as good as what was previously derived from the Generalized Riemann Hypothesis.     

Sphere coverings and identifying codes

In any connected, undirected graph G = (V, E), the distance d(x, y) between two vertices x and y of G is the minimum number of edges in a path linking x to y in G. A sphere in G is a set of the form S _r (x) = {y ∈ V : d(x, y) = r}, where x is a vertex and r is a nonnegative integer called the radius of the sphere. We first address in this paper the following question: What is the minimum number of spheres with fixed radius r ≥ 0 required to cover all the vertices of a finite, connected, undirected graph G? We then turn our attention to the Hamming Hypercube of dimension n, and we show that the minimum number of spheres with any radii required to cover this graph is either n or n + 1, depending on the parity of n. We also relate the two above problems to other questions in combinatorics, in particular to identifying codes.     

Functional equations on semigroups

Summary. We determine the general solution g:S? F g:S\to F of the d'Alembert equation¶¶g(x+y)+g(x+sy)=2g(x)g(y)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)g(y)\qquad (x,y\in S) ,¶the general solution g:S? G g:S\to G of the Jensen equation¶¶g(x+y)+g(x+sy)=2g(x)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)\qquad (x,y\in S) ,¶and the general solution g:S? H g:S\to H of the quadratic equation¶¶g(x+y)+g(x+sy)=2g(x)+2g(y)       (x,y ? S) g(x+y)+g(x+\sigma y)=2g(x)+2g(y)\qquad (x,y\in S) ,¶ where S is a commutative semigroup, F is a quadratically closed commutative field of characteristic different from 2, G is a 2-cancellative abelian group, H is an abelian group uniquely divisible by 2, and s \sigma is an endomorphism of S with s(s(x)) = x \sigma(\sigma(x)) = x .     

On Enomoto’s problems in a bipartite graph

In this paper, we obtain the following result: Let k, n ₁ and n ₂ be three positive integers, and let G = (V ₁,V ₂;E) be a bipartite graph with |V1| = n ₁ and |V ₂| = n ₂ such that n ₁ ⩾ 2k + 1, n ₂ ⩾ 2k + 1 and |n ₁ − n ₂| ⩽ 1. If d(x) + d(y) ⩾ 2k + 2 for every x ∈ V ₁ and y ∈ V ₂ with xy $ \notin $ \notin E(G), then G contains k independent cycles. This result is a response to Enomoto’s problems on independent cycles in a bipartite graph.     

Strong consistency of kernel estimators for Markov transition densities

Let P(x, dy) = t (x, y)ν(d y) be the transition kernel of a Markov chain, where t (x, y) is a density with respect to a σ-finite measure ν on (E,ℰ), with E ⊂ R ^d . In this note, we propose a general class of estimates for t (x, y) that are strongly consistent and that extend the classical results for continuous densities on R ^d . Received: 2 June 2002     

Linear preservers of orthogonal decomposable Tensors

Let G be a subgroup of the symmetric group S_m and V be an n-dimensional unitary space where nm. Let V(G) be the symmetry class of tensors over V associated with G and the identity character. Let D(G) be the set of all decomposable elements of V(G) and O(G) be its subset consisting of all nonzero decomposable tensors x ₁ ^?…^? x_m such that {x ₁,…,x_m } is an orthogonal set. In this paper we study the structure of linear mappings on V(G) that preserve one of the following subsets: (i)O(G), (ii) D(G)\(O(G)?{0}).     

A necessary and sufficient condition for the existence of a spanning tree with specified vertices having large degrees

Let G be a connected simple graph, let X?V (^G) and let f be a mapping from X to the set of integers. When X is an independent set, Frank and Gyárfás, and independently, Kaneko and Yoshimoto gave a necessary and sufficient condition for the existence of spanning tree T in G such that d _T (x) for all x ∈ X, where d _T (x) is the degree of x and T. In this paper, we extend this result to the case where the subgraph induced by X has no induced path of order four, and prove that there exists a spanning tree T in G such that d _T (x) ≥ f(x) for all x ∈ X if and only if for any nonempty subset S ? X, |N _G (S) ? S| ? f(S) + 2|S| ? ω _G (S) ≥, where ω _G (S) is the number of components of the subgraph induced by S.     

Largest cliques in connected supermagic graphs

A graph G=(V,E) is said to be magic if there exists an integer labeling f:VE[1,|VE|] such that f(x)+f(y)+f(xy) is constant for all edges xyE.Enomoto, Masuda and Nakamigawa proved that there are magic graphs of order at most 3n²+o(n²) which contain a complete graph of order n. Bounds on Sidon sets show that the order of such a graph is at least n²+o(n²). We close the gap between those two bounds by showing that, for any given connected graph H of order n, there is a connected magic graph G of order n²+o(n²) containing H as an induced subgraph. Moreover G admits a supermagic labeling f, which satisfies the additional condition f(V)=[1,|V|].     

An Extremal Problem on Degree Sequences of Graphs

 Let G=(I _n ,E) be the graph of the n-dimensional cube. Namely, I _n ={0,1} ⁿ and [x,y]∈E whenever ||x−y||₁=1. For A⊆I _n and x∈A define h _A (x) =#{y∈I _n A|[x,y]∈E}, i.e., the number of vertices adjacent to x outside of A. Talagrand, following Margulis, proves that for every set A⊆I _n of size 2 ⁿ⁻¹ we have for a universal constant K independent of n. We prove a related lower bound for graphs: Let G=(V,E) be a graph with . Then , where d(x) is the degree of x. Equality occurs for the clique on k vertices. Received: January 7, 2000 RID="*" ID="*" Supported in part by BSF and by the Israeli academy of sciences