Search

In 2010, Butler introduced the unfolding operation on a bipartite graph to produce two bipartite graphs, which are cospectral for the adjacency and the normalized Laplacian matrices. In this article, we describe how the idea of unfolding a bipartite graph with respect to another bipartite graph can be extended to nonbipartite graphs. In particular, we describe how unfoldings involving reflexive bipartite, semi-reflexive bipartite, and multipartite graphs are used to obtain cospectral nonisomorphic graphs for the adjacency matrix., Comment: arXiv admin note: text overlap with arXiv:2110.09034

A complex unit gain graph ($ \mathbb{T} $-gain graph), $ \Phi=(G, \varphi) $ is a graph where the gain function $ \varphi $ assigns a unit complex number to each orientation of an edge of $ G $ and its inverse is assigned to the opposite orientation. The associated adjacency matrix $ A(\Phi) $ is defined canonically. The energy $ \mathcal{E}(\Phi) $ of a $ \mathbb{T} $-gain graph $ \Phi $ is the sum of the absolute values of all eigenvalues of $ A(\Phi) $. For any connected triangle-free $ \mathbb{T} $-gain graph $ \Phi $ with the minimum vertex degree $ \delta$, we establish a lower bound $ \mathcal{E}(\Phi)\geq 2\delta$ and characterize the equality. Then, we present a relationship between the characteristic and the matching polynomial of $ \Phi $. Using this, we obtain an upper bound for the energy $ \mathcal{E}(\Phi)\leq 2\mu\sqrt{2\Delta_e+1} $ and characterize the classes of graphs for which the bound sharp, where $ \mu$ and $ \Delta_e$ are the matching number and the maximum edge degree of $ \Phi $, respectively. Further, for any unicyclic graph $ G $, we study the gains for which the gain energy $ \mathcal{E}(\Phi) $ attains the maximum/minimum among all $ \mathbb{T} $-gain graphs defined on $G$.

In this article, we show that the generalized tree shift operation increases the distance spectral radius, distance signless Laplacian spectral radius, and the $D_\alpha$-spectral radius of complements of trees. As a consequence of this result, we correct an ambiguity in the proofs of some of the known results.

The eccentricity matrix of a connected graph $G$, denoted by $\mathcal{E}(G)$, is obtained from the distance matrix of $G$ by keeping the largest nonzero entries in each row and each column, and leaving zeros in the remaining ones. The $\mathcal{E}$-eigenvalues of $G$ are the eigenvalues of $\mathcal{E}(G)$, in which the largest one is the $\mathcal{E}$-spectral radius of $G$. The $\mathcal{E}$-energy of $G$ is the sum of the absolute values of all $\mathcal{E}$-eigenvalues of $G$. In this article, we study some of the extremal problems for eccentricity matrices of complements of trees and characterize the extremal graphs. First, we determine the unique tree whose complement has minimum (respectively, maximum) $\mathcal{E}$-spectral radius among the complements of trees. Then, we prove that the $\mathcal{E}$-eigenvalues of the complement of a tree are symmetric about the origin. As a consequence of these results, we characterize the trees whose complement has minimum (respectively, maximum) least $\mathcal{E}$-eigenvalues among the complements of trees. Finally, we discuss the extremal problems for the second largest $\mathcal{E}$-eigenvalue and the $\mathcal{E}$-energy of complements of trees and characterize the extremal graphs. As an application, we obtain a Nordhaus-Gaddum type lower bounds for the second largest $\mathcal{E}$-eigenvalue and $\mathcal{E}$-energy of a tree and its complement., Comment: 18 pages. Preliminary version

The eccentricity matrix of a connected graph $G$, denoted by $\mathcal{E}(G)$, is obtained from the distance matrix of $G$ by keeping the largest nonzero entries in each row and each column and leaving zeros in the remaining ones. The eigenvalues of $\mathcal{E}(G)$ are the $\mathcal{E}$-eigenvalues of $G$. The eccentricity energy (or the $\mathcal{E}$-energy) of $G$ is the sum of the absolute values of all $\mathcal{E}$-eigenvalues of $G$. In this article, we determine the unique tree with the minimum second largest $\mathcal{E}$-eigenvalue among all trees on $n$ vertices other than the star. Also, we characterize the trees with minimum $\mathcal{E}$-energy among all trees on $n$ vertices., Comment: 18 Pages

