Search

The classical Pauli group can be obtained as the central product of the dihedral group of 8 elements with the cyclic group of order 4. Inspired by this characterization, we introduce the notion of central product of Cayley graphs, which allows to regard the Cayley graph of a central product of groups as a quotient of the Cartesian product of the Cayley graphs of the factor groups. We focus our attention on the Cayley graph C a y (P n , S P n ) of the generalized Pauli group P n on n -qubits; in fact, P n may be decomposed as the central product of finite 2-groups, and a suitable choice of the generating set S P n allows us to recognize the structure of central product of graphs in C a y (P n , S P n ). Using this approach, we are able to recursively construct the adjacency matrix of C a y (P n , S P n ) for each n ≥ 1 , and to explicitly describe its spectrum and the associated eigenvectors. It turns out that C a y (P n , S P n ) is a (3 n + 2) -regular bipartite graph on 4 n + 1 vertices, and it has integral spectrum. This is a highly nontrivial property if one considers that, by choosing as a generating set for P 1 the three classical Pauli matrices, one gets the so-called Möbius-Kantor graph, belonging to the class of generalized Petersen graphs, whose spectrum is not integral. [ABSTRACT FROM AUTHOR]

Abstract: Using the spectral distribution associated with the adjacency matrix of graphs, we introduce a new method of calculation of amplitudes of continuous-time quantum walk on some rather important graphs, such as line, cycle graph C n , complete graph K n , graph G n , finite path and some other finite and infinite graphs, where all are connected with orthogonal polynomials such as Hermite, Laguerre, Tchebichef, and other orthogonal polynomials. It is shown that using the spectral distribution, one can obtain the infinite time asymptotic behavior of amplitudes simply by using the method of stationary phase approximation (WKB approximation), where as an example, the method is applied to star, two-dimensional comb lattices, infinite Hermite and Laguerre graphs. Also by using the Gauss quadrature formula one can approximate the infinite graphs with finite ones and vice versa, in order to derive large time asymptotic behavior by WKB method. Likewise, using this method, some new graphs are introduced, where their amplitudes are proportional to the product of amplitudes of some elementary graphs, even though the graphs themselves are not the same as the Cartesian product of their elementary graphs. Finally, by calculating the mean end to end distance of some infinite graphs at large enough times, it is shown that continuous-time quantum walk at different infinite graphs belong to different universality classes which are also different from those of the corresponding classical ones. [Copyright &y& Elsevier]

The relationship between anatomic and resting state functional connectivity of large-scale brain networks is a major focus of current research. In previous work, we introduced a model based on eigen decomposition of the Laplacian which predicts the functional network from the structural network in healthy brains. In this work, we apply the eigen decomposition model to two types of epilepsy; temporal lobe epilepsy associated with mesial temporal sclerosis, and MRI-normal temporal lobe epilepsy. Our findings show that the eigen relationship between function and structure holds for patients with temporal lobe epilepsy as well as normal individuals. These results suggest that the brain under TLE conditions reconfigures and rewires the fine-scale connectivity (a process which the model parameters are putatively sensitive to), in order to achieve the necessary structure-function relationship. [ABSTRACT FROM AUTHOR]

The goal of this article is to display a Q -polynomial structure for the Attenuated Space poset A q (N , M). The poset A q (N , M) is briefly described as follows. Start with an (N + M) -dimensional vector space H over a finite field with q elements. Fix an M -dimensional subspace h of H. The vertex set X of A q (N , M) consists of the subspaces of H that have zero intersection with h. The partial order on X is the inclusion relation. The Q -polynomial structure involves two matrices A , A ⁎ ∈ Mat X (C) with the following entries. For y , z ∈ X the matrix A has (y , z) -entry 1 (if y covers z); q dim y (if z covers y); and 0 (if neither of y , z covers the other). The matrix A ⁎ is diagonal, with (y , y) -entry q − dim y for all y ∈ X. By construction, A ⁎ has N + 1 eigenspaces. By construction, A acts on these eigenspaces in a (block) tridiagonal fashion. We show that A is diagonalizable, with 2 N + 1 eigenspaces. We show that A ⁎ acts on these eigenspaces in a (block) tridiagonal fashion. Using this action, we show that A is Q -polynomial. We show that A , A ⁎ satisfy a pair of relations called the tridiagonal relations. We consider the subalgebra T of Mat X (C) generated by A , A ⁎. We show that A , A ⁎ act on each irreducible T -module as a Leonard pair. [ABSTRACT FROM AUTHOR]

A graph is determined by its spectrum if there is not another graph with the same spectrum. Cámara and Haemers proved that the graph K n ∖ C k , obtained from the complete graph K n with n vertices by deleting all edges of a cycle C k with k vertices, is determined by its spectrum for k ∈ { 3 , 4 , 5 } , but not for k = 6. In this paper, we show that k = 6 is the unique exception for the spectral determination of K n ∖ C k. [ABSTRACT FROM AUTHOR]

