Search

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

Polygonal meshes have become the standard for discretely approximating 3D shapes, thanks to their efficiency and high flexibility in capturing non-uniform shapes. This non-uniformity, however, leads to irregularity in the mesh structure, making tasks like segmentation of 3D meshes particularly challenging. Semantic segmentation of 3D mesh has been typically addressed through CNN-based approaches, leading to good accuracy. Recently, transformers have gained enough momentum both in NLP and computer vision fields, achieving performance at least on par with CNN models, supporting the long-sought architecture universalism. Following this trend, we propose a transformer-based method for semantic segmentation of 3D mesh motivated by a better modeling of the graph structure of meshes, by means of global attention mechanisms. In order to address the limitations of standard transformer architectures in modeling relative positions of non-sequential data, as in the case of 3D meshes, as well as in capturing the local context, we perform positional encoding by means the Laplacian eigenvectors of the adjacency matrix, replacing the traditional sinusoidal positional encodings, and by introducing clustering-based features into the self-attention and cross-attention operators. Experimental results, carried out on three sets of the Shape COSEG Dataset (Wang et al., 2012), on the human segmentation dataset proposed in Maron et al. (2017) and on the ShapeNet benchmark (Chang et al., 2015), show how the proposed approach yields state-of-the-art performance on semantic segmentation of 3D meshes. • A two-stream architecture exploiting cluster information combined to Laplacian positional encoding to further enforce locality in mesh segmentation. • Interleaved self-attention and cross-attention operations between mesh triangles and clusters. • State-of-the-art performance on multiple benchmarks for 3D mesh segmentation task. [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: 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]

Let d be a (large) integer. Given n ≥ 2 d , let A n be the adjacency matrix of a random directed d -regular graph on n vertices, with the uniform distribution. We show that the rank of A n is at least n − 1 with probability going to one as n grows to infinity. The proof combines the well known method of simple switchings and a recent result of the authors on delocalization of eigenvectors of A n . [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]

Abstract: Let denote a -polynomial distance-regular graph with diameter and intersection numbers , . Let denote the vertex set of and let denote the adjacency matrix of . Fix and let denote the corresponding dual adjacency matrix. Let denote the subalgebra of generated by . We call the Terwilliger algebra of with respect to . We show that up to isomorphism there exists a unique irreducible -module with endpoint . We show that has dimension . We display a basis for which consists of eigenvectors for . We display the action of on this basis. We show that appears in the standard module of with multiplicity , where is the valency of . [Copyright &y& Elsevier]

Abstract: We consider monotone embeddings of a finite metric space into low-dimensional normed space. That is, embeddings that respect the order among the distances in the original space. Our main interest is in embeddings into Euclidean spaces. We observe that any metric on n points can be embedded into , while (in a sense to be made precise later), for almost every n-point metric space, every monotone map must be into a space of dimension (Lemma 3). It becomes natural, then, to seek explicit constructions of metric spaces that cannot be monotonically embedded into spaces of sublinear dimension. To this end, we employ known results on sphericity of graphs, which suggest one example of such a metric space—that is defined by a complete bipartite graph. We prove that an -regular graph of order n, with bounded diameter has sphericity , where is the second largest eigenvalue of the adjacency matrix of the graph, and is constant (Theorem 4). We also show that while random graphs have linear sphericity, there are quasi-random graphs of logarithmic sphericity (Lemma 7). For the above bound to be linear, must be constant. We show that if the second eigenvalue of an -regular graph is bounded by a constant, then the graph is close to being complete bipartite. Namely, its adjacency matrix differs from that of a complete bipartite graph in only entries (Theorem 5). Furthermore, for any , and , there are only finitely many -regular graphs with second eigenvalue at most (Corollary 4). [Copyright &y& Elsevier]

Let G=(V,E) be a binary Hamming graph (or the 1-skeleton of a hypercube). A partition design of G with adjacency matrix M=(mij)1≤i,j≤r is defined as a partition {Y1,…,Yr} of the vertex set V such that for every x∈Yi we have that |{y∈Yj∣(x,y)∈E}|=mij; this holds for 1≤i,j≤r.Let Y be a partition design with adjacency matrix M. For every t≥2 we construct a partition design Yt with adjacency matrix tM, and we describe when Yt is the unique partition design with adjacency matrix tM. [Copyright &y& Elsevier]

