Completely strong path-connected tournaments

Let T = (V, A) be a tournament with p vertices. T is called completely strong path-connected if for each arc (a, b) ∈ A and k (k = 2, 3,…, p), there is a path from b to a of length k (denoted by P_k(a, b)) and a path from a to b of length k (denoted by P′_k(a, b)). In this paper, we prove that T is completely strong path-connected if and only if for each arc (a, b) ∈ A, there exist P₂(a, b), P′₂(a, b) in T, and T satisfies one of the following conditions: (a) T/T₀-type graph, (b) T is 2-connected, (c) for each arc (a, b) ∈ A, there exists a P′_p?1(a, b) in T.     

Sperner labellings: A combinatorial approach

In 2002, De Loera, Peterson and Su proved the following conjecture of Atanassov: let T be a triangulation of a d-dimensional polytope P with n vertices v₁,v₂,…,vn; label the vertices of T by 1,2,…,n in such a way that a vertex of T belonging to the interior of a face F of P can only be labelled by j if vj is on F; then there are at least n−d simplices labelled with d+1 different labels. We prove a generalisation of this theorem which refines this lower bound and which is valid for a larger class of objects.     

Nondifferentiable boundary points of the higher numerical range

Let A be an n-square complex matrix. Every nondifferentiable point on ?W_m(A), the boundary of the mth numerical range of A, is a sum of m eigenvalues of A. This generalizes a theorem of W. F. Donoghue. Moreover, if sufficiently many sums of m eigenvalues of A occur on ?W_m(A), then A is normal. From these results it follows that if ?W_m(A) is a convex polygon with sufficiently many vertices, then A is normal.     

Sur la répartition des diamants dans un tournoi

A tournament T=(V,A) is a directed graph such that for every x,y∈V, where x≠y, (x,y)∈A if and only if (y,x)?A. For example, the 3-cycle is the tournament ({1,2,3}, {(1,2),(2,3),(3,1)}). Up to an isomorphism, there are two tournaments with 4 vertices and containing an unique 3-cycle which we call diamonds. We prove that for any tournament T defined on n?9 vertices, either T contains at least 2n?6 diamonds or the number of diamonds contained in T is equal to 0, n?3 or 2n?8. Following the characterization of the tournaments without diamonds due to Gnanvo and Ille (Z. Math. Logik Grundlag. Math. 38 (1992) 283–291) and to Lopez and Rauzy (Z. Math. Logik Grundlag. Math. 38 (1992) 27–37), we study the morphology of the tournaments defined on n?5 vertices and which contain exactly n?3 or 2n?8 diamonds. To cite this article: H. Bouchaala, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Asymptotical Formulas For Solutions Of Linear Differential Systems Of The First Order

In this paper a system of differential equations y′ ? A(·,λ)y = 0 is considered on the finite interval [a,b] where λ ∈ C, A(·, λ):= λ A₁+ A ₀ +λ _?1A_?1(·,λ) and A ₁,A ₀, A _{? 1} are n × n matrix-functions. The main assumptions: A ₁ is absolutely continuous on the interval [a, b], A ₀ and A _{- 1}(·,λ) are summable on the same interval when ¦λ¦ is sufficiently large; the roots φ₁(x),…,φ_n (x) of the characteristic equation det (φ E — A ₁) = 0 are different for all x ∈ [a,b] and do not vanish; there exists some unlimited set Ω ? C on which the inequalities Re(λφ₁(x)) ≤ … ≤ Re (λφ_n(x)) are fulfilled for all x ∈ [a,b] and for some numeration of the functions φ_j(x). The asymptotic formula of the exponential type for a fundamental matrix of solutions of the system is obtained for sufficiently large ¦λ¦. The remainder term of this formula has a new type dependence on properties of the coefficients A ₁ (x), A _o (x) and A _{- 1} (x).     

Theory of path length distributions I