For every finite Coxeter group Γ, each positive braid in the corresponding braid group admits a unique decomposition as a finite sequence of elements of Γ, the so-called Garside-normal form. The study of the associated adjacency matrix Adj ( Γ ) allows to count the number of Garside-normal form of a given length. In this paper we prove that the characteristic polynomial of Adj ( B n ) divides the one of Adj ( B n + 1 ) . The key point is the use of a Hopf algebra based on signed permutations. A similar result was already known for the type A . We observe that this does not hold for type D . The other Coxeter types ( I , E , F and H ) are also studied. [ABSTRACT FROM AUTHOR]

We prove that the only trees that admit perfect state transfer according to the adjacency matrix model are P 2 and P 3. This answers a question first asked by Godsil in 2012 and proves a conjecture by Coutinho and Liu from 2015. [ABSTRACT FROM AUTHOR]

In Athreya et al. (2021), models from population genetics were used to define stochastic dynamics in the space of graphons arising as continuum limits of dense graphs. In the present paper we exhibit an example of a simple neutral population genetics model for which this dynamics is a Markovian diffusion that can be characterized as the solution of a martingale problem. In particular, we consider a Markov chain in the space of finite graphs that resembles a Moran model with resampling and mutation. We encode the finite graphs as graphemes, which can be represented as a triple consisting of a vertex set (or more generally, a topological space), an adjacency matrix, and a sampling (Borel) measure. We equip the space of graphons with convergence of sample subgraph densities and show that the grapheme-valued Markov chain converges to a grapheme-valued diffusion as the number of vertices goes to infinity. We show that the grapheme-valued diffusion has a stationary distribution that is linked to the Griffiths–Engen–McCloskey (GEM) distribution. In a companion paper (Greven et al. 2023), we build up a general theory for obtaining grapheme-valued diffusions via genealogies of models in population genetics. [ABSTRACT FROM AUTHOR]

Abstract: The Randić index R of a graph G is defined as the sum of over all edges of G, where denotes the degree of a vertex in G. is the largest eigenvalue of the signless Laplacian matrix of G, where D is the diagonal matrix with degrees of the vertices on the main diagonal and A is the adjacency matrix of G. Hansen and Lucas [18] conjectured (1) and equality holds for and (2) with equality if and only if for and for , respectively. In this paper, we prove the conjecture (1) and obtain a result very close to the conjecture (2). Moreover, we give some results relating harmonic index and the largest eigenvalue of the adjacency matrix. [Copyright &y& Elsevier]

We compute the elementary divisors of the adjacency and Laplacian matrices of families of polar graphs. These graphs have as vertices the isotropic one-dimensional subspaces of finite vector spaces with respect to non-degenerate forms, with adjacency given by orthogonality. [ABSTRACT FROM AUTHOR]

The critical group of a finite connected graph is an abelian group defined by the Smith normal form of its Laplacian. Let q be a power of a prime and H be a multiplicative subgroup of K = F q. By Cay (K , H) we denote the Cayley graph on the additive group of K with "connection" set H. A strongly regular graph of the form Cay (K , H) is called a cyclotomic strongly regular graph. Let ℓ > 2 and p be primes such that p is primitive (mod ℓ). We compute the critical groups of a family of cyclotomic strongly regular graphs for which q = p (ℓ − 1) t (with t ∈ N) and H is the unique multiplicative subgroup of order k = q − 1 ℓ. These graphs were first discovered by van Lint and Schrijver in [24]. [ABSTRACT FROM AUTHOR]

Abstract The canonical double cover D (Γ) of a graph Γ is the direct product of Γ and K 2. If Aut (D (Γ)) = Aut (Γ) × Z 2 then Γ is called stable; otherwise Γ is called unstable. An unstable graph is nontrivially unstable if it is connected, non-bipartite and distinct vertices have different neighborhoods. In this paper we prove that every circulant graph of odd prime order is stable and there is no arc-transitive nontrivially unstable circulant graph. The latter answers a question of Wilson in 2008. We also give infinitely many counterexamples to a conjecture of Marušič, Scapellato and Zagaglia Salvi in 1989 by constructing a family of stable circulant graphs with compatible adjacency matrices. [ABSTRACT FROM AUTHOR]

Abstract Motivated by the study of genomes evolving by reversals, we consider pseudograph transformations known as "pressing sequences". In particular, we address the question of when a graph has precisely one pressing sequence resulting in the empty graph, thus answering an question from Cooper and Davis (2015) [13]. We characterize such "uniquely pressable" graphs, count the number of them on a given number of vertices, and provide a polynomial-time recognition algorithm. We conclude with several open questions. [ABSTRACT FROM AUTHOR]

