For a block upper triangular matrix, a necessary and sufficient condition has been given to let it be the sum of block upper rectangular matrices satisfying certain rank constraints; see H. Bart, A. P. M. Wagelmans (2000). The proof involves elements from integer programming and employs Farkas' lemma. The algebra of block upper triangular matrices can be viewed as a matrix algebra determined by a pattern of zeros. The present note is concerned with the question whether the decomposition result referred...

Let $G$ be a finite graph with an eigenvalue $\mu$ of multiplicity $m$. A set $X$ of $m$ vertices in $G$ is called a star set for $\mu$ in $G$ if $\mu$ is not an eigenvalue of the star complement $G\setminus X$ which is the subgraph of $G$ induced by vertices not in $X$. A vertex subset of a graph is $(\kappa ,\tau )$-regular if it induces a $\kappa$-regular subgraph and every vertex not in the subset has $\tau$ neighbors in it. We investigate the graphs having a $(\kappa ,\tau )$-regular set which induces a star complement for some eigenvalue. A survey of known results is provided...

Two inequalities for the Laplacian spread of graphs are proved in this note. These inequalities are reverse to those obtained by Z. You, B. Liu: The Laplacian spread of graphs, Czech. Math. J. 62 (2012), 155–168.

A graph is called distance integral (or $D$-integral) if all eigenvalues of its distance matrix are integers. In their study of $D$-integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$-integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_1,p_2,p_3}$ with $p_1<p_2<p_3$, and $K_{p_1,p_2,p_3,p_4}$ with $p_1<p_2<p_3<p_4$, as well as the infinite classes of distance integral complete...

Let $G$ be a graph with $n$ vertices, $m$ edges and a vertex degree sequence $(d_1,d_2,\cdots ,d_n)$, where $d_1\ge d_2\ge \cdots \ge d_n$. The spectral radius and the largest Laplacian eigenvalue are denoted by $\rho \left(G\right)$ and $\mu \left(G\right)$, respectively. We determine the graphs with $$\rho \left(G\right)=\frac{d_n-1}{2}+\sqrt{2m-n{d}_n+\frac{{(d_n+1)}^2}{4}}$$ and the graphs with $d_n\ge 1$ and $$\mu \left(G\right)=d_n+\frac{1}{2}+\sqrt{{\sum }_{i=1}^n{d}_i(d_i-d_n)+{\left(d_n-\frac{1}{2}\right)}^2}.$$ We also present some sharp lower bounds for the Laplacian eigenvalues of a connected graph.

We give a novel upper bound on graph energy in terms of the vertex cover number, and present a complete characterization of the graphs whose energy equals twice their matching number.

This paper analyzes the proof-theoretic strength of an infinite version of several theorems from algorithmic graph theory. In particular, theorems on reachability matrices, shortest path matrices, topological sorting, and minimal spanning trees are considered.

A G-shift of finite type (G-SFT) is a shift of finite type which commutes with the continuous action of a finite group G. For irreducible G-SFTs we classify right closing almost conjugacy, answering a question of Bill Parry.