A lower bound for the spectral radius of a digraph

We show that the spectral radius ρ(D) of a digraph D with n vertices and c₂ closed walks of length 2 satisfies Moreover, equality occurs if and only if D is the symmetric digraph associated to a -regular graph, plus some arcs that do not belong to cycles. As an application of this result, we construct new sharp upper bounds for the low energy of a digraph, which extends Koolen and Moulton bounds of the energy to digraphs.     

Note on the energy of regular graphs

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ₁ is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .     

Solution to a conjecture on the maximal energy of bipartite bicyclic graphs

The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let C_n denote the cycle of order n and the graph obtained from joining two cycles C₆ by a path P_n-12 with its two leaves. Let B_n denote the class of all bipartite bicyclic graphs but not the graph R_a,b, which is obtained from joining two cycles C_a and C_b (a,b≥10 and ) by an edge. In [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002-1005], Gutman and Vidovi? conjectured that the bicyclic graph with maximal energy is , for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87-98], Li and Zhang showed that the conjecture is true for graphs in the class B_n. However, they could not determine which of the two graphs R_a,b and has the maximal value of energy. In [B. Furtula, S. Radenkovi?, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431-433], numerical computations up to a+b=50 were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of R_a,b, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open.     

Complete solution to a problem on the maximal energy of unicyclic bipartite graphs

The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Denote by C_n the cycle, and the unicyclic graph obtained by connecting a vertex of C₆ with a leaf of P_n-6. Caporossi et al. conjectured that the unicyclic graph with maximal energy is for n=8,12,14 and n≥16. In Hou et al. (2002) [Y. Hou, I. Gutman, C. Woo, Unicyclic graphs with maximal energy, Linear Algebra Appl. 356 (2002) 27-36], the authors proved that is maximal within the class of the unicyclic bipartite n-vertex graphs differing from C_n. And they also claimed that the energies of C_n and is quasi-order incomparable and left this as an open problem. In this paper, by utilizing the Coulson integral formula and some knowledge of real analysis, especially by employing certain combinatorial techniques, we show that the energy of is greater than that of C_n for n=8,12,14 and n≥16, which completely solves this open problem and partially solves the above conjecture.     

Remarks on Hardy spaces defined by non-smooth approximate identity

We study in this paper some relations between Hardy spaces which are defined by non-smooth approximate identity ?(x), and the end-point Triebel-Lizorkin spaces (1?q?∞). First, we prove that for compact ? which satisfies a slightly weaker condition than Fefferman and Stein's condition. Then we prove that non-trivial Hardy space defined by approximate identity ? must contain Besov space . Thirdly, we construct certain functions and a function such that Daubechies wavelet function but .     

Spectral radius of graphs with given matching number

In this paper, we show that of all graphs of order n with matching number β, the graphs with maximal spectral radius are K_n if n = 2β or 2β + 1; if 2β + 2 ? n < 3β + 2; or if n = 3β + 2; if n > 3β + 2, where is the empty graph on t vertices.     

Cospectral graphs and the generalized adjacency matrix

Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value of y. We call such graphs -cospectral. It follows that is a rational number, and we prove existence of a pair of -cospectral graphs for every rational . In addition, we generate by computer all -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of -cospectral graphs for all rational , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of , and by computer we find all such pairs of -cospectral graphs on at most eleven vertices.     

Locally compact abelian groups admitting non-trivial quasi-convex null sequences

In this paper, we show that, for every locally compact abelian group G, the following statements are equivalent:

(i)

G contains no sequence such that {0}∪{±x_n∣n∈N} is infinite and quasi-convex in G, and x_n?0;

(ii)

one of the subgroups {g∈G∣2g=0} or {g∈G∣3g=0} is open in G;

(iii)

G contains an open compact subgroup of the form or for some cardinal κ.

     

Efficient algorithms for robust generalized cross-validation spline smoothing

Generalized cross-validation (GCV) is a widely used parameter selection criterion for spline smoothing, but it can give poor results if the sample size n is not sufficiently large. An effective way to overcome this is to use the more stable criterion called robust GCV (RGCV). The main computational effort for the evaluation of the GCV score is the trace of the smoothing matrix, , while the RGCV score requires both and . Since 1985, there has been an efficient O(n) algorithm to compute . This paper develops two pairs of new O(n) algorithms to compute and , which allow the RGCV score to be calculated efficiently. The algorithms involve the differentiation of certain matrix functionals using banded Cholesky decomposition.     