Let G be a connected graph on n vertices with adjacency matrix A G. Associated to G is a polynomial d G (x 1 , ... , x n) of degree n in n variables, obtained as the determinant of the matrix M G (x 1 , ... , x n) , where M G = Diag (x 1 , ... , x n) − A G. We investigate in this article the set V d G (r) of non-negative values taken by this polynomial when x 1 , ... , x n ≥ r ≥ 1. We show that V d G (1) = Z ≥ 0. We show that for a large class of graphs one also has V d G (2) = Z ≥ 0. When V d G (2) ≠ Z ≥ 0 , we show that for many graphs V d G (2) is dense in Z ≥ 0. We give numerical evidence that in many cases, the complement of V d G (2) in Z ≥ 0 might in fact be finite. As a byproduct of our results, we show that every graph can be endowed with an arithmetical structure whose associated group is trivial. [ABSTRACT FROM AUTHOR]

Abstract: Analyzing human crowds is an important issue in video surveillance and is a challenging task due to their nature of non-rigid shapes. In this paper, optical flows are first estimated and then used for a clue to cluster human crowds into groups in unsupervised manner using our proposed method of adjacency-matrix based clustering (AMC). While the clusters of human crowds are obtained, their behaviors with attributes, orientation, position and crowd size, are characterized by a model of force field. Finally, we can predict the behaviors of human crowds based on the model and then detect if any anomalies of human crowd(s) present in the scene. Experimental results obtained by using extensive dataset show that our system is effective in detecting anomalous events for uncontrolled environment of surveillance videos. [Copyright &y& Elsevier]

We introduce the concept of weakly distance-regular digraph and study some of its basic properties. In particular, the (standard) distance-regular digraphs, introduced by Damerell, turn out to be those weakly distance-regular digraphs which have a normal adjacency matrix. As happens in the case of distance-regular graphs, the study is greatly facilitated by a family of orthogonal polynomials called the distance polynomials. For instance, these polynomials are used to derive the spectrum of a weakly distance-regular digraph. Some examples of these digraphs, such as the butterfly and the cycle prefix digraph which are interesting for their applications, are analyzed in the light of the developed theory. Also, some new constructions involving the line digraph and other techniques are presented. [Copyright &y& Elsevier]

Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random. [ABSTRACT FROM AUTHOR]

Spectral characterization of graphs is an important topic in spectral graph theory. An oriented graph G σ is obtained from a simple undirected graph G by assigning to every edge of G a direction so that G σ becomes a directed graph. The skew-adjacency matrix of an oriented graph G σ is a real skew-symmetric matrix S (G σ) = (s i j) , where s i j = − s j i = 1 if (i , j) is an arc; s i j = s j i = 0 otherwise. Let G σ and H τ be two oriented graphs whose skew-adjacency matrices are S (G σ) and S (H τ) , respectively. We say G σ is R -cospectral to H τ if t J − S (G σ) and t J − S (H τ) have the same spectrum for any t ∈ R , where J is the all-ones matrix. An oriented graph G σ is said to be determined by the generalized skew spectrum (DGSS for short), if any oriented graph which is R -cospectral to G σ is isomorphic to G σ. Let W (G σ) = [ e , S (G σ) e , S 2 (G σ) e , ... , S n − 1 (G σ) e ] be the skew-walk-matrix of G σ , where e is the all-ones vector. A theorem of Qiu, Wang and Wang [9] states that if G σ is a self-converse oriented graph and 2 − ⌊ n 2 ⌋ det ⁡ W (G σ) is odd and square-free, then G σ is DGSS. In this paper, based on the Smith Normal Form of the skew-walk-matrix of G σ we obtain our main result: Let q be a prime and G σ be a self-converse oriented graph on n vertices with det ⁡ W (G σ) ≠ 0. Assume that r a n k q (W (G σ)) = n − 1 if q is an odd prime, and r a n k q (W (G σ)) = ⌈ n 2 ⌉ if q = 2. If Q is a regular rational orthogonal matrix satisfying Q T S (G σ) Q = S (H τ) for some oriented graph H τ , then the level of Q divides d n (W (G σ)) q , where d n (W (G σ)) is the n -th invariant factor of W (G σ). Consequently, it leads to an easier way to prove Qiu, Wang and Wang's theorem above. [ABSTRACT FROM AUTHOR]

Graph eigenvalues are examples of totally real algebraic integers, i.e. roots of real-rooted monic polynomials with integer coefficients. Conversely, the fact that every totally real algebraic integer occurs as an eigenvalue of some finite graph is a deep and remarkable result, conjectured forty years ago by Hoffman, and proved seventeen years later by Estes. This short paper provides an independent and elementary proof of a stronger statement, namely that the graph may actually be chosen to be a tree. As a by-product, our result implies that the atoms of the limiting spectrum of n × n symmetric matrices with independent Bernoulli ( c n ) entries are exactly the totally real algebraic integers. This settles an open problem raised by Ben Arous (2010). [ABSTRACT FROM AUTHOR]

