26 results on '"Adjacency matrix"'
Search Results
2. On the spectral radius of the generalized adjacency matrix of a digraph
- Author
-
Maryam Baghipur, Hilal A. Ganie, Modjtaba Ghorbani, and Enide Andrade
- Subjects
Numerical Analysis ,Aα-spectral radius ,Algebra and Number Theory ,Maximum out-degree ,Strongly connected digraph ,Adjacency matrix ,Discrete Mathematics and Combinatorics ,Geometry and Topology - Abstract
Let $ D$ be a strongly connected digraph and $\alpha\in [0,1].$ In [J. P. Liu, X. Z. Wu, J. S. Chen and B. L. Liu, The $ A_{\alpha} $ spectral radius characterization of some digraphs, Linear Algebra Appl. 563 (2019) 63--74] the matrix $ A_{\alpha}(D)=\alpha Deg(D)+(1-\alpha)A(D),$ where $ A(D)$ and $Deg(D)$ are the adjacency matrix and the diagonal matrix of the out-degrees of $D,$ respectively, was defined. In this paper it is established some sharp bounds on the $A_{\alpha}(D)$-spectral radius in terms of some parameters such as the out-degrees, the maximum out-degree, the second maximum out-degree, the number of vertices, the number of arcs, the average $2$-outdegrees of the vertices of $D$ and the parameter $ \alpha$ of $A_{\alpha}(D)$. The extremal digraphs attaining these bounds are characterized. It is shown that the bounds obtained improve, in some cases, some of recently given bounds presented in the literature. in publication
- Published
- 2022
3. Universal spectra of the disjoint union of regular graphs
- Author
-
Willem H. Haemers, Mohammad Reza Oboudi, Tilburg University, and Econometrics and Operations Research
- Subjects
Vertex (graph theory) ,Identity matrix ,Of the form ,010103 numerical & computational mathematics ,01 natural sciences ,Combinatorics ,Characteristic polynomial ,Seidel adjacency matrix ,Universal adjacency matrix ,Diagonal matrix ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Adjacency matrix ,0101 mathematics ,Mathematics ,Graph spectrum ,Numerical Analysis ,Algebra and Number Theory ,Seidel matrix ,010102 general mathematics ,Signless Laplacian ,Combinatorics (math.CO) ,Geometry and Topology ,05C50 ,Laplacian ,Laplace operator - Abstract
A universal adjacency matrix of a graph G with adjacency matrix A is any matrix of the form U = α A + β I + γ J + δ D with α ≠ 0 , where I is the identity matrix, J is the all-ones matrix and D is the diagonal matrix with the vertex degrees. In the case that G is the disjoint union of regular graphs, we present an expression for the characteristic polynomials of the various universal adjacency matrices in terms of the characteristic polynomials of the adjacency matrices of the components. As a consequence we obtain a formula for the characteristic polynomial of the Seidel matrix of G, and the signless Laplacian of the complement of G (i.e. the join of regular graphs). The main tool is a simple but useful lemma on equitable matrix partitions. With this note we also want to propagate this technique.
- Published
- 2020
4. Communication in Complex Networks
- Author
-
Lothar Reichel, Jiafeng Jin, Silvia Noschese, and Omar De la Cruz Cabrera
- Subjects
Numerical Analysis ,Theoretical computer science ,Property (programming) ,Applied Mathematics ,Krylov methods ,Numerical Analysis (math.NA) ,Complex network ,Computational Mathematics ,network analysis ,sensitivity analysis ,FOS: Mathematics ,Enhanced Data Rates for GSM Evolution ,Adjacency matrix ,Sensitivity (control systems) ,Matrix exponential ,Mathematics - Numerical Analysis ,Resilience (network) ,Eigenvalues and eigenvectors ,Mathematics - Abstract
One of the properties of interest in the analysis of networks is \emph{global communicability}, i.e., how easy or difficult it is, generally, to reach nodes from other nodes by following edges. Different global communicability measures provide quantitative assessments of this property, emphasizing different aspects of the problem. This paper investigates the sensitivity of global measures of communicability to local changes. In particular, for directed, weighted networks, we study how different global measures of communicability change when the weight of a single edge is changed; or, in the unweighted case, when an edge is added or removed. The measures we study include the \emph{total network communicability}, based on the matrix exponential of the adjacency matrix, and the \emph{Perron network communicability}, defined in terms of the Perron root of the adjacency matrix and the associated left and right eigenvectors. Finding what local changes lead to the largest changes in global communicability has many potential applications, including assessing the resilience of a system to failure or attack, guidance for incremental system improvements, and studying the sensitivity of global communicability measures to errors in the network connection data., 28 pages, 7 figures
- Published
- 2021
5. Relation between signless Laplacian energy, energy of graph and its line graph.
- Author
-
Das, Kinkar Ch. and Mojallal, Seyed Ahmad
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *ABSOLUTE value , *MATHEMATICAL bounds , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
The energy of a simple graph G , E ( G ) , is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted by E ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
6. Spectral characterizations of signed lollipop graphs.
- Author
-
Belardo, Francesco and Petecki, Paweł
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICAL analysis , *BOUNDARY value problems , *NUMERICAL analysis - Abstract
Let Γ = ( G , σ ) be a signed graph, where G is the underlying simple graph and σ : E ( G ) → { + , − } is the sign function on the edges of G . In this paper we consider the spectral characterization problem extended to the adjacency matrix and Laplacian matrix of signed graphs. After giving some basic results, we study the spectral determination of signed lollipop graphs, and we show that any signed lollipop graph is determined by the spectrum of its Laplacian matrix. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
7. The many facets of the Estrada indices of graphs and networks
- Author
-
Ernesto Estrada, Department of Physics, University of Strathclyde [Glasgow], and Estrada, Ernesto
- Subjects
Estrada indices ,Control and Optimization ,Trace (linear algebra) ,Computer science ,05C82 ,Gaussian ,05C80 ,0211 other engineering and technologies ,02 engineering and technology ,[MATH] Mathematics [math] ,15A42 ,01 natural sciences ,matrix functions ,symbols.namesake ,0103 physical sciences ,Adjacency matrix ,[MATH]Mathematics [math] ,010306 general physics ,05C22 ,Discrete mathematics ,15A16 ,Numerical Analysis ,Applied Mathematics ,05C92 ,algebraic graph theory ,eigenvalues of graphs Mathematics Subject Classification 05C12 ,021107 urban & regional planning ,Complex network ,Algebraic graph theory ,Estrada index ,Modeling and Simulation ,Matrix function ,symbols ,Adjacency list ,05C50 ,05C35 - Abstract
The Estrada index of a graph/network is defined as the trace of the adjacency matrix exponential. It has been extended to other graph-theoretic matrices, such as the Laplacian, distance, Seidel adjacency, Harary, etc. Here, we describe many of these extensions, including new ones, such as Gaussian, Mittag–Leffler and Onsager ones. More importantly, we contextualize all of these indices in physico-mathematical frameworks which allow their interpretations and facilitate their extensions and further studies. We also describe several of the bounds and estimations of these indices reported in the literature and analyze many of them computationally for small graphs as well as large complex networks. This article is intended to formalize many of the Estrada indices proposed and studied in the mathematical literature serving as a guide for their further studies.
- Published
- 2021
8. Vertex distinction with subgraph centrality: a proof of Estrada's conjecture and some generalizations
- Author
-
Francesco Ballini, Nikita Deniskin, Ballini, Francesco, and Deniskin, Nikita
- Subjects
FOS: Computer and information sciences ,Subgraph centrality ,Generalization ,Network science ,G.2.2 ,Combinatorics ,Settore MAT/08 - Analisi Numerica ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Adjacency matrix ,Algebraic number ,Eigenvalues and eigenvectors ,Mathematics ,Social and Information Networks (cs.SI) ,Numerical Analysis ,Algebra and Number Theory ,Conjecture ,Lindemann-Weierstrass Theorem ,Computer Science - Social and Information Networks ,Vertex (geometry) ,Walk-regular graph ,05C50, 15A16, 11J72 ,Cospectral vertice ,Combinatorics (math.CO) ,Geometry and Topology ,Centrality - Abstract
Centrality measures are used in network science to identify the most important vertices for transmission of information and dynamics on a graph. One of these measures, introduced by Estrada and collaborators, is the $\beta$-subgraph centrality, which is based on the exponential of the matrix $\beta A$, where $A$ is the adjacency matrix of the graph and $\beta$ is a real parameter ("inverse temperature"). We prove that for algebraic $\beta$, two vertices with equal $\beta$-subgraph centrality are necessarily cospectral. We further show that two such vertices must have the same degree and eigenvector centralities. Our results settle a conjecture of Estrada and a generalization of it due to Kloster, Kr\'al and Sullivan. We also discuss possible extensions of our results., Comment: 8 pages, no figures
- Published
- 2020
9. Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices
- Author
-
Peter Schmelcher, Maxim Pyzh, C. V. Morfonios, and M. Röntgen
- Subjects
Numerical Analysis ,Quantum Physics ,Algebra and Number Theory ,Spectral graph theory ,010102 general mathematics ,FOS: Physical sciences ,010103 numerical & computational mathematics ,01 natural sciences ,Graph ,Vertex (geometry) ,Combinatorics ,Homogeneous space ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Symmetric matrix ,Mathematics - Combinatorics ,Geometry and Topology ,Adjacency matrix ,Combinatorics (math.CO) ,0101 mathematics ,05C50, 15A18, 05C22, 81R40, 81V55 ,Quantum Physics (quant-ph) ,Multiplet ,Eigenvalues and eigenvectors ,Mathematics - Abstract
Originating from spectral graph theory, cospectrality is a powerful generalization of exchange symmetry and can be applied to all real-valued symmetric matrices. Two vertices of an undirected graph with real edge weights are cospectral if and only if the underlying weighted adjacency matrix M fulfills [ M k ] u , u = [ M k ] v , v for all non-negative integer k, and as a result any eigenvector ϕ of M has (or, in the presence of degeneracies, can be chosen to have) definite parity on u and v. We here show that the powers of a matrix with cospectral vertices induce further local relations on its eigenvectors, and also can be used to design cospectrality preserving modifications. To this end, we introduce the concept of walk equivalence of cospectral vertices with respect to walk multiplets which are special vertex subsets of a graph. Walk multiplets allow for systematic and flexible modifications of a graph with a given cospectral pair while preserving this cospectrality. The set of modifications includes the addition and removal of both vertices and edges, such that the underlying topology of the graph can be altered. In particular, we prove that any new vertex connected to a walk multiplet by suitable connection weights becomes a so-called unrestricted substitution point (USP), meaning that any arbitrary graph may be connected to it without breaking cospectrality. Also, suitable interconnections between walk multiplets within a graph are shown to preserve the associated cospectrality. Importantly, we demonstrate that the walk equivalence of cospectral vertices u , v imposes a local structure on every eigenvector ϕ obeying ϕ u = ± ϕ v ≠ 0 (in the case of degeneracies, a specific choice of the eigenvector basis is needed). Our work paves the way for flexibly exploiting hidden structural symmetries in the design of generic complex network-like systems.
- Published
- 2020
10. Functions and eigenvectors of partially known matrices with applications to network analysis
- Author
-
Omar De la Cruz Cabrera, Lothar Reichel, Mohammed Al Mugahwi, and Silvia Noschese
- Subjects
low-rank approximation ,Numerical Analysis ,Rank (linear algebra) ,Applied Mathematics ,Arnoldi process ,cross approximation ,Numerical Analysis (math.NA) ,Topology ,Exponential function ,Computational Mathematics ,Matrix function ,matrix function ,FOS: Mathematics ,Adjacency matrix ,Mathematics - Numerical Analysis ,Centrality ,centrality measure ,column subset selection ,Row ,Eigenvalues and eigenvectors ,Mathematics ,Network analysis - Abstract
Matrix functions play an important role in applied mathematics. In network analysis, in particular, the exponential of the adjacency matrix associated with a network provides valuable information about connectivity, as well as about the relative importance or centrality of nodes. Another popular approach to rank the nodes of a network is to compute the left Perron vector of the adjacency matrix for the network. The present article addresses the problem of evaluating matrix functions, as well as computing an approximation to the left Perron vector, when only some of the columns and/or some of the rows of the adjacency matrix are known. Applications to network analysis are considered, when only some sampled columns and/or rows of the adjacency matrix that defines the network are available. A sampling scheme that takes the connectivity of the network into account is described. Computed examples illustrate the performance of the methods discussed., 19 pages, 8 figures
- Published
- 2020
11. On the Perron root and eigenvectors associated with a subshift of finite type
- Author
-
Nikita Agarwal and Haritha Cheriyath
- Subjects
Numerical Analysis ,Pure mathematics ,Algebra and Number Theory ,Mathematics::Dynamical Systems ,Root (chord) ,Directed graph ,Dynamical Systems (math.DS) ,Expression (computer science) ,Subshift of finite type ,Measure (mathematics) ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Ergodic theory ,Mathematics - Combinatorics ,Geometry and Topology ,Adjacency matrix ,Combinatorics (math.CO) ,Mathematics - Dynamical Systems ,Eigenvalues and eigenvectors ,Computer Science::Formal Languages and Automata Theory ,Mathematics - Abstract
In this paper, we describe the relationship between the Perron root and eigenvectors of an irreducible subshift of finite type with the correlation between the forbidden words in the subshift. In particular, we derive an expression for the Perron eigenvectors of the associated adjacency matrix. As an application, we obtain the Perron eigenvectors for irreducible $(0,1)$ matrices which are adjacency matrices for directed graphs. Moreover, we derive an alternate definition of the Parry measure in ergodic theory on an irreducible subshift of finite type., Python code added
- Published
- 2020
12. On the largest eigenvalue of a mixed graph with partial orientation
- Author
-
Yi Wang, Yi-Zheng Fan, and Bo-Jun Yuan
- Subjects
Numerical Analysis ,Algebra and Number Theory ,010102 general mathematics ,Mixed graph ,010103 numerical & computational mathematics ,01 natural sciences ,Hermitian matrix ,Graph ,Combinatorics ,Matching polynomial ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Geometry and Topology ,Adjacency matrix ,Combinatorics (math.CO) ,0101 mathematics ,05C50 ,Eigenvalues and eigenvectors ,Connectivity ,Mathematics - Abstract
Let G be a connected graph and let T be an acyclic set of edges of G. A partial orientation σ of G with respect to T is an orientation of the edges of G except those edges of T, the resulting graph associated with which is denoted by G T σ . In this paper we prove that there exists a partial orientation σ of G with respect to T such that the largest eigenvalue of the Hermitian adjacency matrix of G T σ is at most the largest absolute value of the roots of the matching polynomial of G.
- Published
- 2020
13. The rank of a complex unit gain graph in terms of the matching number
- Author
-
Fengming Dong, Shengjie He, and Rong-Xia Hao
- Subjects
Numerical Analysis ,Algebra and Number Theory ,Gain graph ,010102 general mathematics ,Mixed graph ,Circuit rank ,010103 numerical & computational mathematics ,01 natural sciences ,Hermitian matrix ,Combinatorics ,Bipartite graph ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Geometry and Topology ,Adjacency matrix ,Combinatorics (math.CO) ,0101 mathematics ,05C50 ,Undirected graph ,Complex number ,Mathematics - Abstract
A complex unit gain graph (or T -gain graph) is a triple Φ = ( G , T , φ ) (or ( G , φ ) for short) consisting of a simple graph G, as the underlying graph of ( G , φ ) , the set of unit complex numbers T = { z ∈ C : | z | = 1 } and a gain function φ : E → → T with the property that φ ( e i , j ) = φ ( e j , i ) − 1 . In this paper, we prove that 2 m ( G ) − 2 c ( G ) ≤ r ( G , φ ) ≤ 2 m ( G ) + c ( G ) , where r ( G , φ ) , m ( G ) and c ( G ) are the rank of the Hermitian adjacency matrix H ( G , φ ) , the matching number and the cyclomatic number of G, respectively. Furthermore, the complex unit gain graphs ( G , T , φ ) with r ( G , φ ) = 2 m ( G ) − 2 c ( G ) and r ( G , φ ) = 2 m ( G ) + c ( G ) are characterized. These results generalize the corresponding known results about undirected graphs, mixed graphs and signed graphs. Moreover, we show that 2 m ( G − V 0 ) ≤ r ( G , φ ) ≤ 2 m ( G ) + S holds for any S ⊂ V ( G ) such that G − S is bipartite and any subset V 0 of V ( G ) such that G − V 0 is acyclic.
- Published
- 2019
14. Laplacian spectral characterization of roses
- Author
-
Changxiang He, Edwin van Dam, Research Group: Operations Research, and Econometrics and Operations Research
- Subjects
Vertex (graph theory) ,Closed walks ,Matchings ,010103 numerical & computational mathematics ,0102 computer and information sciences ,01 natural sciences ,Combinatorics ,Laplacian spectrum ,Sachs' theorem ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Adjacency matrix ,0101 mathematics ,Mathematics ,Discrete mathematics ,Numerical Analysis ,Algebra and Number Theory ,Conjecture ,Graph ,Rose graphs ,010201 computation theory & mathematics ,Geometry and Topology ,Combinatorics (math.CO) ,Laplacian matrix ,05C50 ,Laplace operator - Abstract
A rose graph is a graph consisting of cycles that all meet in one vertex. We show that except for two specific examples, these rose graphs are determined by the Laplacian spectrum, thus proving a conjecture posed by Lui and Huang [F.J. Liu and Q.X. Huang, Laplacian spectral characterization of 3-rose graphs, Linear Algebra Appl. 439 (2013), 2914--2920]. We also show that if two rose graphs have a so-called universal Laplacian matrix with the same spectrum, then they must be isomorphic. In memory of Horst Sachs (1927-2016), we show the specific case of the latter result for the adjacency matrix by using Sachs' theorem and a new result on the number of matchings in the disjoint union of paths.
- Published
- 2018
15. No Threshold graphs are cospectral
- Author
-
João Lazzarin, Oscar F. Marquez, and Fernando Tura
- Subjects
Numerical Analysis ,Threshold graph ,Algebra and Number Theory ,010102 general mathematics ,010103 numerical & computational mathematics ,01 natural sciences ,Pseudorandom binary sequence ,Combinatorics ,FOS: Mathematics ,15A18, 05C50, 05C85 ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Geometry and Topology ,Adjacency matrix ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics ,Characteristic polynomial ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
A threshold graph G on n vertices is defined by binary sequence of length n. In this paper we present an explicit formula for computing the characteristic polynomial of a threshold graph from its binary sequence. Applications include obtaining a formula for the determinant of adjacency matrix of a threshold graph and showing that no two nonisomorphic threshold graphs are cospectral., threshold graph, characteristic polynomial, cospectral graphs
- Published
- 2018
16. On the multiplicity of α as an eigenvalue of Aα(G) of graphs with pendant vertices
- Author
-
Domingos M. Cardoso, Oscar Rojo, and Germain Pastén
- Subjects
0211 other engineering and technologies ,Convex combination of matrices ,010103 numerical & computational mathematics ,02 engineering and technology ,01 natural sciences ,Combinatorics ,Graph eigenvalues ,Diagonal matrix ,Discrete Mathematics and Combinatorics ,Adjacency matrix ,0101 mathematics ,Undirected graph ,Eigenvalues and eigenvectors ,Mathematics ,Numerical Analysis ,Algebra and Number Theory ,021107 urban & regional planning ,Multiplicity (mathematics) ,16. Peace & justice ,Vertex (geometry) ,Signless Laplacian matrix ,Geometry and Topology ,Laplacian matrix - Abstract
Let G be a simple undirected graph. Let 0 ≤ α ≤ 1 . Let A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) where D ( G ) and A ( G ) are the diagonal matrix of the vertex degrees of G and the adjacency matrix of G, respectively. Let p ( G ) > 0 and q ( G ) be the number of pendant vertices and quasi-pendant vertices of G, respectively. Let m G ( α ) be the multiplicity of α as an eigenvalue of A α ( G ) . It is proved that m G ( α ) ≥ p ( G ) − q ( G ) with equality if each internal vertex is a quasi-pendant vertex. If there is at least one internal vertex which is not a quasi-pendant vertex, the equality m G ( α ) = p ( G ) − q ( G ) + m N ( α ) is determined in which m N ( α ) is the multiplicity of α as an eigenvalue of the matrix N. This matrix is obtained from A α ( G ) taking the entries corresponding to the internal vertices which are non quasi-pendant vertices. These results are applied to search for the multiplicity of α as an eigenvalue of A α ( G ) when G is a path, a caterpillar, a circular caterpillar, a generalized Bethe tree or a Bethe tree. For the Bethe tree case, a simple formula for the nullity is given.
- Published
- 2018
17. Structural properties of minimal strong digraphs versus trees
- Author
-
J. García-López, L.M. Pozo-Coronado, and Carlos Marijuán
- Subjects
Dígrafos - Matemáticas discretas ,Árboles - Matemáticas discretas ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Science::Robotics ,Combinatorics ,Characteristic polynomial ,Matrix (mathematics) ,Digraphs - Discrete mathematics ,Discrete Mathematics and Combinatorics ,Adjacency matrix ,Reducible matrices ,Contraction (operator theory) ,Mathematics ,Numerical Analysis ,Algebra and Number Theory ,Conjecture ,Spanning tree ,021107 urban & regional planning ,Matrices reducibles ,Tree (graph theory) ,010201 computation theory & mathematics ,Geometry and Topology ,Polinomios característicos ,Focus (optics) ,Trees - Discrete mathematics - Abstract
Producción Científica, In this article, we focus on structural properties of minimal strong digraphs (MSDs). We carry out a comparative study of properties of MSDs versus (undirected) trees. For some of these properties, we give the matrix version, regarding nearly reducible matrices. We give bounds for the coefficients of the characteristic polynomial corresponding to the adjacency matrix of trees, and we conjecture bounds for MSDs. We also propose two different representations of an MSD in terms of trees (the union of a spanning tree and a directed forest; and a double directed tree whose vertices are given by the contraction of connected Hasse diagrams)., Ministerio de Economía, Industria y Competitividad ( grant MTM2015-65764-C3-1-P)
- Published
- 2018
18. Sedentary quantum walks
- Author
-
Chris Godsil
- Subjects
High probability ,Numerical Analysis ,Strongly regular graph ,Algebra and Number Theory ,Paley graph ,010102 general mathematics ,Complete graph ,010103 numerical & computational mathematics ,Unitary matrix ,01 natural sciences ,Vertex (geometry) ,Combinatorics ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Quantum walk ,Combinatorics (math.CO) ,Geometry and Topology ,Adjacency matrix ,0101 mathematics ,Mathematics - Abstract
Let $X$ be a graph with adjacency matrix $A$. The \textsl{continuous quantum walk} on $X$ is determined by the unitary matrices $U(t)=\exp(itA)$. If $X$ is the complete graph $K_n$ and $a\in V(X)$, then \[1-|U(t)_{a,a}|\le2/n. \] In a sense, this means that a quantum walk on a complete graph stay home with high probability. In this paper we consider quantum walks on cones over an $\ell$-regular graph on $n$ vertices. We prove that if $\ell^2/n\to\infty$ as $n$ increases, than a quantum walk that starts on the apex of the cone will remain on it with probability tending to $1$ as $n$ increases. On the other hand, if $\ell\le2$ we prove that there is a time $t$ such that local uniform mixing occurs, i.e., all vertices are equally likely. We investigate when a quantum walk on strongly regular graph has a high probability of "staying at home", producing large families of examples with the stay-at-home property where the valency is small compared to the number of vertices., 21 pages
- Published
- 2017
19. A $\{-1,0,1\}$- and sparsest basis for the null space of a forest in optimal time
- Author
-
Daniel A. Jaume, Gonzalo Molina, Adrián Pastine, and Martín Darío Safe
- Subjects
FOS: Computer and information sciences ,Numerical Analysis ,Algebra and Number Theory ,Discrete Mathematics (cs.DM) ,Basis (linear algebra) ,010103 numerical & computational mathematics ,0102 computer and information sciences ,05C50, 05C05, 65F50 ,Time optimal ,01 natural sciences ,Combinatorics ,Set (abstract data type) ,Matrix (mathematics) ,010201 computation theory & mathematics ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Geometry and Topology ,Adjacency matrix ,0101 mathematics ,Mathematics ,Computer Science - Discrete Mathematics - Abstract
Given a matrix, the Null Space Problem asks for a basis of its null space having the fewest nonzeros. This problem is known to be NP-complete and even hard to approximate. The null space of a forest is the null space of its adjacency matrix. Sander and Sander (2005) and Akbari et al. (2006), independently, proved that the null space of each forest admits a $\{-1,0,1\}$-basis. We devise an algorithm for determining a sparsest basis of the null space of any given forest which, in addition, is a $\{-1,0,1\}$-basis. Our algorithm is time-optimal in the sense that it takes time at most proportional to the number of nonzeros in any sparsest basis of the null space of the input forest. Moreover, we show that, given a forest $F$ on $n$ vertices, the set of those vertices $x$ for which there is a vector in the null space of $F$ that is nonzero at $x$ and the number of nonzeros in any sparsest basis of the null space of $F$ can be found in $O(n)$ time., 9 pages
- Published
- 2017
20. The Spectra of Arrangement Graphs
- Author
-
Tim Bratten and José O. Araujo
- Subjects
Discrete mathematics ,Numerical Analysis ,Algebra and Number Theory ,010102 general mathematics ,Two-graph ,20C30, 05C50 ,0102 computer and information sciences ,01 natural sciences ,Representation theory ,Combinatorics ,Indifference graph ,010201 computation theory & mathematics ,Symmetric group ,Irreducible representation ,Discrete Mathematics and Combinatorics ,Adjacency list ,Geometry and Topology ,Adjacency matrix ,0101 mathematics ,Eigenvalues and eigenvectors ,Mathematics - Representation Theory ,Mathematics - Abstract
Arrangement graphs were introduced for their connection to computational networks and have since generated considerable interest in the literature. In a pair of recent articles by Chen, Ghorbani and Wong, the eigenvalues for the adjacency matrix of an ( n , k ) -arrangement graph are studied and shown to be integers. In this manuscript, we consider the adjacency matrix directly in terms of the representation theory for the symmetric group. Our point of view yields a simple proof for an explicit formula of the associated spectrum in terms of the characters of irreducible representations evaluated on a transposition. As an application we prove a conjecture raised by Chen, Ghorbani and Wong.
- Published
- 2016
21. On the normalized spectrum of threshold graphs
- Author
-
Anirban Banerjee and Ranjit Mehatari
- Subjects
Threshold graph ,0211 other engineering and technologies ,Binary number ,010103 numerical & computational mathematics ,02 engineering and technology ,01 natural sciences ,Combinatorics ,Spectrum of a matrix ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Adjacency matrix ,0101 mathematics ,Eigenvalues and eigenvectors ,Mathematics ,Discrete mathematics ,Numerical Analysis ,Algebra and Number Theory ,Spectrum (functional analysis) ,021107 urban & regional planning ,Mathematics::Spectral Theory ,Graph energy ,Adjacency list ,Combinatorics (math.CO) ,Geometry and Topology ,05C50 - Abstract
In this article we investigate normalized adjacency eigenvalues (simply normalized eigenvalues) and normalized adjacency energy of connected threshold graphs. A threshold graph can always be represented as a unique binary string. Certain eigenvalues are obtained directly from its binary representation and the rest of the eigenvalues are evaluated from its normalized equitable partition matrix. Finally, we characterize threshold graphs with at most five distinct eigenvalues., 16 pages, 3 figures, final version will appear in Linear Algebra and its Application
- Published
- 2016
22. Complex unit gain bicyclic graphs with rank 2, 3 or 4
- Author
-
Yong Lu, Ligong Wang, and Peng Xiao
- Subjects
Numerical Analysis ,Algebra and Number Theory ,Gain graph ,Bicyclic graphs ,Unicyclic graphs ,010103 numerical & computational mathematics ,0102 computer and information sciences ,01 natural sciences ,Graph ,Circle group ,Combinatorics ,010201 computation theory & mathematics ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Geometry and Topology ,Adjacency matrix ,0101 mathematics ,05C50, 05C22 ,Gain function ,Mathematics - Abstract
A $\mathbb{T}$-gain graph is a triple $\Phi=(G,\mathbb{T},\varphi)$ consisting of a graph $G=(V,E)$, the circle group $\mathbb{T}=\{z\in C: |z|=1\}$ and a gain function $\varphi:\overrightarrow{E}\rightarrow \mathbb{T}$ such that $\varphi(e_{ij})=\varphi(e_{ji})^{-1}=\overline{\varphi(e_{ji})}$. The rank of $\mathbb{T}$-gain graph $\Phi$, denoted by $r(\Phi)$, is the rank of the adjacency matrix of $\Phi$. In 2015, Yu, Qu and Tu [ G. H. Yu, H. Qu, J. H. Tu, Inertia of complex unit gain graphs, Appl. Math. Comput. 265(2015) 619--629 ] obtained some properties of inertia of a $\mathbb{T}$-gain graph. They characterized the $\mathbb{T}$-gain unicyclic graphs with small positive or negative index. Motivated by above, in this paper, we characterize the complex unit gain bicyclic graphs with rank 2, 3 or 4., Comment: 15 pages, 4 figures
- Published
- 2015
23. The coefficients of the reduced Bartholdi zeta function
- Author
-
Seyed Naser Hashemi and Maedeh S. Tahaei
- Subjects
Mathematics::Number Theory ,010103 numerical & computational mathematics ,01 natural sciences ,05C50 05C10 15A15 ,law.invention ,Combinatorics ,Arithmetic zeta function ,symbols.namesake ,law ,Line graph ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Adjacency matrix ,0101 mathematics ,Undirected graph ,Prime zeta function ,Mathematics ,Discrete mathematics ,Numerical Analysis ,Algebra and Number Theory ,010102 general mathematics ,Digraph ,Graph ,Riemann zeta function ,Computer Science::Multiagent Systems ,symbols ,Combinatorics (math.CO) ,Geometry and Topology - Abstract
In this paper, we establish a new zeta function based on the Bartholdi zeta function for an undirected graph G called the reduced Bartholdi zeta function. We study the relation between its coefficients and the structure of the graph, and demonstrate that the coefficients count the star subgraphs in the symmetric digraph D ( G ) . Moreover, we investigate the properties of semi-principle minors extracted from the adjacency matrix of the oriented line graph of G . We also present a general formula for calculating all the coefficients of the reduced Bartholdi zeta function.
- Published
- 2015
24. Successful Pressing Sequences for a Bicolored Graph and Binary Matrices
- Author
-
Joshua Cooper and Jeffrey Davis
- Subjects
Pressing ,Numerical Analysis ,05C50, 15B33, 92D15 ,Algebra and Number Theory ,010102 general mathematics ,Binary number ,0102 computer and information sciences ,01 natural sciences ,Graph ,Combinatorics ,010201 computation theory & mathematics ,Computational phylogenetics ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Logical matrix ,Combinatorics (math.CO) ,Geometry and Topology ,Adjacency matrix ,0101 mathematics ,Mathematics - Abstract
We apply matrix theory over F 2 to understand the nature of so-called “successful pressing sequences” of black-and-white vertex-colored graphs. These sequences arise in computational phylogenetics, where, by a celebrated result of Hannenhalli and Pevzner, the space of sortings-by-reversal of a signed permutation can be described by pressing sequences. In particular, we offer several alternative linear-algebraic and graph-theoretic characterizations of successful pressing sequences, describe the relation between such sequences, and provide bounds on the number of them. We also offer several open problems that arose as a result of the present work.
- Published
- 2015
25. Spectral characterizations of signed lollipop graphs
- Author
-
Paweł Petecki, Francesco Belardo, Belardo, Francesco, and Petecki, Paweł
- Subjects
Discrete mathematics ,Numerical Analysis ,Algebra and Number Theory ,Degree matrix ,Spectral graph theory ,Adjacency matrix, Laplacian matrix, Signed lollipop graph, Spectral determination ,Incidence matrix ,Combinatorics ,Graph energy ,Seidel adjacency matrix ,Discrete Mathematics and Combinatorics ,Geometry and Topology ,Adjacency matrix ,Laplacian matrix ,Signed graph ,Mathematics - Abstract
Let Γ = ( G , σ ) be a signed graph, where G is the underlying simple graph and σ : E ( G ) → { + , − } is the sign function on the edges of G . In this paper we consider the spectral characterization problem extended to the adjacency matrix and Laplacian matrix of signed graphs. After giving some basic results, we study the spectral determination of signed lollipop graphs, and we show that any signed lollipop graph is determined by the spectrum of its Laplacian matrix.
- Published
- 2015
26. Zeta-equivalent digraphs: Simultaneous cospectrality
- Author
-
Peter Herbrich
- Subjects
Mathematics::Number Theory ,010103 numerical & computational mathematics ,01 natural sciences ,Combinatorics ,Mathematics - Spectral Theory ,symbols.namesake ,Matrix (mathematics) ,Transpose ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Adjacency matrix ,0101 mathematics ,Spectral Theory (math.SP) ,Mathematics ,Numerical Analysis ,Algebra and Number Theory ,Markov chain ,010102 general mathematics ,Mathematics::Spectral Theory ,Riemann zeta function ,symbols ,Adjacency list ,Geometry and Topology ,Combinatorics (math.CO) ,Laplacian matrix ,Laplace operator - Abstract
We introduce a zeta function of digraphs that determines, and is determined by, the spectra of all linear combinations of the adjacency matrix, its transpose, the out-degree matrix, and the in-degree matrix. In particular, zeta-equivalence of graphs encompasses simultaneous cospectrality with respect to the adjacency, the Laplacian, the signless Laplacian, and the normalized Laplacian matrix, respectively. In addition, we express zeta-equivalence in terms of Markov chains and in terms of invasions where each edge is replaced by a fixed digraph. We finish with a method for constructing zeta-equivalent digraphs., 15 pages, 1 figure
- Published
- 2014
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.