Search

Let $ G $ be a graph of order $ n $ and $ \mu $ be an adjacency eigenvalue of $ G $ with multiplicity $ k\geq 1 $. A star complement for $ \mu $ in $ G $ is an induced subgraph of $ G $ of order $ n-k $ with no eigenvalue $ \mu $. In this paper, we characterize the maximal graphs with the bipartite graph $ K_{2, s} $ as a star complement for eigenvalues $ \mu = -2, 1 $ and study the cases of other eigenvalues for further research.

Let α be a real number with 0 ≤ α 1 , G be a uniform hypergraph, and A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) , where D ( G ) and A ( G ) are the diagonal degree tensor and the adjacency tensor of G , respectively. The spectral radius of A α ( G ) is called the α -spectral radius of G . In this paper, some properties for the α -spectral radius of connected k -uniform hypergraphs are investigated, the unique k -uniform supertree with the largest α -spectral radius among all k -uniform supertrees with a given degree sequence is characterized, and the majorization theorem for k -uniform supertrees is obtained. By applying the majorization theorem, we determine the k -uniform supertrees obtaining the three largest α -spectral radius among all k -uniform supertrees with n vertices, give a new proof ordering the eight largest spectral radius among all k -uniform supertrees with n vertices, propose an open problem for further research, and characterize the unique k -uniform supertree with the largest α -spectral radius among all k -uniform supertrees with given different parameters, e.g., the maximum degree △ , or the number of pendent vertices.

In this paper, we obtain a sharp upper bound on the spectral radius of a nonnegative k-uniform tensor and characterize when this bound is achieved. Furthermore, this result deduces the main result in [X. Duan and B. Zhou, Sharp bounds on the spectral radius of a nonnegative matrix, Linear Algebra Appl. 439:2961–2970, 2013] for nonnegative matrices; improves the adjacency spectral radius and signless Laplacian spectral radius of a uniform hypergraph for some known results in [D.M. Chen, Z.B. Chen and X.D. Zhang, Spectral radius of uniform hypergraphs and degree sequences, Front. Math. China 6:1279–1288, 2017]; and presents some new sharp upper bounds for the adjacency spectral radius and signless Laplacian spectral radius of a uniform directed hypergraph. Moreover, a characterization of a strongly connected k-uniform directed hypergraph is obtained.

In this paper, we define $k$-uniform tensors for $k\geq 2$, which are more closely related to the $k$-uniform hypergraphs than the general tensors, and introduce the parameter $r^{(q)}_{i}(\mathbb{A})$ for a tensor $\mathbb{A}$, which is the generalization of the $i$-th slice sum $r_ {i}(\mathbb{A})$ (also the $i$-th average 2-slice sum $m_{i}(\mathbb{A})$). By using $r^{(q)}_{i}(\mathbb{A})$ for $q\geq1$, we obtain a general result on the sharp upper bound for the spectral radius of a nonnegative $k$-uniform tensor. When $k = 2, q = 1, 2, 3$, this result deduces the main results for nonnegative matrices in [ 1 , 8 , 27 ]; when $k\geq 3, q = 1$, this result deduces the main results in [ 5 , 20 ]. We also find that the upper bounds obtained from different $q$ can not be compared. Furthermore, we can obtain some known or new upper bounds by applying the general result to $k$-uniform hypergraphs and $k$-uniform directed hypergraphs, respectively.

We obtain the sharp upper and lower bounds for the spectral radius of a nonnegative weakly irreducible tensor. By using the technique of the representation associate matrix of a tensor and the associate directed graph of the matrix, the equality cases of the bounds are completely characterized by graph theory methods. Applying these bounds to a nonnegative irreducible matrix or a connected graph (digraph), we can improve the results of L. H. You, Y. J. Shu, and P. Z. Yuan [Linear Multilinear Algebra, 2017, 65(1): 113–128], and obtain some new or known results. Applying these bounds to a uniform hypergraph, we obtain some new results and improve some known results of X. Y. Yuan, M. Zhang, and M. Lu [Linear Algebra Appl., 2015, 484: 540–549]. Finally, we give a characterization of a strongly connected k-uniform directed hypergraph, and obtain some new results by applying these bounds to a uniform directed hypergraph.