Even though it is well known that binary values are common in graph applications (e.g., adjacency matrix), how to leverage the phenomenon for efficiency has not yet been adequately explored. This paper presents a systematic study on how to unlock the potential of the bit-level optimizations of graph computations that involve binary values. It proposes a two-level representation named Bit-Block Compressed Sparse Row (B2SR) and presents a series of optimizations to the graph operations on B2SR by the intrinsics of modern GPUs. It additionally introduces Deep Reinforcement Learning (DRL) as an efficient way to best configure the bit-level optimizations on the fly. The DQN-based adaptive tile size selector with dedicated model training can reach 68% prediction accuracy. Evaluations on the NVIDIA Pascal and Volta GPUs show that the optimizations bring up to 40▪ and 6555▪ for essential GraphBLAS kernels SpMV and SpGEMM, respectively, accelerating GraphBLAS-based BFS by up to 433▪, SSSP, PR, and CC 35▪, and TC 52▪. • The performance of GraphBLAS algorithms can be accelerated with sparse bit storage format and bit manipulation. • Sparse operators such as SpMV and SpGEMM can be accelerated with bit intrinsics on GPU when contains only binary values. • A DRL-based adaptive scheme can be utilized to select the best bit sparse format based on sparse matrix features. [ABSTRACT FROM AUTHOR]

Abstract: Induction of tumor angiogenesis is among the hallmarks of cancer and a driver of metastatic cascade initiation. Recent advances in high-resolution imaging enable highly detailed three-dimensional geometrical representation of the whole-tumor microvascular architecture. This enormous increase in complexity of image-based data necessitates the application of informatics methods for the analysis, mining and reconstruction of these spatial graph data structures. We present a novel methodology that combines ex-vivo high-resolution micro-computed tomography imaging data with a bioimage informatics algorithm to track and reconstruct the whole-tumor vasculature of a human breast cancer model. The reconstructed tumor vascular network is used as an input of a computational model that estimates blood flow in each segment of the tumor microvascular network. This formulation involves a well-established biophysical model and an optimization algorithm that ensures mass balance and detailed monitoring of all the vessels that feed and drain blood from the tumor microvascular network. Perfusion maps for the whole-tumor microvascular network are computed. Morphological and hemodynamic indices from different regions are compared to infer their role in overall tumor perfusion. [Copyright &y& Elsevier]

Abstract: A five-channel (1H, 19F, 31P, 27Al, 13C) 2.5mm magic-angle-spinning (MAS) nuclear magnetic resonance (NMR) probe is used in combination with three separate receivers for the parallel acquisitions of one (1D) and two-dimensional (2D) NMR spectra in model fluorinated aluminophosphate and porous Al-based metal-organic framework (MOF). Possible combinations to record simultaneously spectra using this set-up are presented, including (i) parallel acquisitions of quantitative 1D NMR spectra of solids containing nuclei with contrasted T 1 relaxation rates and (ii) parallel acquisitions of 2D heteronuclear NMR spectra. In solids containing numerous different NMR-accessible nuclei, the number of NMR experiments that have to be acquired to get accurate structural information is high. The strategy we present here, i.e. the multiplication of both the number of irradiation channels in the probe and the number of parallel receivers, offers one possibility to optimize this measurement time. [Copyright &y& Elsevier]

Abstract: Methods of enumeration of spanning trees in a finite graph, a problem related to various areas of mathematics and physics, have been investigated by many mathematicians and physicists. A graph G is said to be n-rotational symmetric if the cyclic group of order n is a subgroup of the automorphism group of G. Some recent studies on the enumeration of spanning trees and the calculation of their asymptotic growth constants on regular lattices with toroidal boundary condition were carried out by physicists. A natural question is to consider the problem of enumeration of spanning trees of lattices with cylindrical boundary condition, which are the so-called rotational symmetric graphs. Suppose G is a graph of order N with n-rotational symmetry and all orbits have size n, which has n isomorphic induced subgraphs . In this paper, we prove that if there exists no edge between and for , then the number of spanning trees of G can be expressed in terms of the product of the weighted enumerations of spanning trees of n graphs ''s for , where has vertices if and vertices otherwise. As applications we obtain explicit expressions for the numbers of spanning trees and asymptotic tree number entropies for five lattices with cylindrical boundary condition in the context of physics. [Copyright &y& Elsevier]