• We propose a new approach called principal parcellation analysis (PPA) for predicting human traits using the brain connectome. • PPA uses tractography-based brain connectome representation, clustering fiber endpoints to create a data-driven white matter parcellation. • With vector-valued representation, PPA facilitates easier statistical analysis, improving trait prediction power and model parsimony. • Applications to data from the human connectome project demonstrate the effectiveness of PPA. Our understanding of the structure of the brain and its relationships with human traits is largely determined by how we represent the structural connectome. Standard practice divides the brain into regions of interest (ROIs) and represents the connectome as an adjacency matrix having cells measuring connectivity between pairs of ROIs. Statistical analyses are then heavily driven by the (largely arbitrary) choice of ROIs. In this article, we propose a human trait prediction framework utilizing a tractography-based representation of the brain connectome, which clusters fiber endpoints to define a data-driven white matter parcellation targeted to explain variation among individuals and predict human traits. This leads to Principal Parcellation Analysis (PPA), representing individual brain connectomes by compositional vectors building on a basis system of fiber bundles that captures the connectivity at the population level. PPA eliminates the need to choose atlases and ROIs a priori, and provides a simpler, vector-valued representation that facilitates easier statistical analysis compared to the complex graph structures encountered in classical connectome analyses. We illustrate the proposed approach through applications to data from the Human Connectome Project (HCP) and show that PPA connectomes improve power in predicting human traits over state-of-the-art methods based on classical connectomes, while dramatically improving parsimony and maintaining interpretability. Our PPA package is publicly available on GitHub, and can be implemented routinely for diffusion image data. [ABSTRACT FROM AUTHOR]

We note that building a magnetic Laplacian from the Markov transition matrix, rather than the graph adjacency matrix, yields several benefits for the magnetic eigenmaps algorithm. The two largest benefits are that the embedding becomes more stable as a function of the rotation parameter g , and the principal eigenvector of the magnetic Laplacian now converges to the page rank of the network as a function of diffusion time. We show empirically that this normalization improves the phase and real/imaginary embeddings of the low-frequency eigenvectors of the magnetic Laplacian. [ABSTRACT FROM AUTHOR]

Let Γ denote a bipartite distance-regular graph with diameter D ≥ 4 and valency k ≥ 3 . Let X denote the vertex set of Γ , and let A denote the adjacency matrix of Γ . For x ∈ X and for 0 ≤ i ≤ D , let Γ i ( x ) denote the set of vertices in X that are distance i from vertex x . Define a parameter Δ 2 in terms of the intersection numbers by Δ 2 = ( k − 2 ) ( c 3 − 1 ) − ( c 2 − 1 ) p 22 2 . For x ∈ X let T = T ( x ) denote the subalgebra of Mat X ( C ) generated by A , E 0 ∗ , E 1 ∗ , … , E D ∗ , where for 0 ≤ i ≤ D , E i ∗ represents the projection onto the i th subconstituent of Γ with respect to x . We refer to T as the Terwilliger algebra of Γ with respect to x . An irreducible T -module W is said to be thin whenever dim ( E i ∗ W ) ≤ 1 for 0 ≤ i ≤ D . By the endpoint of an irreducible T -module W we mean min { i | E i ∗ W ≠ 0 } . Fix x ∈ X and assume that Γ has, up to isomorphism, exactly one irreducible T -module W with endpoint 2 , and that W is non-thin with dim ( E 2 ∗ W ) = 1 , dim ( E D − 1 ∗ W ) ≤ 1 and dim ( E i ∗ W ) ≤ 2 for 3 ≤ i ≤ D . We prove that for 2 ≤ i ≤ D , there exist complex scalars α i , β i such that | Γ i − 1 ( x ) ∩ Γ i − 1 ( y ) ∩ Γ 1 ( z ) | = α i + β i | Γ 1 ( x ) ∩ Γ 1 ( y ) ∩ Γ i − 1 ( z ) | for all y ∈ Γ 2 ( x ) and z ∈ Γ i ( x ) ∩ Γ i ( y ) . Furthermore, we prove Δ 2 = 0 and either D = 5 or c 2 ∈ { 1 , 2 } . We show there exist integers 3 ≤ f ≤ ℓ ≤ D − 2 such that dim ( E i ∗ W ) = 2 if and only if f ≤ i ≤ ℓ . [ABSTRACT FROM AUTHOR]