Let M be a partitioned matrix and B be its equitable quotient matrix. In this paper, we prove the inclusion of their spectra σ ( B ) ⊆ σ ( M ) , and the equality of their spectral radii ρ ( B ) = ρ ( M ) if M is nonnegative. Moreover, σ ( M ) is shown to be completely determined by σ ( B ) if M is from a class of special matrices. Then we apply these results to obtain the spectra of some well-known matrices associated with graphs or digraphs, and then determine the extremal values of different spectral radii associated with connected graphs or strongly connected digraphs with given vertex connectivity.

Hexagonal chains are a special class of catacondensed benzenoid system and phenylene chains are a class of polycyclic aromatic compounds. Recently, A family of Sombor indices was introduced by Gutman in the chemical graph theory. It had been examined that these indices may be successfully applied on modeling thermodynamic properties of compounds. In this paper, we study the expected values of the Sombor indices in random hexagonal chains, phenylene chains, and consider the Sombor indices of some chemical graphs such as graphene, coronoid systems and carbon nanocones., Comment: 19 pages, 13 figures

Two graphs are said to be L -cospectral (respectively, Q -cospectral) if they have the same (respectively, signless) Laplacian spectra, and a graph G is said to be L − D S (respectively, Q − D S ) if there does not exist other non-isomorphic graph H such that H and G are L -cospectral (respectively, Q -cospectral). Let d 1 ( G ) ≥ d 2 ( G ) ≥ ⋯ ≥ d n ( G ) be the degree sequence of a graph G with n vertices. In this paper, we prove that except for two exceptions (respectively, the graphs with d 1 ( G ) ∈ { 4 , 5 } ), if H is L -cospectral (respectively, Q -cospectral) with a connected graph G and d 2 ( G ) = 2 , then H has the same degree sequence as G . A spider graph is a unicyclic graph obtained by attaching some paths to a common vertex of the cycle. As an application of our result, we show that every spider graph and its complement graph are both L − D S , which extends the corresponding results of Haemers et al. (2008), Liu et al. (2011), Zhang et al. (2009) and Yu et al. (2014).

For a connected graph G on n vertices, recall that the distance signless Laplacian matrix of G is defined to be Q ( G ) = T r ( G ) + D ( G ) , where D ( G ) is the distance matrix, T r ( G ) = d i a g ( D 1 , D 2 , … , D n ) and D i is the row sum of D ( G ) corresponding to vertex v i . Denote by ρ D ( G ) , ρ m i n D ( G ) the largest eigenvalue and the least eigenvalue of D ( G ) , respectively. And denote by q D ( G ) , q m i n D ( G ) the largest eigenvalue and the least eigenvalue of Q ( G ) , respectively. The distance spread of a graph G is defined as S D ( G ) = ρ D ( G ) − ρ m i n D ( G ) , and the distance signless Laplacian spread of a graph G is defined as S Q ( G ) = q D ( G ) − q m i n D ( G ) . In this paper, we point out an error in the result of Theorem 2.4 in Yu et al. (2012) and modify it. As well, we obtain some lower bounds on distance signless Laplacian spread of a graph.