Abstract: Let k be a positive integer and let G be a graph of order . It is proved that the sum of k largest eigenvalues of G is at most . This bound is shown to be best possible in the sense that for every k there exist graphs whose sum is . A generalization to arbitrary symmetric matrices is given. [Copyright &y& Elsevier]

Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider the classic model of random geometric graphs where n points are scattered uniformly in a square of area n , and two points have an edge between them if and only if their Euclidean distance is less than r. The reconstruction problem then consists of inferring the vertex positions, up to the symmetries of the square, given only the adjacency matrix of the resulting graph. We give an algorithm that, if r = n α for any 0 < α < 1 / 2 , with high probability reconstructs the vertex positions with a maximum error of O (n β) where β = 1 / 2 − (4 / 3) α , until α ≥ 3 / 8 where β = 0 and the error becomes O (log n). This improves over earlier results, which were unable to reconstruct with error less than r. Our method estimates Euclidean distances using a hybrid of graph distances and short-range estimates based on the number of common neighbors. We extend our results to the surface of the sphere in R 3 and to hypercubes in any constant fixed dimension. [ABSTRACT FROM AUTHOR]

Abstract Matrix functions of the adjacency matrix are very useful for understanding important structural properties of graphs and networks, such as communicability, node centrality, bipartivity, and many more. They are also intimately related to the solution of differential equations describing dynamical processes on graphs and networks. Here, we propose a new matrix function based on the Gaussianization of the adjacency matrix of a graph. This function gives more weight to a selected reference eigenvalue λ ref , which may be located in any region of the graph spectra. We show here that this matrix function can be derived from physical models that consider the interactions between nearest and next-nearest neighbors in the graph. We first obtain a few mathematical results for the trace of this matrix function when λ ref = − 1 (H − 1) for simple graphs as well as for random graphs. We also provide a combinatorial interpretation of this index in terms of subgraphs in the graph, and in terms of the competition pressure among agents in a complex system. Finally, we apply this index to the study of magnetic properties of molecules emerging due to spin interactions as well as to studying the temporal evolution of the international trade network in the period 1992–2002. In both cases we give a clear phenomenological interpretation of the processes described. [ABSTRACT FROM AUTHOR]

In this note we show that the singular probability of the adjacency matrix of a random d -regular graph on n vertices, where d is fixed and n → ∞ , is bounded by n − 1 / 3 + o (1) . This improves a recent bound by Huang in Huang (2021). Our method is based on the study of the singularity problem modulo a prime developed in Huang (2021) (and also partially in Mészáros, 2021; Nguyen and Wood, 2018), together with an inverse-type result on the decay of the characteristic function. The latter is related to the inverse Kneser's problem in combinatorics. [ABSTRACT FROM AUTHOR]

Thus far, digraphs that are uniquely determined by their Hermitian spectra have proven elusive. Instead, researchers have turned to spectral determination of classes of switching equivalent digraphs, rather than individual digraphs. In the present paper, we consider the traditional notion: a digraph (or mixed graph) is said to be strongly determined by its Hermitian spectrum (abbreviated SHDS) if it is isomorphic to each digraph to which it is cospectral. Convincing numerical evidence to support the claim that this property is extremely rare is provided. Nonetheless, the first infinite family of connected digraphs that is SHDS is constructed. This family is obtained via the introduction of twin vertices into a structure that is named negative tetrahedron. This special digraph, that exhibits extreme spectral behavior, is contained in the surprisingly small collection of all digraphs with exactly one negative eigenvalue, which is determined as an intermediate result. [ABSTRACT FROM AUTHOR]

It is well-known that a connected regular graph is strongly-regular if and only if its adjacency matrix has exactly three eigenvalues. Let B denote an integral square matrix and 〈 B 〉 denote the subring of the full matrix ring generated by B . Then 〈 B 〉 is a free Z -module of finite rank, which guarantees that there are only finitely many ideals of 〈 B 〉 with given finite index. Thus, the formal Dirichlet series ζ 〈 B 〉 ( s ) = ∑ n ≥ 1 a n n − s is well-defined where a n is the number of ideals of 〈 B 〉 with index n . In this article we aim to find an explicit form of ζ 〈 B 〉 ( s ) when B has exactly three eigenvalues all of which are integral, e.g., the adjacency matrix of a strongly-regular graph which is not a conference graph with a non-squared number of vertices. By isomorphism theorem for rings, 〈 B 〉 is isomorphic to Z [ x ] / m ( x ) Z [ x ] where m ( x ) is the minimal polynomial of B over Q , and Z [ x ] / m ( x ) Z [ x ] is isomorphic to Z [ x ] / m ( x + γ ) Z [ x ] for each γ ∈ Z . Thus, the problem is reduced to counting the number of ideals of Z [ x ] / x ( x − α ) ( x − β ) Z [ x ] with given finite index where 0 , α and β are distinct integers. [ABSTRACT FROM AUTHOR]