Further results on the least eigenvalue of connected graphs

In this paper, we identify within connected graphs of order n and size n+k (with and ) the graphs whose least eigenvalue is minimal. It is also observed that the same graphs have the largest spectral spread if n is large enough.     

Strong convergence of the empirical distribution of eigenvalues of sample covariance matrices with a perturbation matrix

Let , where is a random symmetric matrix, a random symmetric matrix, and with being independent real random variables. Suppose that , and are independent. It is proved that the empirical spectral distribution of the eigenvalues of random symmetric matrices converges almost surely to a non-random distribution.     

A priori estimate for a family of semi-linear elliptic equations with critical nonlinearity

We consider positive solutions of on B₁ (n?5) where μ and K>0 are smooth functions on B₁. If K is very sub-harmonic at each critical point of K in B2/3 and the maximum of u in is comparable to its maximum over , then all positive solutions are uniformly bounded on . As an application, a priori estimate for solutions of equations defined on Sn is derived.     

Uniformly minimum variance nonnegative quadratic unbiased estimation in a generalized growth curve model

Consider the generalized growth curve model subject to R(X_m)⊆?⊆R(X₁), where B_i are the matrices of unknown regression coefficients, and E=(ε₁,…,ε_s)^′ and are independent and identically distributed with the same first four moments as a random vector normally distributed with mean zero and covariance matrix Σ. We derive the necessary and sufficient conditions under which the uniformly minimum variance nonnegative quadratic unbiased estimator (UMVNNQUE) of the parametric function with C≥0 exists. The necessary and sufficient conditions for a nonnegative quadratic unbiased estimator with of to be the UMVNNQUE are obtained as well.     

Inequalities of Nordhaus-Gaddum type for doubly connected domination number

A set S of vertices of a connected graph G is a doubly connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V−S are connected. The doubly connected domination numberγ_cc(G) is the minimum size of such a set. We prove that when G and are both connected of order n, and we describe the two infinite families of extremal graphs achieving the bound.     

Markov interlacing property for exponential polynomials

Let Un be an extended Tchebycheff system on the real line. Given a point , where x₁<?<xn, we denote by the polynomial from Un, which has zeros x₁,…,xn. (It is uniquely determined up to multiplication by a constant.) The system Un has the Markov interlacing property (M) if the assumption that and interlace implies that the zeros of and interlace strictly, unless . We formulate a general condition which ensures the validity of the property (M) for polynomials from Un. We also prove that the condition is satisfied for some known systems, including exponential polynomials and . As a corollary we obtain that property (M) holds true for Müntz polynomials , too.     

The Laplacian spectral radius of some bipartite graphs

In this paper, we study the largest Laplacian spectral radius of the bipartite graphs with n vertices and k cut edges and the bicyclic bipartite graphs, respectively. Identifying the center of a star K_1,k and one vertex of degree n of K_m,n, we denote by the resulting graph. We show that the graph (1?k?n-4) is the unique graph with the largest Laplacian spectral radius among the bipartite graphs with n vertices and k cut edges, and (n?7) is the unique graph with the largest Laplacian spectral radius among all the bicyclic bipartite graphs.     

The least eigenvalue of the complements of trees

Let be the set of the complements of trees of order n. In this paper, we characterize the unique graph whose least eigenvalue attains the minimum among all graphs in .     

The topology of the monodromy map of a second order ODE

We consider the following question: given A∈SL(2,R), which potentials q for the second order Sturm-Liouville problem have A as its Floquet multiplier? More precisely, define the monodromy map μ taking a potential q∈L²([0,2π]) to , the lift to the universal cover of SL(2,R) of the fundamental matrix map ,

     

Compactifications of the homeomorphism group of a graph

Let Γ be a countable locally finite graph and let H(Γ) and H₊(Γ) denote the homeomorphism group of Γ with the compact-open topology and its identity component. These groups can be embedded into the space of all closed sets of Γ×Γ with the Fell topology, which is compact. Taking closure, we have natural compactifications and . In this paper, we completely determine the topological type of the pair and give a necessary and sufficient condition for this pair to be a (Q,s)-manifold. The pair is also considered for simple examples, and in particular, we find that has homotopy type of RP³. In this investigation we point out a certain inaccuracy in Sakai-Uehara's preceding results on for finite graphs Γ.