The Path Length Distribution (PLD) of a (p, q) graph is defined to be the array (X₀, X₁, X₂, …, X_p-1), where X₀ is the number of (unordered) pairs of vertices which have no path connecting them and X_l, 1 ≦ l ≦ p-1, is the number of pairs of vertices which are connected by a path of length l (see [1, 2]). The topic of this paper is the occurence of non-isomorphic graphs having the same path length distribution. For trees, a constructive procedure is given, showing that for any positive integer N there exist N non-isomorphic trees of diameter four which have the same PLD. Also considered are PLD-maximal graphs — those graphs with p vertices such that all pairs of vertices are connected by a path of length l for 2 ≦ l ≦ p-1. In addition to providing more examples of non-isomorphic graphs having the same PLD, PLD-maximal graphs are of intrinsic interest. For PLD-maximal graphs, we give sufficient degree and edge conditions and a necessary edge condition.     

On the packing chromatic number of some lattices

For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V₁,V₂,…,V_m where V_i is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z³ do not have finite packing chromatic numbers.     

Averaging of gradient in the space of linear triangular and bilinear rectangular finite elements

An averaging method for the second-order approximation of the values of the gradient of an arbitrary smooth function u = u(x ₁, x ₂) at the vertices of a regular triangulation T _h composed both of rectangles and triangles is presented. The method assumes that only the interpolant Π _h [u] of u in the finite element space of the linear triangular and bilinear rectangular finite elements from T _h is known. A complete analysis of this method is an extension of the complete analysis concerning the finite element spaces of linear triangular elements from [Dalík J., Averaging of directional derivatives in vertices of nonobtuse regular triangulations, Numer. Math., 2010, 116(4), 619–644]. The second-order approximation of the gradient is extended from the vertices to the whole domain and applied to the a posteriori error estimates of the finite element solutions of the planar elliptic boundary-value problems of second order. Numerical illustrations of the accuracy of the averaging method and of the quality of the a posteriori error estimates are also presented.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

The diameter of the acyclic Birkhoff polytope

In this work we give an interpretation of vertices and edges of the acyclic Birkhoff polytope, T_n=Ω_n(T), where T is a tree with n vertices, in terms of graph theory. We generalize a recent result relatively to the diameter of the graph G(T_n).     

Simultaneous quasidiagonalization of complex matrices

Let

be the complex algebra generated by a pair of n × n Hermitian matrices A, B. A recent result of Watters states that A, B are simultaneously unitarily quasidiagonalizable [i.e., A and B are simultaneously unitarily similar to direct sums C₁⊕…⊕C_t,D₁⊕…⊕D_t for some t, where C_i, D_i are k_i × k_i and k_i?2(1?i?t)] if and only if [p(A, B), A]² and [p(A, B), B]² belong to the center of

for all polynomials p(x, y) in the noncommuting variables x, y. In this paper, we obtain a finite set of conditions which works. In particular we show that if A, B are positive semidefinite, then A, B are simultaneously quasidiagonalizable if (and only if) [A, B]², [A², B]² and [A, B²]² commute with A, B.     

An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree

A Bethe tree B_d,k is a rooted unweighted of k levels in which the root vertex has degree equal to d, the vertices at level j(2?j?k-1) have degree equal to (d+1) and the vertices at level k are the pendant vertices. In this paper, we first derive an explicit formula for the eigenvalues of the adjacency matrix of B_d,k. Moreover, we give the corresponding multiplicities. Next, we derive an explicit formula for the simple nonzero eigenvalues, among them the largest eigenvalue, of the Laplacian matrix of B_d,k. Finally, we obtain upper bounds on the largest eigenvalue of the adjacency matrix and of the Laplacian matrix of any tree T. These upper bounds are given in terms of the largest vertex degree and the radius of T, and they are attained if and only if T is a Bethe tree.     

Homogeneous structures and rigidity of isoparametric submanifolds in Hilbert space