Let $T$ be a tree on $n$ vertices whose edge weights are positive definite matrices of order $s$. The squared distance matrix of $T$, denoted by $\Delta$, is the $ns \times ns$ block matrix with $\Delta_{ij}=d(i,j)^2$, where $d(i,j)$ is the sum of the weights of the edges in the unique $(i,j)$-path. In this article, we obtain a formula for the determinant of $\Delta$ and find ${\Delta}^{-1}$ under some conditions., Comment: Preliminary version. Comments are welcome. 17 pages

A signed graph $\Sigma = (G, \sigma)$ is a graph where the function $\sigma$ assigns either $1$ or $-1$ to each edge of the simple graph $G$. The adjacency matrix of $\Sigma$, denoted by $A(\Sigma)$, is defined canonically. In a recent paper, Wang et al. extended the eigenvalue bounds of Hoffman and Cvetkovi\'{c} for the signed graphs. They proposed an open problem related to the balanced clique number and the largest eigenvalue of a signed graph. We solve a strengthened version of this open problem. As a byproduct, we give alternate proofs for some of the known classical bounds for the least eigenvalues of the unsigned graphs. We extend the Tur\'{a}n's inequality for the signed graphs. Besides, we study the Bollob\'{a}s and Nikiforov conjecture for the signed graphs and show that the conjecture need not be true for the signed graphs. Nevertheless, the conjecture holds for signed graphs under some assumptions. Finally, we study some of the relationships between the number of signed walks and the largest eigenvalue of a signed graph., Comment: Updated version. Title is changed. Typos are fixed

The \textit{eccentricity matrix} $\mathcal{E}(G)$ of a connected graph $G$ is obtained from the distance matrix of $G$ by keeping the largest non-zero entries in each row and each column, and leaving zeros in the remaining ones. The eigenvalues of $\mathcal{E}(G)$ are the \textit{$\mathcal{E}$-eigenvalues} of $G$. In this article, we find the inertia of the eccentricity matrices of trees. Interestingly, any tree on more than $4$ vertices with odd diameter has two positive and two negative $\mathcal{E}$-eigenvalues (irrespective of the structure of the tree). A tree with even diameter has the same number of positive and negative $\mathcal{E}$-eigenvalues, which is equal to the number of 'diametrically distinguished' vertices (see Definition 3.1). Besides we prove that the spectrum of the eccentricity matrix of a tree is symmetric with respect to the origin if and only if the tree has odd diameter. As an application, we characterize the trees with three distinct $\mathcal{E}$-eigenvalues., Comment: Some of the typos are fixed. Comments are welcome!

In this article, we construct bipartite graphs which are cospectral for both the adjacency and normalized Laplacian matrices using partitioned tensor product. This extends the construction of Ji, Gong, and Wang \cite{ji-gong-wang}. Our proof of the cospectrality of adjacency matrices simplifies the proof of the bipartite case of Godsil and McKay's construction \cite{godsil-mckay-1976}, and shows that the corresponding normalized Laplacian matrices are also cospectral. We partially characterize the isomorphism in Godsil and McKay's construction, and generalize Ji et al.'s characterization of the isomorphism to biregular bipartite graphs. The essential idea in characterizing the isomorphism uses Hammack's cancellation law as opposed to Hall's marriage theorem used by Ji et al., Comment: 13 pages

