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 .     

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.     

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).     

On the spectral radius of trees with fixed diameter

Let T_{(n, d)} be the set of trees on n vertices with diameter d. In this paper, the first spectral radii of trees in the set T_{(n, d)} (3 ? d ? n − 4) are characterized.     

r-Strong edge colorings of graphs

Let G be a graph and for any natural number r, denotes the minimum number of colors required for a proper edge coloring of G in which no two vertices with distance at most r are incident to edges colored with the same set of colors. In [Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623-626] it has been proved that for any tree T with at least three vertices, . Here we generalize this result and show that . Moreover, we show that if for any two vertices u and v with maximum degree d(u,v)?3, then . Also for any tree T with Δ(T)?3 we prove that . Finally, it is shown that for any graph G with no isolated edges, .     

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.     

Non-uniform Turán-type problems

Given positive integers n,k,t, with 2?k?n, and t<2^k, let m(n,k,t) be the minimum size of a family F of (nonempty distinct) subsets of [n] such that every k-subset of [n] contains at least t members of F, and every (k-1)-subset of [n] contains at most t-1 members of F. For fixed k and t, we determine the order of magnitude of m(n,k,t). We also consider related Turán numbers T_?r(n,k,t) and T_r(n,k,t), where T_?r(n,k,t) (T_r(n,k,t)) denotes the minimum size of a family such that every k-subset of [n] contains at least t members of F. We prove that T_?r(n,k,t)=(1+o(1))T_r(n,k,t) for fixed r,k,t with and n→∞.     

Total domination and total domination subdivision number of a graph and its complement

A set S of vertices of a graph G=(V,E) with no isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγ_t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision numbersd_γt(G) is the minimum number of edges that must be subdivided in order to increase the total domination number. We consider graphs of order n?4, minimum degree δ and maximum degree Δ. We prove that if each component of G and has order at least 3 and , then and if each component of G and has order at least 2 and at least one component of G and has order at least 3, then . We also give a result on stronger than a conjecture by Harary and Haynes.     

On Estrada index of trees

Let G be a graph on n vertices, and let λ₁,λ₂,…,λ_n be its eigenvalues. The Estrada index is defined as . We determine the unique tree with maximum Estrada index among the trees on n vertices with given matching number, and the unique tree with maximum Estrada index among the trees on n vertices with fixed diameter. For , we also determine the tree with maximum Estrada index among the trees on n vertices with maximum degree Δ. It gives a partial solution to the conjecture proposed by Ili? and Stevanovi? in Ref. [14].     

Spanning multi-paths in hypercubes

A set A of vertices of a hypercube is called balanced if . We prove that for every natural number n there exists a natural number π₁(n) such that for every hypercube Q with dim(Q)?π₁(n) there exists a family of pairwise vertex-disjoint paths P_i between A_i and B_i for i=1,2,…,n with if and only if {A_i,B_i∣i=1,2,…,n} is a balanced set.     

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 .     

On the skew energy of orientations of hypercubes

Let D be a digraph of order n and λ₁,λ₂,…,λ_n denote all the eigenvalues of the skew-adjacency matrix of D. The skew energy E_S(D) of D is defined as . In this paper, it is proved that for any positive integer k≥3, there exists a k-regular graph of order n having an orientation D with . This work positively answers a problem proposed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a digraph, Linear Algebra Appl. 432 (2010) 1825-1835]. In addition, a digraph is also constructed such that its skew energy is the same as the energy of its underlying graph.     

Extremal problems on detectable colorings of trees

Let G be a connected graph of order 3 or more and let be a coloring of the edges of G (where adjacent edges may be colored the same). For each vertex v of G, the color code of v is the k-tuple c(v)=(a₁,a₂,…,a_k), where a_i is the number of edges incident with v that are colored i (1?i?k). The coloring c is called detectable if distinct vertices have distinct color codes; while the detection number det(G) of G is the minimum positive integer k for which G has a detectable k-coloring. For each integer n?3, let D_T(n) be the maximum detection number among all trees of order n and d_T(n) the minimum detection number among all trees of order n. The numbers D_T(n) and d_T(n) are determined for all integers n?3. Furthermore, it is shown that for integers k?2 and n?3, there exists a tree T of order n having det(T)=k if and only if d_T(n)?k?D_T(n).     

On defining numbers of circular complete graphs

Let d(σ) stand for the defining number of the colouring σ. In this paper we consider and for the onto χ-colourings γ of the circular complete graph K_n,d. In this regard we obtain a lower bound for d^min(K_n,d) and we also prove that this parameter is asymptotically equal to χ-1. Also, we show that when χ?4 and s≠0 then d^max(K_χd-s,d)=χ+2s-3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G.     

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.     

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.     

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.     

Distance irredundance and connected domination numbers of a graph

Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γ_k(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number ir_k(G). The authors prove that if an ir_k-set X is a k-independent set of G, then , and that for k?2, if ir_k(G)=1, if ir_k(G) is odd, and if ir_k(G) is even, which generalize some known results.     

Asymptotic properties of generalized Laguerre orthogonal polynomials

In the present paper we deal with the polynomials L_n^(α,M,N) (x) orthogonal with respect to the Sobolev inner product

     

On conjugate adjacency matrices of a graph

Let G be a simple graph of order n. Let and , where a and b are two nonzero integers and m is a positive integer such that m is not a perfect square. We say that A^c=[c_ij] is the conjugate adjacency matrix of the graph G if c_ij=c for any two adjacent vertices i and j, for any two nonadjacent vertices i and j, and c_ij=0 if i=j. Let P_G(λ)=|λI-A| and denote the characteristic polynomial and the conjugate characteristic polynomial of G, respectively. In this work we show that if then , where denotes the complement of G. In particular, we prove that if and only if P_G(λ)=P_H(λ) and . Further, let P^c(G) be the collection of conjugate characteristic polynomials of vertex-deleted subgraphs G_i=G?i(i=1,2,…,n). If P^c(G)=P^c(H) we prove that , provided that the order of G is greater than 2.