We study isoparametric submanifolds of rank at least two in a separable Hilbert space, which are known to be homogeneous by the main result in [E. Heintze and X. Liu, Ann. of Math. (2), 149 (1999), 149?C181], and with such a submanifold M and a point x in M we associate a canonical homogeneous structure ?? _x (a certain bilinear map defined on a subspace of T _x M × T _x M). We prove that ?? _x , together with the second fundamental form ?? _x , encodes all the information about M, and we deduce from this the rigidity result that M is completely determined by ?? _x and (????) _x , thereby making such submanifolds accessible to classification. As an essential step, we show that the one-parameter groups of isometries constructed in [E. Heintze and X. Liu, Ann. of Math. (2), 149 (1999), 149?C181] to prove their homogeneity induce smooth and hence everywhere defined Killing fields, implying the continuity of ?? (this result also seems to close a gap in [U. Christ, J. Differential Geom., 62 (2002), 1?C15]). Here an important tool is the introduction of affine root systems of isoparametric submanifolds.     

Bohr compactifications and a result of følner

In this paper, we study the Bohr compactification of an arbitrary topological groupT with regard to obtaining relations between relatively dense (or discretely syndetic) subsets ofT, and neighborhoods of the identity in the Bohr compactification. The methods utilized are those algebraic techniques which have been recently applied to topological dynamics (see [2]). For an abelian group, we show that cls (A ^?1 AAa ^?1), forA relatively dense anda∈A, is usually a neighborhood of the identity, thus generalizing a result of Følner [4]. Moreover, an analogous result is proved in the non-abelian case under additional assumptions. Finally, we utilize these results to obtain a generalization of a result of Cotlar-Ricabarra [1] concerning maximal almost periodicity in abelian topological groups.     

All Lobsters with Perfect Matchings are Graceful

Given a tree, T, consider one of its longest paths, P_T, not necessarily unique. We define T to be m–distant if no vertices of T are a distance greater than m away from P_T. We will show that all 3–distant graphs are graceful, providing they satisfy the following properties.

• 1.They have perfect matchings.
• 2.They can be constructed by attaching paths of length 2 to the vertices of a 1–distant tree (caterpillar), by the identification of their end vertices.

A consequence of this is that all 2–distant trees (lobsters) having perfect matchings are graceful.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

Maximal space regularity for abstract linear non-autonomous parabolic equations

The linear non-autonomous evolution equation $\text{u′(t) ? A(t) u(t) = ?(t), t ∈ [0, T]}$, with the initial datum u(0) = x, in the space C([0, T], E), where E is a Banach space and {A(t)} is a family of infinitesimal generators of bounded analytic semigroups is considered; the domains D(A(t)) are supposed constant in t and possibly not dense in E. Maximal regularity of the strict and classical solutions, i.e., regularity of u′ and A(·)u(·) with values in the interpolation spaces D_A(0)(θ, ∞) and D_A(0)(θ) between D(A(0)) and E, is studied. A characterization of such spaces in a concrete case is also given.     

On the Cauchy problem for some abstract nonlinear differential equations

In the present paper, we study the Cauchy problem in a Banach spaceE for an abstract nonlinear differential equation of form $$\frac{{d^2 u}}{{dt^2 }} = - A\frac{{du}}{{dt}} + B(t)u + f(t,W)$$ whereW = (A ₁(t)u,A ₂(t)u,?,A _?(t)u), (A _i (t),i = 1, 2, ?,?), (B(t),t ∈I = [0,b]) are families of closed operators defined on dense sets inE intoE, f is a given abstract nonlinear function onI ×E ^? intoE and ?A is a closed linear operator defined on dense set inE intoE, which generates a semi-group. Further, the existence and uniqueness of the solution of the considered Cauchy problem is studied for a wide class of the families (A _i(t),i = 1, 2, ?,?), (B(t),t ∈I). An application and some properties are also given for the theory of partial diferential equations.     

On the spectra of certain rooted trees

Let T be an unweighted tree with vertex root v which is the union of two trees T₁=(V₁,E₁), T₂=(V₂,E₂) such that V₁ ∩ V₂ = {v} and T₁ and T₂ have the property that the vertices in each of their levels have equal degree. We characterize completely the eigenvalues of the adjacency matrix and of the Laplacian matrix of T. They are the eigenvalues of symmetric tridiagonal matrices whose entries are given in terms of the vertex degrees. Moreover, we give some results about the multiplicity of the eigenvalues. Applications to some particular trees are developed.