On the Laplacian spectral radii of trees

Let Δ(T) and μ(T) denote the maximum degree and the Laplacian spectral radius of a tree T, respectively. Let T_n be the set of trees on n vertices, and . In this paper, we determine the two trees which take the first two largest values of μ(T) of the trees T in when . And among the trees in , the tree which alone minimizes the Laplacian spectral radius is characterized. We also prove that for two trees T₁ and T₂ in , if Δ(T₁)>Δ(T₂) and , then μ(T₁)>μ(T₂). As an application of these results, we give a general approach about extending the known ordering of trees in T_n by their Laplacian spectral radii.     

Perfectness and imperfectness of unit disk graphs on triangular lattice points

Given a finite set of 2-dimensional points P⊆R² and a positive real d, a unit disk graph, denoted by (P,d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is less than or equal to d. Given a pair of non-negative integers m and n, P(m,n) denotes a subset of 2-dimensional triangular lattice points defined by where . Let T_m,n(d) be a unit disk graph defined on a vertex set P(m,n) and a positive real d. Let be the kth power of T_m,n(1).In this paper, we show necessary and sufficient conditions that [ is perfect] and/or [ is perfect], respectively. These conditions imply polynomial time approximation algorithms for multicoloring (T_m,n(d),w) and .     

Integers with dense divisors 2

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are t-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?t. Let D(x,t) be the number of positive integers not exceeding x whose divisors are t-dense. We show that for x?3, and , we have , where , and d(w) is a continuous function which satisfies d(w)?1/w for w?1. We also consider other counting functions closely related to D(x,t).     

Eigenvalues and degree deviation in graphs

Let G be a graph with n vertices and m edges and let μ(G) = μ₁(G) ? ? ? μ_n(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑_u∈V(G)∣d(u)-2m/n∣. We prove that

     

Boundedness of solutions for asymmetric Duffing equations

In this paper, we are concerned with the boundedness of all the solutions and the existence of quasiperiodic solutions for some Duffing equations , where e(t) is of period 1, and g : R → R possesses the characters: g(x) is superlinear when x ? d₀, d₀ is a positive constant and g(x) is semilinear when x ? 0.     

Mutually independent bipanconnected property of hypercube

A graph is denoted by G with the vertex set V(G) and the edge set E(G). A path P = 〈v₀, v₁, … , v_m〉 is a sequence of adjacent vertices. Two paths with equal length P₁ = 〈 u₁, u₂, … , u_m〉 and P₂ = 〈 v₁, v₂, … , v_m〉 from a to b are independent if u₁ = v₁ = a, u_m = v_m = b, and u_i ≠ v_i for 2 ? i ? m − 1. Paths with equal length from a to b are mutually independent if they are pairwisely independent. Let u and v be two distinct vertices of a bipartite graph G, and let l be a positive integer length, d_G(u, v) ? l ? ∣V(G) − 1∣ with (l − d_G(u, v)) being even. We say that the pair of vertices u, v is (m, l)-mutually independent bipanconnected if there exist m mutually independent paths with length l from u to v. In this paper, we explore yet another strong property of the hypercubes. We prove that every pair of vertices u and v in the n-dimensional hypercube, with d_Qn(u,v)?n-1, is (n − 1, l)-mutually independent bipanconnected for every with (l-d_Qn(u,v)) being even. As for d_Qn(u,v)?n-2, it is also (n − 1, l)-mutually independent bipanconnected if l?d_Qn(u,v)+2, and is only (l, l)-mutually independent bipanconnected if l=d_Qn(u,v).     

Lower bounds of Copson type for Hausdorff matrices

Let 1 ? p ? ∞, 0 < q ? p, and A = (a_n,k)_n,k?0 ? 0. Denote by L_p,q(A) the supremum of those L satisfying the following inequality:

     

The ordering of trees and connected graphs by algebraic connectivity

In this paper, we first determine that the first four trees of order n?9 with the smallest algebraic connectivity are P_n,Q_n,W_n and Z_n with α(P_n)<α(Q_n)<α(W_n)<α(Z_n)<α(T), where T is any tree of order n other than P_n, Q_n, W_n, and Z_n. Then we consider the effect on the Laplacian eigenvalues of connected graphs by suitably adding edges. By using these results and methods, we finally determine that the first six connected graphs of order n?9 with the smallest algebraic connectivity are and , with , where G is any connected graph of order n other than P_n, Q_n, , W_n, and .     

Balanced Leonard pairs

Let K denote a field, and let V denote a vector space over K with finite positive dimension. By a Leonard pair on V we mean an ordered pair of linear transformations A : V → V and A^∗ : V → V that satisfy the following two conditions:

(i)

There exists a basis for V with respect to which the matrix representing A is irreducible tridiagonal and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A^∗ is irreducible tridiagonal and the matrix representing A is diagonal.

Let (respectively v₀, v₁, … , v_d) denote a basis for V that satisfies (i) (respectively (ii)). For 0 ? i ? d, let a_i denote the coefficient of , when we write as a linear combination of , and let denote the coefficient of v_i, when we write A^∗v_i as a linear combination of v₀, v₁, … , v_d.In this paper we show a₀ = a_d if and only if . Moreover we show that for d ? 1 the following are equivalent; (i) a₀ = a_d and a₁ = a_d−1; (ii) and ; (iii) a_i = a_d−i and for 0 ? i ? d. These give a proof of a conjecture by the second author. We say A, A^∗ is balanced whenever a_i = a_d−i and for 0 ? i ? d. We say A,A^∗ is essentially bipartite (respectively essentially dual bipartite) whenever a_i (respectively ) is independent of i for 0 ? i ? d. Observe that if A, A^∗ is essentially bipartite or dual bipartite, then A, A^∗ is balanced. For d ≠ 2, we show that if A, A^∗ is balanced then A, A^∗ is essentially bipartite or dual bipartite.     

Integers with dense divisors

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are y-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?y. Let D(x,y,z) be the number of positive integers not exceeding x whose divisors are y-dense and whose prime divisors are bigger than z, and let , and . We show that is equivalent, in a large region, to a function d(u,v) which satisfies a difference-differential equation. Using that equation we find that d(u,v)?(1−u/v)/(u+1) for v?3+ε. Finally, we show that d(u,v)=e^−γd(u)+O(1/v), where γ is Euler's constant and d(u)∼x⁻¹D(x,y,1), for fixed u. This leads to a new estimate for d(u).     

Approximation numbers for the finite sections of Toeplitz operators with piecewise continuous symbols

In this paper we discuss the asymptotic distribution of the approximation numbers of the finite sections for a Toeplitz operator T(a)∈L(?p), 1<p<∞, where a is a piecewise continuous function on the unit circle. We prove that the behavior of the approximation numbers of the finite sections Tn(a)=PnT(a)Pn depends heavily on the Fredholm properties of the operators T(a) and . In particular, if the operators T(a) and are Fredholm on ?p, then the approximation numbers of Tn(a) have the so-called k-splitting property. But, in contrast with the case of continuous symbols, the splitting number k is in general larger than .     

The six classes of trees with the largest algebraic connectivity

In this paper, we study the algebraic connectivity α(T) of a tree T. We introduce six Classes (C1)-(C6) of trees of order n, and prove that if T is a tree of order n?15, then if and only if , where the equality holds if and only if T is a tree in the Class (C6). At the same time we give a complete ordering of the trees in these six classes by their algebraic connectivity. In particular, we show that α(T_i)>α(T_j) if 1?i<j?6 and T_i is any tree in the Class (Ci) and T_j is any tree in the Class (Cj). We also give the values of the algebraic connectivity of the trees in these six classes. As a technique used in the proofs of the above mentioned results, we also give a complete characterization of the equality case of a well-known relation between the algebraic connectivity of a tree T and the Perron value of the bottleneck matrix of a Perron branch of T.     

Transition matrices for well-conditioned Markov chains

Let T∈R^n×n be an irreducible stochastic matrix with stationary distribution vector π. Set A = I − T, and define the quantity , where A_j, j = 1, … , n, are the (n − 1) × (n − 1) principal submatrices of A obtained by deleting the jth row and column of A. Results of Cho and Meyer, and of Kirkland show that κ₃ provides a sensitive measure of the conditioning of π under perturbation of T. Moreover, it is known that .In this paper, we investigate the class of irreducible stochastic matrices T of order n such that , for such matrices correspond to Markov chains with desirable conditioning properties. We identify some restrictions on the zero-nonzero patterns of such matrices, and construct several infinite classes of matrices for which κ₃ is as small as possible.     

A family of invariants of rooted forests

Let A be a commutative k-algebra over a field of k and Ξ a linear operator defined on A. We define a family of A-valued invariants Ψ for finite rooted forests by a recurrent algorithm using the operator Ξ and show that the invariant Ψ distinguishes rooted forests if (and only if) it distinguishes rooted trees T, and if (and only if) it is finer than the quantity α(T)=|Aut(T)| of rooted trees T. We also consider the generating function with , where is the set of rooted trees with n vertices. We show that the generating function U(q) satisfies the equation . Consequently, we get a recurrent formula for U_n (n?1), namely, U₁=Ξ(1) and U_n=ΞS_n−1(U₁,U₂,…,U_n−1) for any n?2, where are the elementary Schur polynomials. We also show that the (strict) order polynomials and two well-known quasi-symmetric function invariants of rooted forests are in the family of invariants Ψ and derive some consequences about these well-known invariants from our general results on Ψ. Finally, we generalize the invariant Ψ to labeled planar forests and discuss its certain relations with the Hopf algebra in Foissy (Bull. Sci. Math. 126 (2002) 193) spanned by labeled planar forests.     

A spectral condition for odd cycles in graphs

Let G be a graph of sufficiently large order n, and let the largest eigenvalue μ(G) of its adjacency matrix satisfies . Then G contains a cycle of length t for every t?n/320This condition is sharp: the complete bipartite graph T₂(n) with parts of size ⌊n/2⌋ and ⌈n/2⌉ contains no odd cycles and its largest eigenvalue is equal to .This condition is stable: if μ(G) is close to and G fails to contain a cycle of length t for some t?n/321, then G resembles T₂(n).     

Some relations between rank of a graph and its complement

Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that .