80 results on '"Adjacency matrix"'
Search Results
2. Dynamic Jacobi graph and trend-aware flow attention convolutional network for traffic forecasting.
- Author
-
Yang, Yongpeng, Yang, Zhenzhen, and Yang, Zhen
- Subjects
- *
TRAFFIC estimation , *FLOWGRAPHS , *INTELLIGENT transportation systems , *VEHICLE detectors , *MATHEMATICAL convolutions - Abstract
Traffic forecasting which has attracted wide attention is the critical issue of the intelligent transportation systems. However, despite its prominent achievements, there are still some challenges due to the complexity of spatial and temporal correlations, which exist in plenty of traffic data. In this paper, a dynamic Jacobi graph and trend-aware flow attention convolutional network (JGFACN) is proposed for traffic forecasting. More specially, a dynamic Jacobi graph convolution network with self-attention is developed for acquiring the spatial correlations among different traffic sensors, in which dynamic adjacency matrix can be derived from the data by dynamic adjacency matrix generator and the spatial correlation among traffic sensors can be minded by Jacobi graph convolution network and self-attention. Secondly, a temporal trend-aware multi-head flow attention mechanism following with a causal dilated convolution is introduced for leveraging the temporal correlation of traffic data effectively. With the help of trend-aware multi-head flow attention, the nonlinear and long-term traffic data can be handled effectively via considering comprehensive information from different representation subspaces and reducing the quadratic complexity. Meanwhile, the participation of a causal dilated convolution can exponentially expand the receptive field. Thirdly, because the nearby spatial-temporal observations are often more correlated, the spatial-temporal order information of traffic data plays an important role in traffic forecasting. Consequently, the rotary temporal position embedding (RTPE) and the learnable spatial positional embedding (LSPE) with graph convolution network are equipped for acquiring the spatial-temporal positional information effectively. Meanwhile, the LSPE with graph convolution network can solve the problem of spatial heterogeneity. At last, the results of extensive experiments on vast amounts of traffic datasets demonstrate the effectiveness of our proposed JGFACN. The graphical abstract of the proposed methods for traffic forecasting • A JGFACN model is proposed for traffic forecasting. • A dynamic JGCN with self-attention is to acquire the spatial correlations. • A temporal trend-aware MFAM is to capture the temporal correlation. • The RTPE and LSPE are equipped for acquiring the positional information. • Extensive experiments demonstrate the performance of our model. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
3. A Poisson multi-Bernoulli mixture filter for tracking multiple resolvable group targets.
- Author
-
Zhou, Yusong, Zhao, Jin, Wu, Sunyong, and Liu, Chang
- Subjects
- *
FILTERS & filtration , *GRAPH theory , *MIXTURES , *FUNCTIONALS , *DYNAMIC models - Abstract
This paper presents a novel Poisson multi-Bernoulli mixture (PMBM) filter for tracking multiple resolvable group targets (MRGT) based on graph theory. Firstly, the number of groups and the relationships between members within the group are modelled by the adjacency matrix. Then, considering that a single dynamic evolution model is insufficient to guarantee stable tracking performance for group targets, the virtual leader-follower model (VLFM) is introduced to predict the evolution trend of unknown and potentially detected targets, respectively. Furthermore, we prove the conjugation of the proposed algorithm with the probability generating functionals (PGF) and give a detailed implementation of the Gaussian mixture (GM). Based on the coexistence scenario of splitting, merging and non-linear motion of the group targets, the simulation results show the effectiveness of the proposed algorithm in comparison with the existing methods. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
4. A divisibility result in combinatorics of generalized braids.
- Author
-
Foissy, Loïc and Fromentin, Jean
- Subjects
- *
BRAID theory , *DIVISIBILITY groups , *COMBINATORICS , *COXETER groups , *MATHEMATICAL decomposition , *HOPF algebras - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
5. On two conjectures of Randić index and the largest signless Laplacian eigenvalue of graphs.
- Author
-
Deng, Hanyuan, Balachandran, S., and Ayyaswamy, S.K.
- Subjects
- *
EIGENVALUES , *GRAPH theory , *LAPLACIAN matrices , *HARMONIC analysis (Mathematics) , *MATHEMATICAL proofs , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
6. Smith and critical groups of polar graphs.
- Author
-
Pantangi, Venkata Raghu Tej and Sin, Peter
- Subjects
- *
LAPLACIAN matrices , *DIVISOR theory , *VECTOR spaces - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
7. Critical groups of van Lint-Schrijver cyclotomic strongly regular graphs.
- Author
-
Pantangi, Venkata Raghu Tej
- Subjects
- *
CAYLEY graphs , *REGULAR graphs , *GRAPH connectivity , *FINITE groups , *ABELIAN groups - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
8. Stability of circulant graphs.
- Author
-
Qin, Yan-Li, Xia, Binzhou, and Zhou, Sanming
- Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
9. Uniquely pressable graphs: Characterization, enumeration, and recognition.
- Author
-
Cooper, Joshua and Whitlatch, Hays
- Subjects
- *
GRAPHIC methods , *GRAPH theory , *ALGORITHMS , *MATHEMATICAL models , *NUMERICAL analysis - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
10. Two remarks on Huang's characterization of the bilinear forms graphs
- Author
-
Hans Cuypers and Discrete Algebra and Geometry
- Subjects
Combinatorics ,Computational Theory and Mathematics ,Discrete Mathematics and Combinatorics ,Geometry and Topology ,Adjacency matrix ,Bilinear form ,Eigenvalues and eigenvectors ,Graph ,Computer Science::Databases ,Theoretical Computer Science ,Mathematics - Abstract
In [4] Huang has given a characterization of the bilinear forms graphsHq (n, d) using the weak 4-vertex conditions and a condition on the parametersn, d andq. We show that the weak 4-vertex condition can be replaced by a condition on the eigenvalues of the adjacency matrix of the graph. Furthermore, we show that the conditions on the parameters can be weakened.
- Published
- 1992
11. Weakly distance-regular digraphs
- Author
-
Comellas, F., Fiol, M.A., Gimbert, J., and Mitjana, M.
- Subjects
- *
DIRECTED graphs , *POLYNOMIALS , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2004
- Full Text
- View/download PDF
12. Eigenvectors of random matrices: A survey.
- Author
-
O'Rourke, Sean, Vu, Van, and Wang, Ke
- Subjects
- *
EIGENVECTORS , *RANDOM matrices , *EIGENANALYSIS , *MATRICES (Mathematics) , *COMBINATORICS - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
13. Accelerating matrix-centric graph processing on GPUs through bit-level optimizations.
- Author
-
Chen, Jou-An, Sung, Hsin-Hsuan, Shen, Xipeng, Tallent, Nathan, Barker, Kevin, and Li, Ang
- Subjects
- *
REINFORCEMENT learning , *SPARSE matrices , *GRAPH algorithms - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
14. Every totally real algebraic integer is a tree eigenvalue.
- Author
-
Salez, Justin
- Subjects
- *
ALGEBRA , *INTEGERS , *TREE graphs , *EIGENVALUES , *GRAPH theory - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
15. Enumeration of spanning trees of graphs with rotational symmetry
- Author
-
Yan, Weigen and Zhang, Fuji
- Subjects
- *
SPANNING trees , *MATHEMATICAL symmetry , *LAPLACIAN operator , *MATRICES (Mathematics) , *TREE graphs , *NUMERICAL analysis - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
16. On the sum of k largest eigenvalues of graphs and symmetric matrices
- Author
-
Mohar, Bojan
- Subjects
- *
SYMMETRIC matrices , *EIGENVALUES , *RADIUS (Geometry) , *GENERALIZATION , *GRAPH theory , *CHARTS, diagrams, etc. - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
17. Gaussianization of the spectra of graphs and networks. Theory and applications.
- Author
-
Alhomaidhi, Alhanouf, Al-Thukair, Fawzi, and Estrada, Ernesto
- Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
18. The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum.
- Author
-
Wissing, Pepijn and van Dam, Edwin R.
- Subjects
- *
TETRAHEDRA , *COLLECTIONS , *EVIDENCE - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
19. The number of ideals of [formula omitted] containing x(x − α)(x − β) with given index.
- Author
-
Hirasaka, Mitsugu and Oh, Semin
- Subjects
- *
GRAPH connectivity , *IDEALS (Algebra) , *NUMBER theory , *REGULAR graphs , *MATRICES (Mathematics) - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
20. On structure of topological entropy for tree-shift of finite type.
- Author
-
Ban, Jung-Chao, Chang, Chih-Hung, Hu, Wen-Guei, and Wu, Yu-Liang
- Subjects
- *
TOPOLOGICAL entropy , *FINITE, The - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
21. Relation between the skew-rank of an oriented graph and the rank of its underlying graph.
- Author
-
Wong, Dein, Ma, Xiaobin, and Tian, Fenglei
- Subjects
- *
DIRECTED graphs , *SKEWNESS (Probability theory) , *SYMMETRIC functions , *DIMENSIONAL analysis , *MATRIX analytic methods - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
22. The algebraic degree of spectra of circulant graphs.
- Author
-
Mönius, Katja
- Subjects
- *
PRIME numbers , *ALGEBRAIC cycles - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
23. MeT: A graph transformer for semantic segmentation of 3D meshes.
- Author
-
Vecchio, Giuseppe, Prezzavento, Luca, Pino, Carmelo, Rundo, Francesco, Palazzo, Simone, and Spampinato, Concetto
- Subjects
TRANSFORMER models ,COMPUTER vision ,VISUAL fields ,EIGENVECTORS - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
24. The Colin de Verdière parameter, excluded minors, and the spectral radius.
- Author
-
Tait, Michael
- Subjects
- *
RADIUS (Geometry) , *MATROIDS , *RAMSEY numbers , *GRAPH theory , *MINORS - Abstract
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]
- Published
- 2019
- Full Text
- View/download PDF
25. Divisible design graphs
- Author
-
Haemers, Willem H., Kharaghani, Hadi, and Meulenberg, Maaike A.
- Subjects
- *
COMBINATORIAL designs & configurations , *GRAPH theory , *DIVISIBILITY groups , *EIGENVALUES , *INFORMATION theory , *SYMMETRIC matrices , *GENERALIZATION - Abstract
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]
- Published
- 2011
- Full Text
- View/download PDF
26. The rank of random regular digraphs of constant degree.
- Author
-
Litvak, Alexander E., Lytova, Anna, Tikhomirov, Konstantin, Tomczak-Jaegermann, Nicole, and Youssef, Pierre
- Subjects
- *
EIGENVECTORS , *PROBABILITY theory , *DIRECTED graphs , *RANDOM matrices , *MATHEMATICAL singularities - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
27. Distance-regular graphs and the -tetrahedron algebra
- Author
-
Ito, Tatsuro and Terwilliger, Paul
- Subjects
- *
ALGEBRA , *GRAPHIC methods , *DISTANCE geometry , *AFFINE algebraic groups - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
28. -polynomial distance-regular graphs with and
- Author
-
Miklavič, Štefko
- Subjects
- *
GRAPH theory , *POLYNOMIALS , *ALGEBRA , *ISOMORPHISM (Mathematics) , *EIGENVECTORS , *MULTIPLICITY (Mathematics) - Abstract
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]
- Published
- 2009
- Full Text
- View/download PDF
29. Monotone maps, sphericity and bounded second eigenvalue
- Author
-
Bilu, Yonatan and Linial, Nati
- Subjects
- *
MATRICES (Mathematics) , *SET theory , *GRAPH theory , *EIGENVALUES - Abstract
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]
- Published
- 2005
- Full Text
- View/download PDF
30. Characterizing imprimitive partition designs of binary Hamming graphs
- Author
-
Canogar, R.
- Subjects
- *
BINARY number system , *MATRICES (Mathematics) , *VERTEX operator algebras , *PARTITIONS (Mathematics) - Abstract
Let
G=(V,E) be a binary Hamming graph (or the 1-skeleton of a hypercube). A partition design ofG with adjacency matrixM=(mij)1≤i,j≤r is defined as a partition{Y1,…,Yr} of the vertex setV such that for everyx∈Yi we have that|{y∈Yj∣(x,y)∈E}|=mij ; this holds for1≤i,j≤r .LetY be a partition design with adjacency matrixM . For everyt≥2 we construct a partition designYt with adjacency matrixtM , and we describe whenYt is the unique partition design with adjacency matrixtM . [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
31. PPA: Principal parcellation analysis for brain connectomes and multiple traits.
- Author
-
Liu, Rongjie, Li, Meng, and Dunson, David B.
- Subjects
- *
WHITE matter (Nerve tissue) , *BRAIN anatomy , *PREDICTION models , *STATISTICS , *LARGE-scale brain networks - Abstract
• 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]
- Published
- 2023
- Full Text
- View/download PDF
32. A note on Markov normalized magnetic eigenmaps.
- Author
-
Cloninger, Alexander
- Subjects
- *
LAPLACIAN matrices , *EMBEDDINGS (Mathematics) , *MATHEMATICAL functions , *MARKOV processes , *GRAPH theory , *EIGENVECTORS - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
33. On bipartite distance-regular graphs with exactly one non-thin [formula omitted]-module with endpoint two.
- Author
-
MacLean, Mark S. and Miklavič, Štefko
- Subjects
- *
BIPARTITE graphs , *ISOMORPHISM (Mathematics) , *INTEGERS , *IRREDUCIBLE polynomials , *INTERSECTION graph theory - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
34. Invertibility of sparse non-Hermitian matrices.
- Author
-
Basak, Anirban and Rudelson, Mark
- Subjects
- *
SPARSE matrices , *HERMITIAN structures , *RANDOM matrices , *RANDOM variables , *MATHEMATICAL singularities , *SPECTRAL theory , *MATRIX norms - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
35. Some extremal properties of the resolvent energy, Estrada and resolvent Estrada indices of graphs.
- Author
-
Zhu, Zhongxun
- Subjects
- *
GRAPH theory , *INDEXES , *RESOLVENTS (Mathematics) , *EIGENVALUES , *GEOMETRIC vertices - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
36. Adjacency matrices of random digraphs: Singularity and anti-concentration.
- Author
-
Litvak, Alexander E., Lytova, Anna, Tikhomirov, Konstantin, Tomczak-Jaegermann, Nicole, and Youssef, Pierre
- Subjects
- *
RANDOM matrices , *DIRECTED graphs , *MATHEMATICAL singularities , *GEOMETRIC vertices , *REGULAR graphs , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
37. A simple arithmetic criterion for graphs being determined by their generalized spectra.
- Author
-
Wang, Wei
- Subjects
- *
GRAPH theory , *ARITHMETIC , *PATHS & cycles in graph theory , *ISOMORPHISM (Mathematics) , *SPECTRAL theory - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
38. On the addition of squares of units modulo n.
- Author
-
Mollahajiaghaei, Mohsen
- Subjects
- *
BRAUER groups , *MATHEMATICAL proofs , *GENERALIZATION , *RESIDUE theorem , *RING theory - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
39. Some spectral and quasi-spectral characterizations of distance-regular graphs.
- Author
-
Abiad, A., van Dam, E.R., and Fiol, M.A.
- Subjects
- *
REGULAR graphs , *INTERSECTION numbers , *INTERSECTION graph theory , *SPECTRAL geometry , *EIGENVALUES - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
40. On extremal bipartite bicyclic graphs.
- Author
-
Huang, Jing, Li, Shuchao, and Zhao, Qin
- Subjects
- *
EXTREMAL problems (Mathematics) , *BIPARTITE graphs , *GRAPH theory , *PATHS & cycles in graph theory , *GEOMETRIC vertices , *GRAPH connectivity - Abstract
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]
- Published
- 2016
- Full Text
- View/download PDF
41. The local eigenvalues of a bipartite distance-regular graph.
- Author
-
MacLean, Mark S.
- Subjects
- *
EIGENVALUES , *BIPARTITE graphs , *REGULAR graphs , *GRAPH theory , *MATHEMATICAL analysis - Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
42. A graph signal processing approach to Fourier-like number-theoretic transforms.
- Author
-
Lima, Juliano B. and de Oliveira Neto, José R.
- Subjects
- *
SIGNAL processing , *HARTLEY transforms , *FOURIER transforms , *IMAGE encryption , *COSINE transforms , *LAPLACIAN matrices - Abstract
In this paper, we employ a graph signal processing approach to redefine Fourier-like number-theoretic transforms, which includes the Fourier number transform itself, the Hartley number transform and specific types of the cosine number transform and the sine number transform. Our strategy basically consists in identifying graphs whose Laplacian or adjacency matrix has an eigenbasis coinciding with the basis employed to define each of the aforementioned transforms. We then demonstrate how to extend this idea to multidimensional cases and provide a general definition, which corresponds to the graph Fourier number transform (GFNT). We develop illustrative examples and perform a preliminary investigation regarding the use of the GFNT in an image encryption scenario. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
43. Multi-dimensional graph fractional Fourier transform and its application to data compression.
- Author
-
Yan, Fang-Jia and Li, Bing-Zhao
- Subjects
- *
DATA compression , *FOURIER transforms , *LAPLACIAN matrices , *SIGNAL processing , *DIGITAL images - Abstract
Many multi-dimensional signals appear in the real world, such as digital images and data that has spatial and temporal dimensions. Designing a transform method to process these multi-dimensional signals in graph fractional domain is a key challenge in graph signal processing. This paper investigates the novel transform for multi-dimensional graph signals defined on Cartesian product graph and studies several related properties. Our work includes: (i) proposing the two-dimensional graph fractional Fourier transforms using two basic graph signal processing methods i.e. based on Laplacian matrix and adjacency matrix; (ii) extending the two-dimensional transforms to multi-dimensional graph fractional Fourier transforms (MGFRFT). MGFRFT provides an additional fractional analysis tool for multi-dimensional graph signal processing; (iii) exploring the advantages of MGFRFT in terms of spectrum, directional characteristics and computational time; (iv) applying the proposed transform to data compression to highlight its utility and effectiveness. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
44. On the spectrum of Wenger graphs.
- Author
-
Cioabă, Sebastian M., Lazebnik, Felix, and Li, Weiqiang
- Subjects
- *
GRAPH theory , *VECTOR spaces , *FINITE fields , *EIGENVALUES , *MATRICES (Mathematics) , *DIMENSIONAL analysis - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
45. Groups all of whose undirected Cayley graphs are integral.
- Author
-
Abdollahi, Alireza and Jazaeri, Mojtaba
- Subjects
- *
UNDIRECTED graphs , *GROUP theory , *CAYLEY graphs , *INTEGRALS , *PATHS & cycles in graph theory , *EIGENVALUES , *ABELIAN groups - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
46. 4-regular oriented graphs with optimum skew energies.
- Author
-
Gong, Shi-Cai, Xu, Guang-Hui, and Zhong, Wen-Bing
- Subjects
- *
DIRECTED graphs , *REGULAR graphs , *SKEWNESS (Probability theory) , *SINGULAR value decomposition , *MATRICES (Mathematics) , *GRAPH theory - Abstract
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]
- Published
- 2014
- Full Text
- View/download PDF
47. Average mixing of continuous quantum walks.
- Author
-
Godsil, Chris
- Subjects
- *
CONTINUOUS functions , *ARITHMETIC mean , *QUANTUM computing , *GRAPH theory , *MATHEMATICAL proofs - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
48. Structural-covariance networks identify topology-based cortical-thickness changes in children with persistent executive function impairments after traumatic brain injury.
- Author
-
King, Daniel J., Seri, Stefano, Catroppa, Cathy, Anderson, Vicki A., and Wood, Amanda G.
- Subjects
- *
BRAIN injuries , *EXECUTIVE function , *MAGNETIC resonance imaging , *COGNITION disorders - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
49. Random Lights Out processes on graphs.
- Author
-
Hughes, Jacob
- Subjects
- *
GRAPH theory , *STOCHASTIC processes , *STOCHASTIC convergence , *DISTRIBUTION (Probability theory) , *ASYMPTOTIC distribution , *RANDOM walks , *EIGENVALUES - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
50. Human attitudes in environmental management: Fuzzy Cognitive Maps and policy option simulations analysis for a coal-mine ecosystem in China
- Author
-
Zhang, Hong, Song, Jie, Su, Chao, and He, Mengying
- Subjects
- *
ECOSYSTEM management , *STAKEHOLDERS , *COAL mining , *COAL mining & the environment , *ATTITUDES toward the environment , *COGNITIVE maps (Psychology) , *SIMULATION methods & models , *CITIZEN participation in environmental policy , *ATTITUDE (Psychology) - Abstract
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]
- Published
- 2013
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.