The eccentricity matrix $\varepsilon(G)$ of a graph $G$ is obtained from the distance matrix of $G$ by retaining the largest distances in each row and each column, and leaving zeros in the remaining ones. The eccentricity energy of $G$ is sum of the absolute values of the eigenvalues of $\varepsilon(G)$. Although the eccentricity matrices of graphs are closely related to the distance matrices of graphs, a number of properties of eccentricity matrices are substantially different from those of the distance matrices. The change in eccentricity energy of a graph due to an edge deletion is one such property. In this article, we give examples of graphs for which the eccentricity energy increase (resp., decrease) but the distance energy decrease (resp., increase) due to an edge deletion. Also, we prove that the eccentricity energy of the complete $k$-partite graph $K_{n_1,\hdots,n_k}$ with $k\geq 2$ and $ n_i\geq 2$, increases due to an edge deletion., Comment: Preliminary version. 11 pages

A complex unit gain graph ($\mathbb{T}$-gain graph), $\Phi = (G, \varphi)$ is a graph where the function $\varphi$ assigns a unit complex number to each orientation of an edge of $G$, and its inverse is assigned to the opposite orientation. A $ \mathbb{T} $-gain graph $\Phi$ is balanced if the product of the edge gains of each cycle (with a fixed orientation) is $1$. Signed graphs are special cases of $\mathbb{T}$-gain graphs. The adjacency matrix of $\Phi$, denoted by $ \mathbf{A}(\Phi)$ is defined canonically. The gain Laplacian for $\Phi$ is defined as $\mathbf{L}(\Phi) = \mathbf{D}(\Phi) - \mathbf{A}(\Phi)$, where $\mathbf{D}(\Phi)$ is the diagonal matrix with diagonal entries are the degrees of the vertices of $G$. The minimum number of vertices (resp., edges) to be deleted from $\Phi$ in order to get a balanced gain graph the frustration number (resp, frustration index). We show that frustration number and frustration index are bounded below by the smallest eigenvalue of $\mathbf{L}(\Phi)$. We provide several lower and upper bounds for extremal eigenvalues of $\mathbf{L}(\Phi)$ in terms of different graph parameters such as the number of edges, vertex degrees, and average $2$-degrees. The signed graphs are particular cases of the $\mathbb{T}$-gain graphs, all the bounds established in paper hold for signed graphs. Most of the bounds established here are new for signed graphs. Finally, we perform comparative analysis for all the obtained bounds in the paper with the state-of-the-art bounds available in the literature for randomly generated Erd\H{o}s-Re\'yni graphs. Some of the major highlights of our paper are the gain-dependent bounds, limit convergence of the bounds to the extremal eigenvalues, and optimal extremal bounds obtained by posing optimization problems to achieve the best possible bounds., Comment: Preliminary version. 32 pages

A complex unit gain graph ($ \mathbb{T} $-gain graph), $ \Phi=(G, \varphi) $ is a graph where the function $ \varphi $ assigns a unit complex number to each orientation of an edge of $ G $, and its inverse is assigned to the opposite orientation. %A complex unit gain graph($ \mathbb{T} $-gain graph) is a simple graph where each orientation of an edge is given a complex unit, and its inverse is assigned to the opposite orientation of the edge. In this article, we propose gain distance matrices for $ \mathbb{T} $-gain graphs. These notions generalize the corresponding known concepts of distance matrices and signed distance matrices. Shahul K. Hameed et al. introduced signed distance matrices and developed their properties. Motivated by their work, we establish several spectral properties, including some equivalences between balanced $ \mathbb{T} $-gain graphs and gain distance matrices. Furthermore, we introduce the notion of positively weighted $ \mathbb{T} $-gain graphs and study some of their properties. Using these properties, Acharya's and Stani\'c's spectral criteria for balance are deduced. Moreover, the notions of order independence and distance compatibility are studied. Besides, we obtain some characterizations for distance compatibility., Comment: 20 pages; 2 figures