We define and study three different types of upper (and lower) triangular blocked tensors, which are all generalizations of the triangular blocked matrices, and are also generalizations of reducible or weakly reducible tensors. We study some common properties, as well as different properties of these three types of triangular blocked tensors. We obtain the formulas for the determinants, characteristic polynomials and spectra of the first and second type triangular blocked tensors, and give an example to show that these formulas no longer hold for the third type triangular blocked tensors. We prove that the product of any two ( n 1 , ⋯ , n r ) -upper (or lower) triangular blocked tensors of the first or second or third type is still an ( n 1 , ⋯ , n r ) -upper (or lower) triangular blocked tensor of the same type. We also prove that, if an ( n 1 , ⋯ , n r ) -upper triangular blocked tensor of the first or second or third type has a left k-inverse, then its unique left k-inverse is still an ( n 1 , ⋯ , n r ) -upper triangular blocked tensor of all the three types. Also if it has a right k-inverse, then all of its right k-inverses are still ( n 1 , ⋯ , n r ) -upper triangular blocked tensors of all the three types. By showing that the left k-inverse (if any) of a weakly irreducible nonsingular M-tensor is a positive tensor, we show that the left k-inverse (if any) of a first or second or third type normal ( n 1 , ⋯ , n r ) -upper triangular blocked nonsingular M-tensor is an ( n 1 , ⋯ , n r ) -upper triangular blocked tensor of all the three types all of whose diagonal blocks are positive tensors. We also show that every order m dimension n tensor is permutation similar to some third type normal upper triangular blocked tensor (all of whose diagonal blocks are irreducible). We give an example to show that this is not true for the first type normal upper triangular blocked tensor.

In this paper, we obtain the sharp upper and lower bounds for the spectral radius of a nonnegative irreducible matrix. We also apply these bounds to various matrices associated with a graph or a digraph, obtain some new results or known results about various spectral radii, including the adjacency spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance signless Laplacian spectral radius of a graph or a digraph.

In [1], Abdo and Dimitov defined the total irregularity of a graph G=(V,E) as irrt(G)=1/2 ?u,v?V|dG(u)-dG(v)|, where dG(u) denotes the vertex degree of a vertex u ? V. In this paper, we investigate the minimal total irregularity of the connected graphs, determine the minimal, the second minimal, the third minimal total irregularity of trees, unicyclic graphs, bicyclic graphs on n vertices, and propose an open problem for further research.

In this paper, we show that the primitive degree set of nonnegative primitive tensors with order m ( ≥ 3 ) and dimension n is { 1 , 2 , … , ( n − 1 ) 2 + 1 } , which implies that the results of the case m ≥ 3 (the case of tensors) is totally different from the case m = 2 (the case of matrices), and we also propose some open problems for further research.

Recently, Song and Qi extended the concept of P , P 0 and B matrices to P , P 0 , B and B 0 tensors, obtained some properties about these tensors, and proposed many questions for further research. In this paper, we answer three questions mentioned as above and obtain further results about P , P 0 , B and B 0 tensors.