We consider a class of sparse random matrices of the form A n = ( ξ i , j δ i , j ) i , j = 1 n , where { ξ i , j } are i.i.d. centered random variables, and { δ i , j } are i.i.d. Bernoulli random variables taking value 1 with probability p n , and prove a quantitative estimate on the smallest singular value for p n = Ω ( log ⁡ n n ) , under a suitable assumption on the spectral norm of the matrices. This establishes the invertibility of a large class of sparse matrices. For p n = Ω ( n − α ) with some α ∈ ( 0 , 1 ) , we deduce that the condition number of A n is of order n with probability tending to one under the optimal moment assumption on { ξ i , j } . This in particular, extends a conjecture of von Neumann about the condition number to sparse random matrices with heavy-tailed entries. In the case that the random variables { ξ i , j } are i.i.d. sub-Gaussian, we further show that a sparse random matrix is singular with probability at most exp ⁡ ( − c n p n ) whenever p n is above the critical threshold p n = Ω ( log ⁡ n n ) . The results also extend to the case when { ξ i , j } have a non-zero mean. We further find quantitative estimates on the smallest singular value of the adjacency matrix of a directed Erdős–Réyni graph whenever its edge connectivity probability is above the critical threshold Ω ( log ⁡ n n ) . [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph on n vertices and λ 1 , λ 2 , … , λ n be the eigenvalues of the adjacency matrix of G . Estrada and Higham proposed an invariant of a graph G based on Taylor series expansion of spectral moments E E ( G , c ) = ∑ k = 0 ∞ c k M k ( G ) . For c k = 1 n k (resp. 1 k ! , 1 ( n − 1 ) k ), E E ( G , c ) is the Resolvent energy (resp. Estrada index, Resolvent Estrada index) of G . In [18,17] , Gutman et al. conjectured the structure of the extremal members of some classes of graphs by the aid of computer on Resolvent energy and Resolvent Estrada index, respectively. In [1] , L. Allem et al. confirmed the validity of some of these conjectures on Resolvent energy. In this paper, we continue to study these indices based on these conjectures. [ABSTRACT FROM AUTHOR]

Let D n , d be the set of all d -regular directed graphs on n vertices. Let G be a graph chosen uniformly at random from D n , d and M be its adjacency matrix. We show that M is invertible with probability at least 1 − C ln 3 ⁡ d / d for C ≤ d ≤ c n / ln 2 ⁡ n , where c , C are positive absolute constants. To this end, we establish a few properties of d -regular directed graphs. One of them, a Littlewood–Offord type anti-concentration property, is of independent interest. Let J be a subset of vertices of G with | J | ≈ n / d . Let δ i be the indicator of the event that the vertex i is connected to J and define δ = ( δ 1 , δ 2 , . . . , δ n ) ∈ { 0 , 1 } n . Then for every v ∈ { 0 , 1 } n the probability that δ = v is exponentially small. This property holds even if a part of the graph is “frozen.” [ABSTRACT FROM AUTHOR]

A graph G is said to be determined by its generalized spectrum (DGS for short) if, whenever H is a graph such that H and G are cospectral with cospectral complements, then H must be isomorphic to G . It turns out that whether a graph G is DGS is closely related to the arithmetic properties of its walk-matrix. More precisely, let A be the adjacency matrix of a graph G on n vertices, and let W = [ e , A e , A 2 e , ⋯ , A n − 1 e ] ( e is the all-ones vector) be its walk-matrix . In Wang (2013) [16] , the author defined a large family of graphs F n = { G | det ( W ) 2 ⌊ n 2 ⌋ is an odd square-free integer } (which may have positive density among all graphs, as suggested by some numerical experiments) and conjectured every graph in F n is DGS. In this paper, we show that the conjecture is actually true, thereby giving a simple arithmetic condition for determining whether a graph is DGS. [ABSTRACT FROM AUTHOR]

Let Z n be the ring of residue classes modulo n , and let Z n ⁎ be the group of its units. 90 years ago, Brauer obtained a formula for the number of representations of c ∈ Z n as the sum of k units. Recently, Yang and Tang (2015) [6] gave a formula for the number of solutions of the equation x 1 2 + x 2 2 = c with x 1 , x 2 ∈ Z n ⁎ . In this paper, we generalize this result. We find an explicit formula for the number of solutions of the equation x 1 2 + ⋯ + x k 2 = c with x 1 , … , x k ∈ Z n ⁎ . [ABSTRACT FROM AUTHOR]

In this paper we consider the concept of preintersection numbers of a graph. These numbers are determined by the spectrum of the adjacency matrix of the graph, and generalize the intersection numbers of a distance-regular graph. By using the preintersection numbers we give some new spectral and quasi-spectral characterizations of distance-regularity, in particular for graphs with large girth or large odd-girth. [ABSTRACT FROM AUTHOR]

Let B n + be the set of all connected bipartite bicyclic graphs with n vertices. The Estrada index of a graph G is defined as EE ( G ) = ∑ i = 1 n e λ i , where λ 1 , λ 2 , … , λ n are the eigenvalues of the adjacency matrix of G , and the Kirchhoff index of a graph G is defined as Kf ( G ) = ∑ i < j r i j , where r i j is the resistance distance between vertices v i and v j in G . The complement of G is denoted by G ‾ . In this paper, sharp upper bound on EE ( G ) (resp. Kf ( G ‾ ) ) of graph G in B n + is established. The corresponding extremal graphs are determined, respectively. Furthermore, by means of some newly created inequalities, the graph G in B n + with the second maximal EE ( G ) (resp. Kf ( G ‾ ) ) is identified as well. It is interesting to see that the first two bicyclic graphs in B n + according to these two orderings are mainly coincident. [ABSTRACT FROM AUTHOR]

We consider a bipartite distance-regular graph Γ with vertex set X , diameter D ≥ 4 , and valency k ≥ 3 . For 0 ≤ i ≤ D , let Γ i ( x ) denote the set of vertices in X that are distance i from vertex x . We assume there exist scalars r , s , t ∈ R , not all zero, such that r | Γ 1 ( x ) ∩ Γ 1 ( y ) ∩ Γ 2 ( z ) | + s | Γ 2 ( x ) ∩ Γ 2 ( y ) ∩ Γ 1 ( z ) | + t = 0 for all x , y , z ∈ X with path-length distances ∂ ( x , y ) = 2 , ∂ ( x , z ) = 3 , ∂ ( y , z ) = 3 . Fix x ∈ X , and let Γ 2 2 denote the graph with vertex set X ̃ = { y ∈ X ∣ ∂ ( x , y ) = 2 } and edge set R ̃ = { y z ∣ y , z ∈ X ̃ , ∂ ( y , z ) = 2 } . We show that the adjacency matrix of the local graph Γ 2 2 has at most four distinct eigenvalues. We are motivated by the fact that our assumption above holds if Γ is Q -polynomial. [ABSTRACT FROM AUTHOR]

Abstract: Let , where p is a prime and is an integer. For , let P and L be two copies of the -dimensional vector spaces over the finite field . Consider the bipartite graph with partite sets P and L defined as follows: a point is adjacent to a line if and only if the following m equalities hold: for . We call the graphs Wenger graphs. In this paper, we determine all distinct eigenvalues of the adjacency matrix of and their multiplicities. We also survey results on Wenger graphs. [Copyright &y& Elsevier]

Abstract: Let be a finite group, be a set such that if , then , where denotes the identity element of . The undirected Cayley graph of over the set is the graph whose vertex set is and two vertices and are adjacent whenever . The adjacency spectrum of a graph is the multiset of all eigenvalues of the adjacency matrix of the graph. A graph is called integral whenever all adjacency spectrum elements are integers. Following Klotz and Sander, we call a group Cayley integral whenever all undirected Cayley graphs over are integral. Finite abelian Cayley integral groups are classified by Klotz and Sander as finite abelian groups of exponent dividing or . Klotz and Sander have proposed the determination of all non-abelian Cayley integral groups. In this paper we complete the classification of finite Cayley integral groups by proving that finite non-abelian Cayley integral groups are the symmetric group of degree , and for some integer , where is the quaternion group of order . [Copyright &y& Elsevier]

Abstract: The skew energy of an oriented graph , denoted by , is defined as the sum of the singular values of its skew adjacency matrix . The connected -regular oriented graph on vertices having skew energy is called the optimum skew energy -regular oriented graph. In this paper, we determine the 4-regular graphs such that each of them has an orientation satisfying which is an optimum skew energy oriented graph. In addition, as by-product we obtain a method to construct optimum skew energy -regular oriented graphs with large order. [Copyright &y& Elsevier]

Abstract: If X is a graph with adjacency matrix A, then we define to be the operator . The Schur (or entrywise) product is a doubly stochastic matrix and because of work related to quantum computing, we are concerned with the average mixing matrix , defined by In this paper we establish some of the basic properties of this matrix, showing that it is positive semidefinite and that its entries are always rational. We see that in a number of cases its form is surprisingly simple. Thus for the path on n vertices it is equal to where T is the permutation matrix that swaps j and for each j. If X is an odd cycle or, more generally, if X is one of the graphs in a pseudocyclic association scheme on n vertices with d classes, each of valency m, then its average mixing matrix is (One reason this is interesting is that a graph in a pseudocyclic scheme may have trivial automorphism group, and then the mixing matrix is more symmetric than the graph itself.) [Copyright &y& Elsevier]

Paediatric traumatic brain injury (pTBI) results in inconsistent changes to regional morphometry of the brain across studies. Structural-covariance networks represent the degree to which the morphology (typically cortical-thickness) of cortical-regions co-varies with other regions, driven by both biological and developmental factors. Understanding how heterogeneous regional changes may influence wider cortical network organization may more appropriately capture prognostic information in terms of long term outcome following a pTBI. The current study aimed to investigate the relationships between cortical organisation as measured by structural-covariance, and long-term cognitive impairment following pTBI. T1-weighted magnetic resonance imaging (MRI) from n = 83 pTBI patients and 33 typically developing controls underwent 3D-tissue segmentation using Freesurfer to estimate cortical-thickness across 68 cortical ROIs. Structural-covariance between regions was estimated using Pearson's correlations between cortical-thickness measures across 68 regions-of-interest (ROIs), generating a group-level 68 × 68 adjacency matrix for patients and controls. We grouped a subset of patients who underwent executive function testing at 2-years post-injury using a neuropsychological impairment (NPI) rule, defining impaired- and non-impaired subgroups. Despite finding no significant reductions in regional cortical-thickness between the control and pTBI groups, we found specific reductions in graph-level strength of the structural covariance graph only between controls and the pTBI group with executive function (EF) impairment. Node-level differences in strength for this group were primarily found in frontal regions. We also investigated whether the top n nodes in terms of effect-size of cortical-thickness reductions were nodes that had significantly greater strength in the typically developing brain than n randomly selected regions. We found that acute cortical-thickness reductions post-pTBI are loaded onto regions typically high in structural covariance. This association was found in those patients with persistent EF impairment at 2-years post-injury, but not in those for whom these abilities were spared. This study posits that the topography of post-injury cortical-thickness reductions in regions that are central to the typical structural-covariance topology of the brain, can explain which patients have poor EF at follow-up. [ABSTRACT FROM AUTHOR]

Abstract: Lights Out is a single player game on graph G. The game starts with a coloring of the vertices of G with two colors, 0 and 1. At each step, one vertex is toggled which switches the color of that vertex and all of its neighbors. The game is won when all vertices have color 0. We consider the stochastic process arising from toggling a sequence of random vertices. We demonstrate how the process can be viewed as a random walk on an associated state graph. We then find the eigenvalues of the state graph, and use them to bound the rate of convergence and hitting times. We show that the distribution of this random process converges to the uniform distribution and show that the χ-squared distance after t steps is less than for all , where is the rank of the adjacency matrix of the state graph plus the identity matrix taken over . We also provide bounds on the average number of steps until this random process reaches the all 0 coloring that are asymptotically tight for many families of graphs. [Copyright &y& Elsevier]

Ecosystem management is a complex process, and every stakeholder's cognition plays a crucial role in it. In order to manage the ecosystem better, it is significant for the coal-mining environmental managers to choose appropriate measures, in accord with the stakeholders'' interests. Hence, the purpose of this study is to assess knowledge of and attitudes towards coal-mine ecosystems among stakeholders and then simulate policy options in a typical coal-mine region in China. The Fuzzy Cognitive Mapping (FCM) method was used to develop a participatory ecosystem management model in research area. Combining the initial state of variables and the adjacency matrix getting from FCM, Artificial Neural Network (ANN) was used to conduct simulations. The results found that among stakeholder groups'' FCM model, ‘air pollution’ and ‘water pollution’ are the most frequently mentioned variables, while ‘health effects’ and ‘expansion of related industries’ are the core variables. However, different stakeholders expressed diverse perceptions on coal-mine ecosystem management. Mine workers paid more attention to occupational safety and their health impacts inducted by air and water pollution during coal-mine process. Local residents were concerned with local economic development and welfare facilities improvement; they also concerned their health impacts raised by coal-mine related problems such as air and water pollution, traffic and noises. Managers emphasized economic interests and environmental projects with immediate environmental effects other than long-term ecosystem improvement. Engineers mentioned more variables than other groups; they believed that air pollution, water pollution, soil erosion and biodiversity loss were important. Scenario analysis for policy simulation based on ANN suggested that the local governments and enterprises should place an emphasis on protecting farmland, increasing vegetation coverage, reducing solid contamination and improving energy efficiency to decrease air pollution. In addition, they should start from decreasing air pollution, protecting water environment, increasing vegetation coverage and paying attention to people's safety to improve health. National policy, public administration and enterprise countermeasures have positive influence to ecosystem management. The findings of this study could provide valuable information to researchers and administrators about stakeholders'' knowledge of and attitudes towards coal-mine ecosystem management. These, in turn, could be incorporated into the development of protective measures for a coal-mine ecosystem in China. [Copyright &y& Elsevier]