Let $ \Phi=(G, \varphi) $ be a connected complex unit gain graph ($ \mathbb{T} $-gain graph) on a simple graph $ G $ with $ n $ vertices and maximum vertex degree $ \Delta $. The associated adjacency matrix and degree matrix are denoted by $ A(\Phi) $ and $ D(\Phi) $, respectively. Let $ m_{\alpha}(\Phi,\lambda) $ be the multiplicity of $ \lambda $ as an eigenvalue of $ A_{\alpha}(\Phi) :=\alpha D(\Phi)+(1-\alpha)A(\Phi)$, for $ \alpha\in[0,1) $. In this article, we establish that $ m_{\alpha}(\Phi, \lambda)\leq \frac{(\Delta-2)n+2}{\Delta-1}$, and characterize the classes of graphs for which the equality hold. Furthermore, we establish a couple of bounds for the rank of $A(\Phi)$ in terms of the maximum vertex degree and the number of vertices. One of the main results extends a result known for unweighted graphs and simplifies the proof in [15], and other results provide better bounds for $r(\Phi)$ than the bounds known in [8].

We propose the notion of normalized Laplacian matrix $\mathcal{L}(\Phi)$ for a gain graphs and study its properties in detail, providing insights and counterexamples along the way. We establish bounds for the eigenvalues of $\mathcal{L}(\Phi)$ and characterize the classes of graphs for which equality holds. The relationships between the balancedness, bipartiteness, and their connection to the spectrum of $\mathcal{L}(\Phi)$ are also studied. Besides, we extend the edge version of eigenvalue interlacing for the gain graphs. Thereupon, we determine the coefficients for the characteristic polynomial of $\mathcal{L}(\Phi)$., Comment: 20 Pages

We establish a characterization of almost $P$-matrices via a sign non-reversal property. In this we are inspired by the analogous results for $N$-matrices. Next, the interval hull of two $m \times n$ matrices $A=(a_{ij})$ and $B = (b_{ij})$, denoted by $\mathbb{I}(A,B)$, is the collection of all matrices $C \in \mathbb{R}^{m \times n}$ such that each $c_{ij}$ is a convex combination of $a_{ij}$ and $b_{ij}$. Using the sign non-reversal property, we identify a finite subset of $\mathbb{I}(A,B)$ that determines if all matrices in $\mathbb{I}(A,B)$ are $N$-matrices/almost $P$-matrices. This provides a test for an entire class of matrices simultaneously to be $N$-matrices/almost $P$-matrices. We also establish analogous results for semipositive and minimally semipositive matrices. These characterizations may be considered similar in spirit to that of $P$-matrices by Bialas-Garloff [Linear Algebra Appl. 1984] and Rohn-Rex [SIMAX 1996], and of positive definite matrices by Rohn [SIMAX 1994].

Let $G$ be a simple, connected graph and let $A(G)$ be the adjacency matrix of $G$. If $D(G)$ is the diagonal matrix of the vertex degrees of $G$, then for every real $\alpha \in [0,1]$, the matrix $A_{\alpha}(G)$ is defined as $$A_{\alpha}(G) = \alpha D(G) + (1- \alpha) A(G).$$ The eigenvalues of the matrix $A_{\alpha}(G)$ form the $A_{\alpha}$-spectrum of $G$. Let $G_1 \dot{\vee} G_2$, $G_1 \underline{\vee} G_2$, $G_1 \langle \textrm{v} \rangle G_2$ and $G_1 \langle \textrm{e} \rangle G_2$ denote the subdivision-vertex join, subdivision-edge join, $R$-vertex join and $R$-edge join of two graphs $G_1$ and $G_2$, respectively. In this paper, we compute the $A_{\alpha}$-spectra of $G_1 \dot{\vee} G_2$, $G_1 \underline{\vee} G_2$, $G_1 \langle \textrm{v} \rangle G_2$ and $G_1 \langle \textrm{e} \rangle G_2$ for a regular graph $G_1$ and an arbitrary graph $G_2$ in terms of their $A_{\alpha}$-eigenvalues. As an application of these results, we construct infinitely many pairs of $A_{\alpha}$-cospectral graphs.

