No Arabic abstract
Let $G$ be a digraph with adjacency matrix $A(G)$. Let $D(G)$ be the diagonal matrix with outdegrees of vertices of $G$. Nikiforov cite{Niki} proposed to study the convex combinations of the adjacency matrix and diagonal matrix of the degrees of undirected graphs. Liu et al. cite{LWCL} extended the definition to digraphs. For any real $alphain[0,1]$, the matrix $A_alpha(G)$ of a digraph $G$ is defined as $$A_alpha(G)=alpha D(G)+(1-alpha)A(G).$$ The largest modulus of the eigenvalues of $A_alpha(G)$ is called the $A_alpha$ spectral radius of $G$, denoted by $lambda_alpha(G)$. This paper proves some extremal results about the spectral radius $lambda_alpha(G)$ that generalize previous results about $lambda_0(G)$ and $lambda_{frac{1}{2}}(G)$. In particular, we characterize the extremal digraph with the maximum (or minimum) $A_alpha$ spectral radius among all $widetilde{infty}$-digraphs and $widetilde{theta}$-digraphs on $n$ vertices. Furthermore, we determine the digraphs with the second and the third minimum $A_alpha$ spectral radius among all strongly connected bicyclic digraphs. For $0leqalphaleqfrac{1}{2}$, we also determine the digraphs with the second, the third and the fourth minimum $A_alpha$ spectral radius among all strongly connected digraphs on $n$ vertices. Finally, we characterize the digraph with the minimum $A_alpha$ spectral radius among all strongly connected bipartite digraphs which contain a complete bipartite subdigraph.
Let $A_alpha(G)$ be the $A_alpha$-matrix of a digraph $G$ and $lambda_{alpha 1}, lambda_{alpha 2}, ldots, lambda_{alpha n}$ be the eigenvalues of $A_alpha(G)$. Let $rho_alpha(G)$ be the $A_alpha$ spectral radius of $G$ and $E_alpha(G)=sum_{i=1}^n lambda_{alpha i}^2$ be the $A_alpha$ energy of $G$ by using second spectral moment. Let $mathcal{G}_n^m$ be the set of non-strongly connected digraphs with order $n$, which contain a unique strong component with order $m$ and some directed trees which are hung on each vertex of the strong component. In this paper, we characterize the digraph which has the maximal $A_alpha$ spectral radius and the maximal (minimal) $A_alpha$ energy in $mathcal{G}_n^m$.
We have recently proposed a surplus-based algorithm which solves the multi-agent average consensus problem on general strongly connected and static digraphs. The essence of that algorithm is to employ an additional variable to keep track of the state changes of each agent, thereby achieving averaging even though the state sum is not preserved. In this note, we extend this approach to the more interesting and challenging case of time-varying topologies: An extended surplus-based averaging algorithm is designed, under which a necessary and sufficient graphical condition is derived that guarantees state averaging. The derived condition requires only that the digraphs be arbitrary strongly connected in a emph{joint} sense, and does not impose balanced or symmetric properties on the network topology, which is therefore more general than those previously reported in the literature.
Let $G$ be a connected uniform hypergraphs with maximum degree $Delta$, spectral radius $lambda$ and minimum H-eigenvalue $mu$. In this paper, we give some lower bounds for $Delta-lambda$, which extend the result of [S.M. Cioabu{a}, D.A. Gregory, V. Nikiforov, Extreme eigenvalues of nonregular graphs, J. Combin. Theory, Ser. B 97 (2007) 483-486] to hypergraphs. Applying these bounds, we also obtain a lower bound for $Delta+mu$.
We define strongly chordal digraphs, which generalize strongly chordal graphs and chordal bipartite graphs, and are included in the class of chordal digraphs. They correspond to square 0,1 matrices that admit a simultaneous row and column permutation avoiding the {Gamma} matrix. In general, it is not clear if these digraphs can be recognized in polynomial time, and we focus on symmetric digraphs (i.e., graphs with possible loops), tournaments with possible loops, and balanced digraphs. In each of these cases we give a polynomial-time recognition algorithm and a forbidden induced subgraph characterization. We also discuss an algorithm for minimum general dominating set in strongly chordal graphs with possible loops, extending and unifying similar algorithms for strongly chordal graphs and chordal bipartite graphs.
Let $G$ be a graph with adjacency matrix $A(G)$ and let $D(G)$ be the diagonal matrix of the degrees of $G$. For every real $alphainleft[ 0,1right] $, write $A_{alpha}left( Gright) $ for the matrix [ A_{alpha}left( Gright) =alpha Dleft( Gright) +(1-alpha)Aleft( Gright) . ] Let $alpha_{0}left( Gright) $ be the smallest $alpha$ for which $A_{alpha}(G)$ is positive semidefinite. It is known that $alpha_{0}left( Gright) leq1/2$. The main results of this paper are: (1) if $G$ is $d$-regular then [ alpha_{0}=frac{-lambda_{min}(A(G))}{d-lambda_{min}(A(G))}, ] where $lambda_{min}(A(G))$ is the smallest eigenvalue of $A(G)$; (2) $G$ contains a bipartite component if and only if $alpha_{0}left( Gright) =1/2$; (3) if $G$ is $r$-colorable, then $alpha_{0}left( Gright) geq1/r$.