Let D be a strongly connected digraph and A(D) be the adjacency matrix of D. Let diag(D) be the diagonal matrix with outdegrees of the vertices of D and Q(D) = diag(D) + A(D) be the signless Laplacian matrix of D. The spectral radius of Q(D) is called the signless Laplacian spectral radius of D, denoted by q(D). In this paper, we give sharp bound on q(D) with outdegree sequence and compare the bound with some known bounds, establish some sharp upper or lower bound on q(D) with some given parameter such as clique number, girth or vertex connectivity, and characterize the corresponding extremal digraph or proposed open problem. In addition, we also determine the unique digraph which achieves the minimum (or maximum), the second minimum (or maximum), the third minimum, the fourth minimum spectral radius and signless Laplacian spectral radius among all strongly connected digraphs, and answer the open problem proposed by Lin-Shu [H.Q. Lin, J.L. Shu, A note on the spectral characterization of strongly connected bicyclic digraphs, Linear Algebra Appl. 436 (2012) 2524{2530]., Comment: 20 pages, 6 figures

In this paper, we obtain some results on the sharp upper bounds of the spectral radius of a nonnegative matrix, then apply these results to signless Laplacian matrices to obtain some known results. We also apply these results to distance signless Laplacian matrix of a graph, and obtain some sharp bounds on the distance signless Laplacian spectral radius.

Let G be a connected regular graph. Denoted by t(G) and Kf(G) the total graph and Kirchhoff index of G, respectively. This paper is to point out that Theorem 3.7 and Corollary 3.8 from ''Kirchhoff index in line, subdivision and total graphs of a regular graph'' [X. Gao, Y.F. Luo, W.W. Liu, Kirchhoff index in line, subdivision and total graphs of a regular graph, Discrete Appl. Math. 160(2012) 560-565] are incorrect, since the conclusion of a lemma is essentially wrong. Moreover, we first show the Laplacian characteristic polynomial of t(G), where G is a regular graph. Consequently, by using Kf(G), we give an expression on Kf(t(G)) and a lower bound on Kf(t(G)) of a regular graph G, which correct Theorem 3.7 and Corollary 3.8 in Gao et al. (2012) [2].

An n × n sign pattern matrix has entries in {1, −1, 0}. This paper surveys the following problems concerning the bases of sign pattern matrices: base and base set of sign pattern matrices; the generalizations of the base of sign pattern matrices; other indices of sign pattern matrices. Several open problems are identified.

Suppose S is a primitive non-powerful signed digraph. A pair of SSSD walks of S are two directed walks of S , which have the same initial vertex, same terminal vertex and same length, but different signs. The lewin number of S , denoted l ( S ) , is the least positive integer k such that there are both SSSD walks of lengths k and k + 1 from some vertex u to some vertex v (possibly u again) of S . This paper presents a proof of a conjecture on l ( S ) , which was put forward by You et al. [L.H. You, M.H. Liu, B.L. Liu, Bounds on the lewin number for primitive non-powerful signed digraphs, Acta Math. Appl. Sinica 35 (2012) 396–407].

In this paper, we obtain a sharp upper bound for the spectral radius of a nonnegative matrix. This result is used to present upper bounds for the adjacency spectral radius, the Laplacian spectral radius, the signless Laplacian spectral radius, the distance spectral radius, the distance Laplacian spectral radius, the distance signless Laplacian spectral radius of a graph or a digraph. These results are new or generalize some known results., 16 pages in Czechoslovak Math. J., 2016. arXiv admin note: text overlap with arXiv:1507.07059

A sign pattern matrix M with zero trace is primitive non-powerful if for some positive integer k, M k = J #. The base l(M) of the primitive non-powerful matrix M is the smallest integer k. By considering the signed digraph S whose adjacent matrix is the primitive non-powerful matrix M, we will show that if l(M) = 2, the minimum number of non-zero entries of M is 5n − 8 or 5n − 7 depending on whether n is even or odd.

Let b = b ( A ) be the Boolean rank of an n × n primitive Boolean matrix A and exp( A ) be the exponent of A . Then exp( A ) ⩽ ( b − 1) 2 + 2, and the matrices for which equality occurs have been determined in [D.A. Gregory, S.J. Kirkland, N.J. Pullman, A bound on the exponent of a primitive matrix using Boolean rank, Linear Algebra Appl. 217 (1995) 101–116]. In this paper, we show that for each 3 ⩽ b ⩽ n − 1, there are n × n primitive Boolean matrices A with b ( A ) = b such that exp( A ) = ( b − 1) 2 + 1, and we explicitly describe all such matrices.

A connected graph $G$ is a cactus if any two of its cycles have at most one common vertex. Let $\ell_n^m$ be the set of cacti on $n$ vertices with matching number $m.$ S.C. Li and M.J. Zhang determined the unique graph with the maximum signless Laplacian spectral radius among all cacti in $\ell_n^m$ with $n=2m$. In this paper, we characterize the case $n\geq 2m+1$. This confirms the conjecture of Li and Zhang(S.C. Li, M.J. Zhang, On the signless Laplacian index of cacti with a given number of pendant vetices, Linear Algebra Appl. 436, 2012, 4400--4411). Further, we characterize the unique graph with the maximum signless Laplacian spectral radius among all cacti on $n$ vertices., Comment: 20

In [J.Y. Shao, L.H. You, Bound on the base of irreducible generalized sign pattern matrices, Discrete Math., in press], Shao and You extended the concept of the base from powerful sign pattern matrices to non-powerful (and generalized) sign pattern matrices. In this paper, we study the base for primitive non-powerful nearly reducible sign pattern (and generalized sign pattern) matrices. We obtain sharp upper bounds, together with complete characterization of the equality cases of the base for primitive nearly reducible sign pattern (and generalized sign pattern) matrices. We also show that there exist “gaps” in the base set of the classes of such matrices.

Let n , r be integers with 0 ⩽ r ⩽ n − 1. An n × n matrix A is called r - partly decomposable if it contains a k × l zero submatrix with k + l = n − r + 1. A matrix which is not r -partly decomposable is called r - indecomposable (shortly, r -inde). Let E ij be the n × n matrix with a 1 in the ( i , j ) position and 0’s elsewhere. If A is r -indecomposable and, for each a ij ≠ 0, the matrix A − aijE ij is no longer r -indecomposable, then A is called r - nearly decomposable (shortly, r -nde). In this paper, we derive numerical and enumerative results concerning r -nde matrices of 0’s and 1’s. We also obtain some bounds on the index of convergence of r -inde matrices, especially for the adjacency matrices of primitive Cayley digraphs and circulant matrices. Finally, we propose an open problem for further research.

In this paper, we present a necessary and sufficient condition for a nonnegative tensor to be a primitive one, show that the exponent set of nonnegative primitive tensors with order $m(\ge n)$ and dimension $n$ is $\{k| 1\le k\le (n-1)^2+1\}. $, 10 pages, 1 figures

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. A signed graph is a graph with a sign attached to each of its edges. In this paper, we apply the coefficient theorem on the characteristic polynomial of a signed graph and give two formulae on the nullity of signed graphs with cut-points. As applications of the above results, we investigate the nullity of the bicyclic signed graphΓ∞p,q,l, obtain the nullity set of unbalanced bicyclic signed graphs, and thus determine the nullity set of bicyclic signed graphs.

In 2012, Abdo and Dimitrov defined the total irregularity of a graphG=(V,E)asirrtG=1/2∑u,v∈VdGu-dGv, wheredGudenotes the vertex degree of a vertexu∈V. In this paper, we investigate the total irregularity of bicyclic graphs and characterize the graph with the maximal total irregularity among all bicyclic graphs onnvertices.

Let $\mathbb{P}_n$ be the set of all matrices which have the same zero patterns with some permutation matrix of order $n$. In this paper, we prove the following result: Let $\mathbb{I}$ be the unit tensor of order $m\ge3$ and dimension $n\ge2$. Suppose that $P$ and $Q$ are two matrices with $P\mathbb{I}Q=\mathbb{I}$, then $P,Q\in \mathbb{P}_n$. This gives a characterization for the similarities of tensors with order $m\ge3$., 7 pages

In this paper, we prove: Let A be a nonnegative primitive tensor with order m and dimension n. Then its primitive degree R(A)\leq (n-1)^2+1, and the upper bound is sharp. This confirms a conjecture of Shao [7]., Comment: 8 pages

Let $G$ be a simple graph with $n$ vertices and $e(G)$ edges, and $q_1(G)\geq q_2(G)\geq\cdots\geq q_n(G)\geq0$ be the signless Laplacian eigenvalues of $G.$ Let $S_k^+(G)=\sum_{i=1}^{k}q_i(G),$ where $k=1, 2, \ldots, n.$ F. Ashraf et al. conjectured that $S_k^+(G)\leq e(G)+\binom{k+1}{2}$ for $k=1, 2, \ldots, n.$ In this paper, we give various upper bounds for $S_k^+(G),$ and prove that this conjecture is true for the following cases: connected graph with sufficiently large $k,$ unicyclic graphs and bicyclic graphs for all $k,$ and tricyclic graphs when $k\neq 3.$, Comment: 13 pages, 5 figures

In this paper, the primitive symmetric loop-free signed digraphs with the maximum base are characterized.

In [B.M. Kim, B.C. Song, W. Hwang, Primitive graphs with given exponents and minimum number of edges, Linear Algebra Appl. 420 (2007) 648–662], the minimum number of edges of a simple graph on n vertices with exponent k was determined. In this paper, we completely determine the minimum number, H ( n , k ) , of arcs of primitive non-powerful symmetric loop-free signed digraphs on n vertices with base k , characterize the underlying digraphs which have H ( n , k ) arcs when k is 2, nearly characterize the case when k is 3 and propose an open problem.