Accurate 3D human pose estimation is a challenging task due to occlusion and depth ambiguity. In this paper, we introduce a multi-hop graph transformer network designed for 2D-to-3D human pose estimation in videos by leveraging the strengths of multi-head self-attention and multi-hop graph convolutional networks with disentangled neighborhoods to capture spatio-temporal dependencies and handle long-range interactions. The proposed network architecture consists of a graph attention block composed of stacked layers of multi-head self-attention and graph convolution with learnable adjacency matrix, and a multi-hop graph convolutional block comprised of multi-hop convolutional and dilated convolutional layers. The combination of multi-head self-attention and multi-hop graph convolutional layers enables the model to capture both local and global dependencies, while the integration of dilated convolutional layers enhances the model's ability to handle spatial details required for accurate localization of the human body joints. Extensive experiments demonstrate the effectiveness and generalization ability of our model, achieving competitive performance on benchmark datasets. [ABSTRACT FROM AUTHOR]

A graph is prime if it does not admit a partition (A , B) of its vertex set such that min { | A | , | B | } ≥ 2 and the rank of the A × B submatrix of its adjacency matrix is at most 1. A vertex v of a graph is non-essential if at least two of the three kinds of vertex-minor reductions at v result in prime graphs. In 1994, Allys proved that every prime graph with at least four vertices has a non-essential vertex unless it is locally equivalent to a cycle graph. We prove that every prime graph with at least four vertices has at least two non-essential vertices unless it is locally equivalent to a cycle graph. As a corollary, we show that for a prime graph G with at least six vertices and a vertex x , there is a vertex v ≠ x such that G ∖ v or G ∗ v ∖ v is prime, unless x is adjacent to all other vertices and G is isomorphic to a particular graph on odd number of vertices. Furthermore, we show that a prime graph with at least four vertices has at least three non-essential vertices, unless it is locally equivalent to a graph consisting of at least two internally-disjoint paths between two fixed distinct vertices having no common neighbors. We also prove analogous results for pivot-minors. [ABSTRACT FROM AUTHOR]

The positive part U q + of U q ( sl ˆ 2) has a presentation with two generators W 0 , W 1 and two relations called the q -Serre relations. The algebra U q + contains some elements, said to be alternating. There are four kinds of alternating elements, denoted { W − k } k ∈ N , { W k + 1 } k ∈ N , { G k + 1 } k ∈ N , { G ˜ k + 1 } k ∈ N. The alternating elements of each kind mutually commute. A tridiagonal pair is an ordered pair of diagonalizable linear maps A , A ⁎ on a nonzero, finite-dimensional vector space V , that each act in a (block) tridiagonal fashion on the eigenspaces of the other one. Let A , A ⁎ denote a tridiagonal pair on V. Associated with this pair are six well-known direct sum decompositions of V ; these are the eigenspace decompositions of A and A ⁎ , along with four decompositions of V that are often called split. In our main results, we assume that A , A ⁎ has q -Serre type. Under this assumption A , A ⁎ satisfy the q -Serre relations, and V becomes an irreducible U q + -module on which W 0 = A and W 1 = A ⁎. We describe how the alternating elements of U q + act on the above six decompositions of V. We show that for each decomposition, every alternating element acts in either a (block) diagonal, (block) upper bidiagonal, (block) lower bidiagonal, or (block) tridiagonal fashion. We investigate two special cases in detail. In the first case the eigenspaces of A and A ⁎ all have dimension one. In the second case A and A ⁎ are obtained by adjusting the adjacency matrix and a dual adjacency matrix of a distance-regular graph that has classical parameters and is formally self-dual. [ABSTRACT FROM AUTHOR]

• The graph weighted reinforcement network (GWRNet) is proposed to accurately diagnose the fault of rotating machines under small samples and strong noise. Two highlights of this study can be summarized as follows. • The time and frequency domain characteristics of the vibration signal are extracted, and the adjacency matrix is constructed based on the Euclidean distance of these characteristics to achieve node pre-classification. • The graph-weighting enhanced mechanism is used to aggregate the node features in the graph, suppress the background noise interference during feature extraction, and realize rotating machinery fault diagnosis under strong noise conditions. Available fault vibration signals of large rotating machines are usually limited and consist of strong noise. Existing deep learning methods do not sufficiently extract the correlation relationship between samples, and the process of extracting features is easily disturbed by noise. Therefore, the accuracy of rotating machinery fault diagnosis needs further improvement. A graph-weighted reinforcement network (GWRNet) is proposed to accurately diagnose the faults of rotating machines under small samples and strong noise. First, an adjacency matrix was constructed by measuring the Euclidean distance of the time- and frequency-domain characteristics of small samples to achieve the pre-classification of nodes. Second, the node feature aggregation strategy was designed by dynamically enhancing the largest weight of the multiheaded attention matrix to suppress strong noise interference. Finally, the effectiveness of the proposed method was verified using datasets from the drivetrain diagnostics simulator (DDS) test rig and wind turbine gearboxes. [ABSTRACT FROM AUTHOR]

