The operad Lie is free

We show that the operad Lie is free as a non-symmetric operad. Then we study the generating series counting the operadic generators. We find a recursive formula for the coefficients of the series and show that the asymptotic density of the operadic generators is 1/e.     

Semistrict models of connected 3-types and Tamsamani’s weak 3-groupoids

Homotopy 3-types can be modelled algebraically by Tamsamani’s weak 3-groupoids as well as, in the path-connected case, by cat²-groups. This paper gives a comparison between the two models in the path-connected case. This leads to two different semistrict algebraic models of connected 3-types using Tamsamani’s model. Both are then related to Gray groupoids.     

New proofs for Levine’s theorems

Recently, Levine [9] expressed the vertex weighted complexity on spanning trees (with a fixed root) of the directed line graph of a digraph D in terms of the edge weighted complexity on spanning trees (with a fixed root) of D. We present new proofs for two Levine’s Theorems. Furthermore, we express the number of unicycles of the directed line graph of a digraph D in terms of the number of unicycles of D.     

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 .     

A lower bound for algebraic connectivity based on the connection-graph-stability method

This paper introduces the connection-graph-stability method and uses it to establish a new lower bound on the algebraic connectivity of graphs (the second smallest eigenvalue of the Laplacian matrix of the graph) that is sharper than the previously published bounds. The connection-graph-stability score for each edge is defined as the sum of the lengths of the shortest paths making use of that edge. We prove that the algebraic connectivity of the graph is bounded below by the size of the graph divided by the maximum connection-graph-stability score assigned to the edges.     

Geršgorin variations III: On a theme of Brualdi and Varga

Brualdi brought to Geršgorin Theory the concept that the digraph G(A) of a matrix A is important in studying whether A is singular. He proved, for example, that if, for every directed cycle of G(A), the product of the diagonal entries exceeds the product of the row sums of the moduli of the off-diagonal entries, then the matrix is nonsingular. We will show how, in polynomial time, that condition can be tested and (if satisfied) produce a diagonal matrix D, with positive diagonal entries, such that AD (where A is any nonnnegative matrix satisfying the conditions) is strictly diagonally dominant (and so, A is nonsingular). The same D works for all matrices satisfying the conditions. Varga raised the question of whether Brualdi’s conditions are sharp. Improving Varga’s results, we show, if G is scwaltcy (strongly connected with at least two cycles), and if the Brualdi conditions do not hold, how to construct (again in polynomial time) a complex matrix whose moduli satisfy the given specifications, but is singular.     

A NOTE ON MERRIS＇ CONJECTURES

The Merris‘ conjectures for threshold graphs and d-regular graphs are proved. Andthe one of the conjectures of Merris holds for trees is also proved.     

On the null-spaces of acyclic and unicyclic singular graphs

For acyclic and unicyclic graphs we determine a necessary and sufficient condition for a graph G to be singular. Further, it is shown that this characterization can be used to construct a basis for the null-space of G.     

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.     

A generalized characteristic polynomial of a graph having a semifree action

For an abelian group Γ, a formula to compute the characteristic polynomial of a Γ-graph has been obtained by Lee and Kim [Characteristic polynomials of graphs having a semi-free action, Linear algebra Appl. 307 (2005) 35-46]. As a continuation of this work, we give a computational formula for generalized characteristic polynomial of a Γ-graph when Γ is a finite group. Moreover, after showing that the reciprocal of the Bartholdi zeta function of a graph can be derived from the generalized characteristic polynomial of a graph, we compute the reciprocals of the Bartholdi zeta functions of wheels and complete bipartite graphs as an application of our formula.     

On the nullity of graphs with pendant trees

The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity.     

Sharp bounds on the spectral radius of a nonnegative matrix

We give upper and lower bounds for the spectral radius of a nonnegative matrix using its row sums and characterize the equality cases if the matrix is irreducible. Then we apply these bounds to various matrices associated with a graph, including the adjacency matrix, the signless Laplacian matrix, the distance matrix, the distance signless Laplacian matrix, and the reciprocal distance matrix. Some known results in the literature are generalized and improved.     

On the reduced signless Laplacian spectrum of a degree maximal graph

For a (simple) graph G, the signless Laplacian of G is the matrix A(G)+D(G), where A(G) is the adjacency matrix and D(G) is the diagonal matrix of vertex degrees of G; the reduced signless Laplacian of G is the matrix Δ(G)+B(G), where B(G) is the reduced adjacency matrix of G and Δ(G) is the diagonal matrix whose diagonal entries are the common degrees for vertices belonging to the same neighborhood equivalence class of G. A graph is said to be (degree) maximal if it is connected and its degree sequence is not majorized by the degree sequence of any other connected graph. For a maximal graph, we obtain a formula for the characteristic polynomial of its reduced signless Laplacian and use the formula to derive a localization result for its reduced signless Laplacian eigenvalues, and to compare the signless Laplacian spectral radii of two well-known maximal graphs. We also obtain a necessary condition for a maximal graph to have maximal signless Laplacian spectral radius among all connected graphs with given numbers of vertices and edges.     

Ordering of trees with fixed matching number by the Laplacian coefficients

Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix L(G), . Aleksandar Ili? [A. Ili?, Trees with minimal Laplacian coefficients, Comput. Math. Appl. 59 (2010) 2776-2783] identified n-vertex trees with given matching number q which simultaneously minimize all Laplacian coefficients. In this paper, we give another proof of this result. Generalizing the approach in the above paper, we determine n-vertex trees with given matching number q which have the second minimal Laplacian coefficients. We also identify the n-vertex trees with a perfect matching having the largest and the second largest Laplacian coefficients, respectively. Extremal values on some indices, such as Wiener index, modified hyper-Wiener index, Laplacian-like energy, incidence energy, of n-vertex trees with matching number q are obtained in this paper.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

On the distance and distance signless Laplacian spectral radii of bicyclic graphs

The unique graphs with minimum and second-minimum distance (distance signless Laplacian, respectively) spectral radii are determined among bicyclic graphs with fixed number of vertices.     

The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all graphs of a fixed order and a given vertex (edge) independence number or vertex (edge) cover number, and get some bounds for the vertex (edge) independence number, vertex (edge) cover number of a graph in terms of the least eigenvalue of the graph.