A matrix $A$ is totally positive (or non-negative) of order $k$, denoted $TP_k$ (or $TN_k$), if all minors of size $\leq k$ are positive (or non-negative). It is well-known that such matrices are characterized by the variation diminishing property together with the sign non-reversal property. We do away with the former, and show that $A$ is $TP_k$ if and only if every submatrix formed from at most $k$ consecutive rows and columns has the sign non-reversal property. In fact this can be strengthened to only consider test vectors in $\mathbb{R}^k$ with alternating signs. We also show a similar characterization for all $TN_k$ matrices - more strongly, both of these characterizations use a single vector (with alternating signs) for each square submatrix. These characterizations are novel, and similar in spirit to the fundamental results characterizing $TP$ matrices by Gantmacher-Krein [Compos. Math. 1937] and $P$-matrices by Gale-Nikaido [Math. Ann. 1965]. As an application, we study the interval hull $\mathbb{I}(A,B)$ of two $m \times n$ matrices $A=(a_{ij})$ and $B = (b_{ij})$. This is the collection of $C \in \mathbb{R}^{m \times n}$ such that each $c_{ij}$ is between $a_{ij}$ and $b_{ij}$. Using the sign non-reversal property, we identify a two-element subset of $\mathbb{I}(A,B)$ that detects the $TP_k$ property for all of $\mathbb{I}(A,B)$ for arbitrary $k \geq 1$. In particular, this provides a test for total positivity (of any order), simultaneously for an entire class of rectangular matrices. In parallel, we also provide a finite set to test the total non-negativity (of any order) of an interval hull $\mathbb{I}(A,B)$., Comment: Final version, to appear in Bulletin of the London Mathematical Society. 9 pages, no figures

Let $H$ be a real Hilbert space. In this short note, using some of the properties of bounded linear operators with closed range defined on $H$, certain bounds for a specific convex subset of the solution set of infinite linear complementarity problems, are established.

A $\mathbb{T}$-gain graph, $\Phi = (G, \varphi)$, is a graph in which the function $\varphi$ assigns a unit complex number to each orientation of an edge, and its inverse is assigned to the opposite orientation. The associated adjacency matrix $ A(\Phi) $ is defined canonically. The energy $ \mathcal{E}(\Phi) $ of a $ \mathbb{T} $-gain graph $ \Phi $ is the sum of the absolute values of all eigenvalues of $ A(\Phi) $. We study the notion of energy of a vertex of a $ \mathbb{T} $-gain graph, and establish bounds for it. For any $ \mathbb{T} $-gain graph $ \Phi$, we prove that $2\tau(G)-2c(G) \leq \mathcal{E}(\Phi) \leq 2\tau(G)\sqrt{\Delta(G)}$, where $ \tau(G), c(G)$ and $ \Delta(G)$ are the vertex cover number, the number of odd cycles and the largest vertex degree of $ G $, respectively. Furthermore, using the properties of vertex energy, we characterize the classes of $ \mathbb{T} $-gain graphs for which $ \mathcal{E}(\Phi)=2\tau(G)-2c(G) $ holds. Also, we characterize the classes of $ \mathbb{T} $-gain graphs for which $\mathcal{E}(\Phi)= 2\tau(G)\sqrt{\Delta(G)} $ holds. This characterization solves a general version of an open problem. In addition, we establish bounds for the energy in terms of the spectral radius of the associated adjacency matrix., Comment: 31 pages, 4 figures

It is well known that the set of all $ n \times n $ matrices with distinct eigenvalues is a dense subset of the set of all real or complex $ n \times n $ matrices. In [Hartfiel, D. J. Dense sets of diagonalizable matrices. Proc. Amer. Math. Soc., 123(6): 1669-1672, 1995.], the author established a necessary and sufficient condition for a subspace of the set of all $n \times n$ matrices to have a dense subset of matrices with distinct eigenvalues. We are interested in finding a few necessary and sufficient conditions for a subset of the set of all $n \times n$ real or complex matrices to have a dense subset of matrices with distinct eigenvalues. Some of our results are generalizing the results of Hartfiel. Also, we study the existence of dense subsets of matrices with distinct singular values, distinct analytic eigenvalues, and distinct analytic singular values, respectively, in the subsets of the set of all real or complex matrices., Comment: 20 pages