This paper deals with the topological entropy for hom Markov shifts T M on d -tree. If M is a reducible adjacency matrix with q irreducible components M 1 , ⋯ , M q , we show that h (T M) = max 1 ≤ i ≤ q ⁡ h (T M i ) fails generally, and present a case study with full characterization in terms of the equality. Though that it is likely the sets { h (T M) : M is binary and irreducible } and { h (T X) : X is a one-sided shift } are not coincident, we show the two sets share the common closure. Despite the fact that such closure is proved to contain the interval [ d log ⁡ 2 , ∞) , numerical experiments suggest its complement contain open intervals. [ABSTRACT FROM AUTHOR]

• Modal controllability and synchronizability increase in the internet gaming addicts. • Addiction mediates the relationship between brain controllability and anxiety state. • Regional morphometry is associated with the brain controllability. • Specific regional controllability could deeply affect brain states. Internet gaming addiction (IGD) is a common disease in teenagers which usually reflects the abnormalities in brain function or structure. Several computational models have been applied to investigate the characteristic of IGD brain networks, for instance, the conception of brain controllability. The primary objective of this study was to explore the relationship between brain controllability and IGD related clinical behaviour. A sample of 101 subjects, including 49 IGD patients and 52 normal controls, were recruited to undergo MR T1 and DTI scanning. Specifically, the MR images were used to generate the white matter connectivity matrix and the morphometry similarity network. The morphometry similarity network was then divided into several communities using modular decomposition. After, average controllability, modal controllability and synchronizability were calculated through measuring the adjacency matrix. The results indicated that the IGD group had greater synchronizability and modal controllability compared to that of the control group, and different morphological-based brain communities had different controllability properties. Furthermore, the addiction demonstrated the mediating effects between nodal or modular brain controllability as well as anxiety. In conclusion, brain controllability could be a potential biomarker of IGD. [ABSTRACT FROM AUTHOR]

An oriented graph G σ is a digraph without loops and multiple arcs, where G is called the underlying graph of G σ . Let S ( G σ ) denote the skew-adjacency matrix of G σ , and A ( G ) be the adjacency matrix of G . The skew-rank of G σ , written as s r ( G σ ) , refers to the rank of S ( G σ ) , which is always even since S ( G σ ) is skew symmetric. A natural problem is: How about the relation between the skew-rank of an oriented graph G σ and the rank of its underlying graph? In this paper, we focus our attention on this problem. Denote by d ( G ) the dimension of cycle spaces of G , that is d ( G ) = | E ( G ) | − | V ( G ) | + θ ( G ) , where θ ( G ) denotes the number of connected components of G . It is proved that s r ( G σ ) ≤ r ( G ) + 2 d ( G ) for an oriented graph G σ , the oriented graphs G σ whose skew-rank attains the upper bound are characterized. [ABSTRACT FROM AUTHOR]

We investigate the algebraic degree of circulant graphs, i.e. the dimension of the splitting field of the characteristic polynomial of the associated adjacency matrix over the rationals. Studying the algebraic degree of graphs seems more natural than characterizing graphs with integral spectra only. We prove that the algebraic degree of circulant graphs on n vertices is bounded above by φ (n) / 2 , where φ denotes Euler's totient function, and that the family of cycle graphs provides a family of maximum algebraic degree within the family of all circulant graphs. Moreover, we precisely determine the algebraic degree of circulant graphs on a prime number of vertices. [ABSTRACT FROM AUTHOR]

Deep learning-based remaining useful life (RUL) prediction methods have achieved great success due to their powerful capacity of feature representation especially when big data of condition monitoring is available. However, how to fuse multi-sensor information to facilitate RUL prediction accuracy remains a challenging problem due to the complex temporal and spatial dependencies within multi-sensor signals. To address this problem, we propose a dual-view graph Transformer, named as DVGTformer, for RUL prediction, which can fully learn potential degradation patterns from multi-sensor signals by capturing complex correlations within them. The proposed method involves the design of a novel graph Transformer, named as GTformer, by collaboratively integrating learnable graph adjacency matrix and multi-head self-attention to learn structural and dynamic correlations between the nodes of graphs. We then construct the DVGTformer for RUL prediction based on the GTformer. Each layer of a DVGTformer is formed by cascading a temporal-view GTformer layer and a spatial-view GTformer layer to fuse temporal and spatial information across time stamps and sensor nodes. Experimental results on the benchmark CMAPSS dataset and a wind turbine dataset from real applications show that our method consistently provides accurate and robust RUL prediction results compared with the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

We show that the maximum cardinality of an equiangular line system in R 18 is at most 59. Our proof includes a novel application of the Jacobi identity for complementary subgraphs. In particular, we show that there does not exist a graph whose adjacency matrix has characteristic polynomial (x − 22) (x − 2) 42 (x + 6) 15 (x + 8) 2. [ABSTRACT FROM AUTHOR]

