Recent zbMATH articles in MSC 15A16https://www.zbmath.org/atom/cc/15A162021-05-28T16:06:00+00:00WerkzeugVertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations.https://www.zbmath.org/1459.053102021-05-28T16:06:00+00:00"Ballini, Francesco"https://www.zbmath.org/authors/?q=ai:ballini.francesco"Deniskin, Nikita"https://www.zbmath.org/authors/?q=ai:deniskin.nikitaSummary: Centrality measures are used in network science to identify the most important vertices for transmission of information and dynamics on a graph. One of these measures, introduced by \textit{E. Estrada} and \textit{J. A. Rodríguez-Velázquez} [``Subgraph centrality in complex networks'', Phys. Rev. E 71, Article ID 056103, 9 p. (2005; \url{doi:10.1103/PhysRevE.71.056103})], is the \(\beta\)-subgraph centrality, which is based on the exponential of the matrix \(\beta A\), where \(A\) is the adjacency matrix of the graph and \(\beta\) is a real parameter (``inverse temperature''). We prove that for algebraic \(\beta\), two vertices with equal \(\beta\)-subgraph centrality are necessarily cospectral. We further show that two such vertices must have the same degree and eigenvector centralities. Our results settle a conjecture of Estrada and a generalization of it due to \textit{K. Kloster} et al. [Linear Algebra Appl. 546, 115--121 (2018; Zbl 1391.05169)]. We also discuss possible extensions of our results.Sedentary quantum walks.https://www.zbmath.org/1459.051712021-05-28T16:06:00+00:00"Godsil, Chris"https://www.zbmath.org/authors/?q=ai:godsil.christopher-davidSummary: Let \(X\) be a graph with adjacency matrix \(A\). The continuous quantum walk on \(X\) is determined by the unitary matrices \(U(t)=\exp(itA)\) (for \(t\in\mathbb{R})\). If \(X\) is the complete graph \(K_n\) and \(a\in V(X)\), then
\[
1-|U(t)_{a,a}|\leq 2/n.
\]
Roughly speaking, this means that a quantum walk on a complete graph stays home with high probability. We say that a family of graphs is sedentary if there is a constant \(c\) such that \(1-|U(t)_{a,a}|\leq c/|V(X)|\) for all \(t\). In this paper we investigate this condition, and produce further examples of sedentary graphs.
A cone over a graph \(X\) is the graph we get by adjoining a new vertex and making it adjacent to each vertex of \(X\). We prove that if \(X\) is the cone over an \(\ell\)-regular graph on \(n\) vertices, then \(|U(t)_{a,a}|\leq\ell^2/(\ell^2+4n)\). It follows that if we choose \(\ell\) and \(n\) such that \(n/\ell^2\to 0\), then a continuous quantum walk starting on the ``conical'' vertex will remain there with probability close to 1. On the other hand, if \(\ell\leq 2\), we show there is a time \(t\) such that all entries in the \(a\)-column of \(U(t)e_a\) have absolute value \(1/\sqrt{n}\). We show that there are large classes of strongly regular graphs such that \(1-|U(t)_{a,a}|\leq c/V(X)\) for some constant \(c\). On the other hand, for Paley graphs on \(n\) vertices, we prove that if \(t=\pi/\sqrt{n}\), then \(|U(t)_{a,a}|\leq 1/n\).On improved universal estimation of exponents of digraphs.https://www.zbmath.org/1459.051032021-05-28T16:06:00+00:00"Fomichev, V. M."https://www.zbmath.org/authors/?q=ai:fomichev.v-mSummary: An improved formula for universal estimation of exponent is obtained for \(n\)-vertex primitive digraphs. A previous formula by \textit{A. L. Dulmage} and \textit{N. S. Mendelsohn} [Ill. J. Math. 8, 642--656 (1964; Zbl 0125.00706)] is based on a system \(\hat{C}\) of directed circuits \(C_1,\ldots,C_m\), which are held in a graph and have lengths \(l_1,\ldots,l_m\) with \(\gcd(l_1,\ldots,l_m)=1\). A new formula is based on a similar circuit system \(\hat{C} \), where \(\gcd(l_1,\ldots,l_m)=d\geq 1\). Also, the new formula uses \(r_{i,j}^{s/d}(\hat{C})\), that is the length of the shortest path from \(i\) to \(j\) going through the circuit system \(\hat{C}\) and having the length which is comparable to \(s\) modulo \(d, s=0,\ldots,d-1\). It is shown, that \(\text{exp}\,\Gamma\leq 1+\hat{F}(L(\hat{C}))+R(\hat{C})\), where \(\hat{F}(L)=d\cdot F(l_1/d,\ldots, l_m/d)\) and \(F(a_1,\ldots,a_m)\) is the Frobenius number, \(R(\hat{C})=\max_{(i,j)}\max_s\{r_{i,j}^{s/d}(\hat{C})\} \). For some class of \(2k\)-vertex primitive digraphs, it is proved, that the improved formula gives the value of estimation \(2k\), and the previous formula gives the value of estimation \(3k-2\).Functions and eigenvectors of partially known matrices with applications to network analysis.https://www.zbmath.org/1459.650462021-05-28T16:06:00+00:00"Al Mugahwi, Mohammed"https://www.zbmath.org/authors/?q=ai:al-mugahwi.mohammed"De la Cruz Cabrera, Omar"https://www.zbmath.org/authors/?q=ai:de-la-cruz-cabrera.omar"Noschese, Silvia"https://www.zbmath.org/authors/?q=ai:noschese.silvia"Reichel, Lothar"https://www.zbmath.org/authors/?q=ai:reichel.lotharSummary: Matrix functions play an important role in applied mathematics. In network analysis, in particular, the exponential of the adjacency matrix associated with a network provides valuable information about connectivity, as well as about the relative importance or centrality of nodes. Another popular approach to rank the nodes of a network is to compute the left Perron vector of the adjacency matrix for the network. The present article addresses the problem of evaluating matrix functions, as well as computing an approximation to the left Perron vector, when only some of the columns and/or some of the rows of the adjacency matrix are known. Applications to network analysis are considered, when only some sampled columns and/or rows of the adjacency matrix that defines the network are available. A sampling scheme that takes the connectivity of the network into account is described. Computed examples illustrate the performance of the methods discussed.Computing enclosures for the matrix exponential.https://www.zbmath.org/1459.650562021-05-28T16:06:00+00:00"Frommer, Andreas"https://www.zbmath.org/authors/?q=ai:frommer.andreas"Hashemi, Behnam"https://www.zbmath.org/authors/?q=ai:hashemi.behnamBernoulli F-polynomials and fibo-Bernoulli matrices.https://www.zbmath.org/1459.110642021-05-28T16:06:00+00:00"Kuş, Semra"https://www.zbmath.org/authors/?q=ai:kus.semra"Tuglu, Naim"https://www.zbmath.org/authors/?q=ai:tuglu.naim"Kim, Taekyun"https://www.zbmath.org/authors/?q=ai:kim.taekyunSummary: In this article, we define the Euler-Fibonacci numbers, polynomials and their exponential generating function. Several relations are established involving the Bernoulli F-polynomials, the Euler-Fibonacci numbers and the Euler-Fibonacci polynomials. A new exponential generating function is obtained for the Bernoulli F-polynomials. Also, we describe the Fibo-Bernoulli matrix, the Fibo-Euler matrix and the Fibo-Euler polynomial matrix by using the Bernoulli F-polynomials, the Euler-Fibonacci numbers and the Euler-Fibonacci polynomials, respectively. Factorization of the Fibo-Bernoulli matrix is obtained by using the generalized Fibo-Pascal matrix and a special matrix whose entries are the Bernoulli-Fibonacci numbers. The inverse of the Fibo-Bernoulli matrix is also found.