On the maximum positive semi-definite nullity and the cycle matroid of graphs.
Let be a connected graph of order and a unicyclic graph with the same order. We firstly give a sharp bound for , the multiplicity of a Laplacian eigenvalue of . As a straightforward result, . We then provide two graph operations (i.e., grafting and shifting) on graph for which the value of is nondecreasing. As applications, we get the distribution of for unicyclic graphs on vertices. Moreover, for the two largest possible values of , the corresponding graphs are completely...
In this paper we investigate the effect on the multiplicity of Laplacian eigenvalues of two disjoint connected graphs when adding an edge between them. As an application of the result, the multiplicity of 1 as a Laplacian eigenvalue of trees is also considered.
Let be a 3-connected planar graph, with . Let be a symmetric matrix with exactly one negative eigenvalue (of multiplicity 1), such that for with , if and are adjacent then and if and are nonadjacent then , and such that has rank . Then the null space of gives an embedding of in as follows: let be a basis of , and for let ; then , and embeds in such that connecting, for any two adjacent vertices , the points and by a shortest geodesic on , gives...
As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition,...
The zero forcing number and the positive zero forcing number of a graph are two graph parameters that arise from two types of graph colourings. The zero forcing number is an upper bound on the minimum number of induced paths in the graph that cover all the vertices of the graph, while the positive zero forcing number is an upper bound on the minimum number of induced trees in the graph needed to cover all the vertices in the graph. We show that for a block-cycle graph the zero forcing number equals...
Kragujevac (M. L. Kragujevac: On the Laplacian energy of a graph, Czech. Math. J. 56(131) (2006), 1207–1213) gave the definition of Laplacian energy of a graph and proved ; equality holds if and only if . In this paper we consider the relation between the Laplacian energy and the chromatic number of a graph and give an upper bound for the Laplacian energy on a connected graph.
Let G be a mixed graph. We discuss the relation between the second largest eigenvalue λ₂(G) and the second largest degree d₂(G), and present a sufficient condition for λ₂(G) ≥ d₂(G).
A graph is determined by its signless Laplacian spectrum if no other non-isomorphic graph has the same signless Laplacian spectrum (simply is ). Let denote the -shape tree obtained by identifying the end vertices of three paths , and . We prove that its all line graphs except () are , and determine the graphs which have the same signless Laplacian spectrum as . Let be the maximum signless Laplacian eigenvalue of the graph . We give the limit of , too.