Let $G$ be a connected simple graph on $n$ vertices. The Laplacian index of $G$, namely, the greatest Laplacian eigenvalue of $G$, is well known to be bounded above by $n$. In this paper, we give structural characterizations for graphs $G$ with the largest Laplacian index $n$. Regular graphs, Hamiltonian graphs and planar graphs with the largest Laplacian index are investigated. We present a necessary and sufficient condition on $n$ and $k$ for the existence of a $k$-regular graph $G$ of order $n$ with the largest Laplacian...

Let $G$ be an undirected connected graph with $n$, $n\ge 3$, vertices and $m$ edges with Laplacian eigenvalues ${\mu }_1\ge {\mu }_2\ge \cdots \ge {\mu }_{n-1}>{\mu }_n=0$. Denote by ${\mu }_I={\mu }_{r_1}+{\mu }_{r_2}+\cdots +{\mu }_{r_k}$, $1\le k\le n-2$, $1\le r_1<r_2<\cdots <r_k\le n-1$, the sum of $k$ arbitrary Laplacian eigenvalues, with ${\mu }_{I_1}={\mu }_1+{\mu }_2+\cdots +{\mu }_k$ and ${\mu }_{I_n}={\mu }_{n-k}+\cdots +{\mu }_{n-1}$. Lower bounds of graph invariants ${\mu }_{I_1}-{\mu }_{I_n}$ and ${\mu }_{I_1}/{\mu }_{I_n}$ are obtained. Some known inequalities follow as a special case.

A matrix $𝒜$ whose entries come from the set $\{+,-,0\}$ is called a sign pattern matrix, or sign pattern. A sign pattern is said to be potentially nilpotent if it has a nilpotent realization. In this paper, the characterization problem for some potentially nilpotent double star sign patterns is discussed. A class of double star sign patterns, denoted by $𝒟SSP(m,2)$, is introduced. We determine all potentially nilpotent sign patterns in $𝒟SSP(3,2)$ and $𝒟SSP(5,2)$, and prove that one sign pattern in $𝒟SSP(3,2)$ is potentially stable.

In this paper, two robust consensus problems are considered for a multi-agent system with various disturbances. To achieve the robust consensus, two distributed control schemes for each agent, described by a second-order differential equation, are proposed. With the help of graph theory, the robust consensus stability of the multi-agent system with communication delays is obtained for both fixed and switching interconnection topologies. The results show the leaderless consensus can be achieved with...

Let G be a finite group of order n. The strong power graph Ps(G) of G is the undirected graph whose vertices are the elements of G such that two distinct vertices a and b are adjacent if am1=bm2 for some positive integers m1, m2 < n. In this article we classify all groups G for which Ps(G) is a line graph. Spectrum and permanent of the Laplacian matrix of the strong power graph Ps(G) are found for any finite group G.

In this paper we present some theoretical results about the irreducibility of the Laplacian matrix ordered by the Reverse Cuthill-McKee (RCM) algorithm. We consider undirected graphs with no loops consisting of some connected components. RCM is a well-known scheme for numbering the nodes of a network in such a way that the corresponding adjacency matrix has a narrow bandwidth. Inspired by some properties of the eigenvectors of a Laplacian matrix, we derive some properties based on row sums of a...

Let G and H be two graphs. The join G ∨ H is the graph obtained by joining every vertex of G with every vertex of H. The corona G ○ H is the graph obtained by taking one copy of G and |V (G)| copies of H and joining the i-th vertex of G to every vertex in the i-th copy of H. The neighborhood corona G★H is the graph obtained by taking one copy of G and |V (G)| copies of H and joining the neighbors of the i-th vertex of G to every vertex in the i-th copy of H. The edge corona G ◇ H is the graph obtained...