On the nullity and the matching number of unicyclic graphs

Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu.     

On the nullity of a graph with cut-points

Let G be a simple graph of order n and A(G) be its adjacency matrix. The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in the spectrum of A(G). Denote by Ck and Lk the set of all connected graphs with k induced cycles and the set of line graphs of all graphs in Ck, respectively. In 1998, Sciriha [I. Sciriha, On singular line graphs of trees, Congr. Numer. 135 (1998) 73-91] show that the order of every tree whose line graph is singular is even. Then Gutman and Sciriha [I. Gutman, I. Sciriha, On the nullity of line graphs of trees, Discrete Math. 232 (2001) 35-45] show that the nullity set of L0 is {0,1}. In this paper, we investigate the nullity of graphs with cut-points and deduce some concise formulas. Then we generalize Scirihas' result, showing that the order of every graph G is even if such a graph G satisfies that G∈Ck and η(L(G))=k+1, and the nullity set of Lk is {0,1,…,k,k+1} for any given k, where L(G) denotes the line graph of the graph G.     

On the least eigenvalue of a unicyclic mixed graph

Using the result on Fiedler vectors of a simple graph, we obtain a property on the structure of the eigenvectors of a nonsingular unicyclic mixed graph corresponding to its least eigenvalue. With the property, we get some results on minimizing and maximizing the least eigenvalue over all nonsingular unicyclic mixed graphs on n vertices with fixed girth. In particular, the graphs which minimize and maximize, respectively, the least eigenvalue are given over all such graphs with girth 3.     

Maximum generic nullity of a graph

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree.     

On the line graph of the complete tripartite graph

It is shown that the line graph of the complete tripartite graphK_n,n,n is characterized by the spectrum of its adjacency matrix.     

On the depth of a planar graph

In this paper, we have defined the concept of the depth of a planar graph. We show that, if G is a simple finite planar graph with p vertices and q edges and q > 3(p ? 1) ? p/2^s?1, then the depth of G is at least equal to s.     

LARGEST EIGENVALUE OF A UNICYCLIC MIXED GRAPH

The graphs which maximize and minimize respectively the largest eigenvalue over all unicyclic mixed graphs U on n vertices are determined. The unicyclic mixed graphs U with the largest eigenvalue λ1 (U)=n or λ1 (U)∈ (n ,n 1] are characterized.     

On the nullity of graphs with pendent vertices

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. Cheng and Liu [B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007) 60-67] characterized the extremal graphs attaining the upper bound n-2 and the second upper bound n-3. In this paper, as the continuance of it, we determine the extremal graphs with pendent vertices achieving the third upper bound n-4 and fourth upper bound n-5. We then proceed recursively to construct all graphs with pendent vertices which satisfy η(G)>0. Our results provide a unified approach to determine n-vertex unicyclic (respectively, bicyclic and tricyclic) graphs which achieve the maximal and second maximal nullity and characterize n-vertex extremal trees attaining the second and third maximal nullity. As a consequence we, respectively, determine the nullity sets of trees, unicyclic graphs, bicyclic graphs and tricyclic graphs on n vertices.     

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.     

On the nullity of bipartite graphs

The nullity of a graph is defined to be the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. In this paper, we obtain the nullity set of bipartite graphs of order n, and characterize the bipartite graphs with nullity n-4 and the regular bipartite graphs with nullity n-6.     

On the nullity of bicyclic graphs

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. In this paper, we obtain the nullity set of bicyclic graphs of order n, and determine the bicyclic graphs with maximum nullity.     

On the nullity of tricyclic graphs

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. It is known that η(G)?n-2 if G is a simple graph on n vertices and G is not isomorphic to nK₁. The extremal graphs attaining the upper bound n-2 and the second upper bound n-3 have been obtained. In this paper, the graphs with nullity n-4 are characterized. Furthermore the tricyclic graphs with maximum nullity are discussed.     

On the design of networks with unicyclic connected components

This is a summary of my PhD thesis supervised by Walid Ben-Ameur and defended on September 29 2009, at Télécom SudParis. The thesis is written in French language and is available from the author upon request at makhlouf.hadji@it-sudparis.eu.     

On the clique number of the square of a line graph and its relation to maximum degree of the line graph

In 1985, Erdős and Nešetřil conjectured that the square of the line graph of a graph , that is, , can be colored with colors. This conjecture implies the weaker conjecture that the clique number of such a graph, that is, , is at most . In 2015, Śleszyńska-Nowak proved that . In this paper, we prove that . This theorem follows from our stronger result that where .     

First eigenvalue and first eigenvectors of a nonsingular unicyclic mixed graph

Let G be a mixed graph and let L(G) be the Laplacian matrix of the graph G. The first eigenvalue and the first eigenvectors of G are respectively referred to the least nonzero eigenvalue and the corresponding eigenvectors of L(G). In this paper we focus on the properties of the first eigenvalue and the first eigenvectors of a nonsingular unicyclic mixed graph (abbreviated to a NUM graph). We introduce the notion of characteristic set associated with the first eigenvectors, and then obtain some results on the sign structure of the first eigenvectors. By these results we determine the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order and fixed girth, and the unique graph which minimizes the first eigenvalue over all NUM graphs of fixed order.