Search

Partition problems in graphs are extremely important in applications, as shown in the Data science and Machine learning literature. One approach is spectral partitioning based on a Fiedler vector, i.e., an eigenvector corresponding to the second smallest eigenvalue $a(G)$ of the Laplacian matrix $L_G$ of the graph $G$. This problem corresponds to the minimization of a quadratic form associated with $L_G$, under certain constraints involving the $\ell_2$-norm. We introduce and investigate a similar problem, but using the $\ell_1$-norm to measure distances. This leads to a new parameter $b(G)$ as the optimal value. We show that a well-known cut problem arises in this approach, namely the sparsest cut problem. We prove connectivity results and different bounds on this new parameter, relate to Fiedler theory and show explicit expressions for $b(G)$ for trees. We also comment on an $\ell_{\infty}$-norm version of the problem.

In this paper, closed formulas for the eigenvectors of a particular class of matrices generated by generalized permutation matrices, named generalized circulant matrices, are presented.

A g-circulant matrix of order n is defined as a matrix of order n where each row is a right cyclic shift in g-places to the preceding row. Using number theory, certain nonnegative g-circulant real matrices are constructed. In particular, it is shown that spectra with sufficient conditions so that it can be the spectrum of a real g-circulant matrix is not a spectrum with sufficient conditions so that it can be the spectrum of a real circulant matrix of the same order. The obtained results are applied to Nonnegative Inverse Eigenvalue Problem to construct nonnegative, g-circulant matrices with given appropriated spectrum. Moreover, nonnegative g-circulant matrices by blocks are also studied and in this case, their orders can be a multiple of a prime number.

Let $R$ be a Hermitian matrix. The energy of $R$, $\mathcal{E}(R)$, corresponds to the sum of the absolute values of its eigenvalues. In this work it is obtained two lower bounds for $\mathcal{E}(R).$ The first one generalizes a lower bound obtained by Mc Clellands for the energy of graphs in $1971$ to the case of Hermitian matrices and graphs with a given nullity. The second one generalizes a lower bound obtained by K. Das, S. A. Mojallal and I. Gutman in 2013 to symmetric non-negative matrices and graphs with a given nullity. The equality cases are discussed. These lower bounds are obtained for graphs with $m$ edges and some examples are provided showing that, some obtained bounds are incomparable with the known lower bound for the energy $2\sqrt{m}$. Another family of lower bounds are obtained from an increasing sequence of lower bounds for the spectral radius of a graph. The bounds are stated for singular and non-singular graphs.

Let $G$ be a simple graph. The signless Laplacian spread of $G$ is defined as the maximum distance of pairs of its signless Laplacian eigenvalues. This paper establishes some new bounds, both lower and upper, for the signless Laplacian spread. Several of these bounds depend on invariant parameters of the graph. We also use a minmax principle to find several lower bounds for this spectral invariant.

Let $G=\left( V\left( G\right) ,E\left( G\right) \right) $ be an $\left( n,m\right) $-graph and $X$ a nonempty proper subset of $V\left( G\right) $. Let $X^{c}=V\left( G\right) \backslash X$.\ The edge density of $X$ in $G$ is given by \begin{equation*} \rho _{G}\left( X\right) =\frac{n\left\vert E_{X}\left( G\right) \right\vert }{\left\vert X\right\vert \left\vert X^{c}\right\vert }, \end{equation*} where $E_{X}\left( G\right) \ $ is the set of edges in $G$ with one end in $% X $ and the other in $X^{c}$. The Laplacian spread of a graph is the difference between the greatest Laplacian eigenvalue and the algebraic connectivity. In this paper, we use the edge density of some nonempty proper subsets of vertices in $G$ to establish new lower bounds for the Laplacian spread. Also, using some known numerical inequalities some lower bounds for the Laplacian spread of a graph with a prescribed degree sequence are presented.

In this paper we deal with circulant and partitioned into $n$-by-$n$ circulant blocks matrices and introduce spectral results concerning this class of matrices. The problem of finding lists of complex numbers corresponding to a set of eigenvalues of a nonnegative block matrix with circulant blocks is treated. Along the paper we call realizable list if its elements are the eigenvalues of a nonnegative matrix. The Guo's index $\lambda_0$ of a realizable list is the minimum spectral radius such that the list (up to the initial spectral radius) together with $\lambda_0$ is realizable. The Guo's index of block circulant matrices with circulant blocks is obtained, and in consequence, necessary and sufficient conditions concerning the NIEP, Nonnegative Inverse Eigenvalue Problem, for the realizability of some spectra are given.

A square matrix of order n with $n\geq 2$ is called permutative matrix when all its rows (up to the frst one) are permutations of precisely its frst row. In this paper recalling spectral results for partitioned into $2$-by-$2$ symmetric blocks matrices sufcient conditions on a given complex list to be the list of the eigenvalues of a nonnegative permutative matrix are given. In particular, we study NIEP and PNIEP when some complex elements into the considered lists have no zero imaginary part. Realizability regions for nonnegative permutative matrices are obtained.

A square matrix of order $n$ with $n\geq 2$ is called a \textit{permutative matrix} or permutative when all its rows (up to the first one) are permutations of precisely its first row. In this paper, the spectra of a class of permutative matrices are studied. In particular, spectral results for matrices partitioned into $2$-by-$2$ symmetric blocks are presented and, using these results sufficient conditions on a given list to be the list of eigenvalues of a nonnegative permutative matrix are obtained and the corresponding permutative matrices are constructed. Guo perturbations on given lists are exhibited.