In [Steve Butler. A note about cospectral graphs for the adjacency and normalized Laplacian matrices. Linear Multilinear Algebra, 58(3-4):387-390, 2010.], Butler constructed a family of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. In this article, we extend this construction for generating larger classes of bipartite graphs, which are cospectral for both the adjacency and the normalized Laplacian matrices. Also, we provide a couple of constructions of non-bipartite graphs, which are cospectral for the adjacency matrices but not necessarily for the normalized Laplacian matrices.

This paper is devoted to the study of eigenvalue region of the doubly stochastic matrices which are also permutative, that is, each row of such a matrix is a permutation of any other row. We call these matrices as permutative doubly stochastic (PDS) matrices. A method is proposed to obtain symbolic representation of all PDS matrices of order $n$ by finding equivalence classes of permutationally similar symbolic PDS matrices. This is a hard problem in general as it boils down to finding all Latin squares of order $n.$ However, explicit symbolic representation of matrices in these classes are determined in this paper when $n=2, 3, 4.$ It is shown that eigenvalue regions are same for doubly stochastic matrices and PDS matrices when $n=2, 3.$ It is also established that this is no longer true for $n=4,$ and two line segments are determined which belong to the eigenvalue region of doubly stochastic matrices but not in the eigenvalue region of PDS matrices. Thus a conjecture is developed for the boundary of the eigenvalue region of PDS matrices of order $4.$ Finally, inclusion theorems for eigenvalue region of PDS matrices are proved when $n\geq 2.$, Comment: 37 pages, some new results are added, title is changed

The eccentricity matrix $\varepsilon(G)$ of a graph $G$ is obtained from the distance matrix by retaining the eccentricities (the largest distance) in each row and each column. In this paper, we give a characterization of the star graph, among the trees, in terms of invertibility of the associated eccentricity matrix. The largest eigenvalue of $\varepsilon(G)$ is called the $\varepsilon$-spectral radius, and the eccentricity energy (or the $\varepsilon$-energy) of $G$ is the sum of the absolute values of the eigenvalues of $\varepsilon(G)$. We establish some bounds for the $\varepsilon$-spectral radius and characterize the extreme graphs. Two graphs are said to be $\varepsilon$-equienergetic if they have the same $\varepsilon$-energy. For any $n \geq 5$, we construct a pair of $\varepsilon$-equienergetic graphs on $n$ vertices, which are not $\varepsilon$-cospectral., Comment: 11 Pages

A $\mathbb{T}$-gain graph is a simple graph in which a unit complex number is assigned to each orientation of an edge, and its inverse is assigned to the opposite orientation. The associated adjacency matrix is defined canonically, and is called $\mathbb{T}$-gain adjacency matrix. Let $\mathbb{T}_{G} $ denote the collection of all $\mathbb{T}$-gain adjacency matrices on a graph $G$. In this article, we study the cospectrality of matrices in $\mathbb{T}_{G} $ and we establish equivalent conditions for a graph $G$ to be a tree in terms of the spectrum and the spectral radius of matrices in $\mathbb{T}_{G} $. We identify a class of connected graphs $\mathfrak{F^{'}}$ such that for each $G \in \mathfrak{F^{'}}$, the matrices in $\mathbb{T}_G$ have nonnegative real part up to diagonal unitary similarity. Then we establish bounds for the spectral radius of $\mathbb{T}$-gain adjacency matrices on $ G \in \mathfrak{F^{'}} $ in terms of their largest eigenvalues. Thereupon, we characterize $\mathbb{T}$-gain graphs for which the spectral radius of the associated $\mathbb{T}$-gain adjacency matrices equal to the largest vertex degree of the underlying graph. These bounds generalize results known for the spectral radius of Hermitian adjacency matrices of digraphs and provide an alternate proof of a result about the sharpness of the bound in terms of largest vertex degree established in [Krystal Guo, Bojan Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. J. Graph Theory 85 (2017), no. 1, 217-248.]., Comment: Comments are welcome!