Signal processing is an important research topic. This paper aims to provide a general framework for signal processing on arbitrary dynamic graphs. We propose a new graph transformation by defining a temporal-attention product. This product transforms the sequence of graph time slices with arbitrary topology and number of nodes into a static graph, effectively capturing graph signals' spatio-temporal dynamic evolution process. The temporal-attention product graph provides a solid mathematical foundation to model the time-dependent graph signal processes as martingales. The weighted adjacency matrix obtained by temporal-attention products is a block tridiagonal matrix, which has been extensively studied. Therefore, it is general and convenient to perform graph signal processing on this new static graph. We apply two real datasets to illustrate the effectiveness of spectral graph wavelet transform based on temporal-attention product. For one of the datasets with no graph structure, we learn the graph weights through a neural network. [ABSTRACT FROM AUTHOR]

We investigate spectral conditions on Hermitian matrices of roots of unity. Our main results are conjecturally sharp upper bounds on the number of residue classes of the characteristic polynomial of such matrices modulo ideals generated by powers of (1 − ζ) , where ζ is a root of unity. We also prove a generalisation of a classical result of Harary and Schwenk about a relation for traces of powers of a graph-adjacency matrix, which is a crucial ingredient for the proofs of our main results. [ABSTRACT FROM AUTHOR]

In order to improve the accuracy of fault diagnosis, researchers are constantly trying to develop new diagnostic models. However, limited by the inherent thinking of human beings, it has always been difficult to build a pioneering architecture for rotating machinery fault diagnosis. In order to solve this problem, this paper uses reinforcement learning algorithm based on adjacency matrix to carry out network architecture search (NAS) of rotating machinery fault diagnosis model. A reinforcement learning agent for deep deterministic policy gradient (DDPG) is developed based on actor–critic neural networks. The observation state of reinforcement learning is used to develop the graph neural network (GNN) diagnosis model, and the diagnosis accuracy is fed back to the agent as a reward for updating the reinforcement learning parameters. The MFPT bearing fault datasets and the developed gear pitting fault experimental data are used to validate the proposed network architecture search method based on reinforcement learning (RL-NAS). The proposed method is proved to be practical and effective in various aspects such as fault diagnosis ability, search space, search efficiency and multi-working condition performance. [ABSTRACT FROM AUTHOR]

Abstract In this paper we characterize graphs which maximize the spectral radius of their adjacency matrix over all graphs of Colin de Verdière parameter at most m. We also characterize graphs of maximum spectral radius with no H as a minor when H is either K r or K s , t. Interestingly, the extremal graphs match those which maximize the number of edges over all graphs with no H as a minor when r and s are small, but not when they are larger. [ABSTRACT FROM AUTHOR]

Abstract We provide a unified variational inequality framework for the study of fundamental properties of the Nash equilibrium in network games. We identify several conditions on the underlying network (in terms of spectral norm, infinity norm and minimum eigenvalue of its adjacency matrix) that guarantee existence, uniqueness, convergence and continuity of equilibrium in general network games with multidimensional and possibly constrained strategy sets. We delineate the relations between these conditions and characterize classes of networks that satisfy each of these conditions. [ABSTRACT FROM AUTHOR]

Abstract: A divisible design graph is a graph whose adjacency matrix is the incidence matrix of a divisible design. Divisible design graphs are a natural generalization of -graphs, and like -graphs they make a link between combinatorial design theory and algebraic graph theory. The study of divisible design graphs benefits from, and contributes to, both parts. Using information of the eigenvalues of the adjacency matrix, we obtain necessary conditions for existence. Old results of Bose and Connor on symmetric divisible designs give other conditions and information on the structure. Many constructions are given using various combinatorial structures, such as -graphs, distance-regular graphs, symmetric divisible designs, Hadamard matrices, and symmetric balanced generalized weighing matrices. Several divisible design graphs are characterized in terms of the parameters. [ABSTRACT FROM AUTHOR]

Abstract: This paper describes numerical characterization of proteome maps based on partial ordering of protein spots with respect to the mass and the charge. The partial ordering diagram is embedded directly over the 2D map and the corresponding adjacency matrix is constructed. The adjacency matrix is augmented by including the information on the abundance of proteins in a gel as suitably scaled diagonal entries of the matrix. The approach is illustrated on proteome maps of based on experimental results from liver cells of rats exposed to four peroxisome proliferators. We used the leading eigenvectors of the adjacency matrices as maps descriptors in order to determine the degree of similarity between proteome maps. [ABSTRACT FROM AUTHOR]

Abstract: Let denote a distance-regular graph with classical parameters and , . The condition on implies that is formally self-dual. For we use the adjacency matrix and dual adjacency matrix to obtain an action of the -tetrahedron algebra on the standard module of . We describe four algebra homomorphisms into from the quantum affine algebra ; using these we pull back the above -action to obtain four actions of on the standard module of . [Copyright &y& Elsevier]