Search

Perfect state transfer in graphs is a concept arising from quantum physics and quantum computing. Given a graph G with adjacency matrix A G , the transition matrix of G with respect to A G is defined as H A G ( t ) = exp ( − i t A G ) , t ∈ R , i = − 1 . We say that perfect state transfer from vertex u to vertex v occurs in G at time τ if u ≠ v and the modulus of the ( u , v ) -entry of H A G ( τ ) is equal to 1. If the moduli of all diagonal entries of H A G ( τ ) are equal to 1 for some τ , then G is called periodic with period τ . In this paper we give a few sufficient conditions for NEPS of complete graphs to be periodic or exhibit perfect state transfer.

We find a basis for the null space of the adjacency matrix of unicyclic graphs. Based on the support of such a basis, we determine a null decomposition of these graphs. As an application, we obtain closed formulas for the independence and matching numbers of unicyclic graphs that solely rely on the support of the graph.

The net Laplacian matrix of a signed graph G is defined to be N G = D G ± − A G , where D G ± and A G are the diagonal matrix of net-degrees and the adjacency matrix of G , respectively. For a binary vector b , the pair ( N G , b ) is controllable if N G has no eigenvector orthogonal to b ; we also say that G is net Laplacian controllable for b . In this study we consider the net Laplacian controllability of joins of signed graphs. In particular, we establish all controllable pairs ( N G , b ) , where G is a signed threshold graph determined by a ( 0 , 1 , − 1 ) -generating sequence. This result contains all controllable pairs ( L G , b ) , where L G is the Laplacian matrix of a graph G .

A Hamiltonian graph G is said to be hyper-Hamiltonian when G − v is Hamiltonian for any vertex v of G . In this paper, sufficient conditions for a graph to be hyper-Hamiltonian based on different parameters, such as degree and number of edges, are presented. Furthermore, other sufficient conditions for hyper-Hamiltonicity are obtained from spectral parameters, such as the spectral radii of the adjacency matrix, the signless Laplacian matrix and the distance matrix. Results on hyper-Hamiltonicity of a threshold graph through the eigenvalues of its Laplacian matrix are also presented.

Let G be a simple graph with n ( G ) vertices and e ( G ) edges. The elementary cyclic number c ( G ) of G is defined as c ( G ) = e ( G ) − n ( G ) + ω ( G ) , where ω ( G ) is the number of connected components of G . The nullity of G , denoted by η ( G ) , is the multiplicity of the eigenvalue zero of the adjacency matrix of G . A graph is leaf-free if it has no pendent vertices. In Ma et al. (2016) proved that if G is leaf-free and each component of G contains at least two vertices, then η ( G ) ≤ 2 c ( G ) , the equality is attained if and only if G is the union of disjoint cycles, where each cycle has length a multiple of 4. In this paper, we completely characterize all leaf-free graphs with nullity one less than the above upper bound, i.e., η ( G ) = 2 c ( G ) − 1 .

We report our experiments in identifying large bipartite subgraphs of simple connected graphs which are based on the sign pattern of eigenvectors belonging to the extremal eigenvalues of different graph matrices: adjacency, signless Laplacian, Laplacian, and normalized Laplacian matrix. We compare the performance of these methods to a local switching algorithm based on the Erdos bound that each graph contains a bipartite subgraph with at least half of its edges. Experiments with one scale-free and three random graph models, which cover a wide range of real-world networks, show that the methods based on the eigenvectors of the normalized Laplacian and the adjacency matrix yield slightly better, but comparable results to the local switching algorithm. We also formulate two edge bipartivity indices based on the former eigenvectors, and observe that the method of iterative removal of edges with maximum bipartivity index until one obtains a bipartite subgraph, yields comparable results to the local switching algorithm, and significantly better results than an analogous method that employs the edge bipartivity index of Estrada and Gomez-Gardenes., 20 pages, 8 figures

Let G be a simple connected graph with n vertices and m edges. Let W ( G ) = ( G , w ) be the weighted graph corresponding to G . Let λ 1 , λ 2 , … , λ n be the eigenvalues of the adjacency matrix A ( W ( G ) ) of the weighted graph W ( G ) . The energy E ( W ( G ) ) of a weighted graph W ( G ) is defined as the sum of absolute value of the eigenvalues of W ( G ) . In this paper, we obtain upper bounds for the energy E ( W ( G ) ) , in terms of the sum of the squares of weights of the edges, the maximum weight, the maximum degree d 1 , the second maximum degree d 2 and the vertex covering number τ of the underlying graph G . As applications to these upper bounds we obtain some upper bounds for the energy (adjacency energy), the extended graph energy, the Randic energy and the signed energy of the connected graph G . We also obtain some new families of weighted graphs where the energy increases with increase in weights of the edges.

The pineapple graph K p q is obtained by appending q pendant edges to a vertex of a complete graph K p ( p ≥ 3 , q ≥ 1 ). We prove that among connected graphs, the pineapple graph is determined by its adjacency spectrum. Moreover, we determine all disconnected graphs which are cospectral with a pineapple graph. Thus we find for which values of p and q the pineapple graph K p q is determined by its adjacency spectrum. The main tool is a recent classification of all graphs with all but three eigenvalues equal to 0 or − 1 by the third author.

A graph is called a chain graph if it is bipartite and the neighbourhoods of the vertices in each colour class form a chain with respect to inclusion. A threshold graph can be obtained from a chain graph by making adjacent all pairs of vertices in one colour class. Given a graph G , let λ be an eigenvalue (of the adjacency matrix) of G with multiplicity k ≥ 1 . A vertex v of G is a downer, or neutral, or Parter depending whether the multiplicity of λ in G − v is k − 1 , or k , or k + 1 , respectively. We consider vertex types in the above sense in threshold and chain graphs. In particular, we show that chain graphs can have neutral vertices, disproving a conjecture by Alazemi et al.

A nonsingular graph with a singular deck, or NSSD, is a graph with weighted edges and no loops whose adjacency matrix is nonsingular and whose vertex-deleted subgraphs have singular adjacency matrices. When all the weights of the edges of a NSSD are equal to one, we obtain a molecular NSSD, which is an ipso omni-insulator molecular graph. We present necessary and sufficient conditions for a NSSD G to remain a NSSD after increasing the weight of one of its edges by w ∈ R ∖ { 0 } ; this weight change may result in the addition or removal of that edge to or from G . Using this result, we construct molecular NSSDs of a fixed even order. This is accomplished by systematically introducing edges to, or removing edges from, a nonsingular tree.

The graph energy, as a graph invariant, contains very important structural information about the graph, its subgraphs, and ingredient segments. Estrada and Benzi (2017) have shown that the graph energy can be extracted from the weighted sum of the traces of the even powers of its adjacency matrix. Based on this kind of representation, they have reported newer and more precise bounds of the energy as the sum of fragments’ contributions such as C n (cycles of length n), P n (path graph), S n (star graph), D n (diamond graph), F (a subgraph containing a square with a pendant vertex), and H (a subgraph containing two triangles with a shared vertex). In this paper, inspired by the work of Estrada and Benzi, we first introduce a general formula for calculating the contribution of subgraphs to the total energy of the graph. We also compute the boundaries of the contributions of the above subgraphs and some of the subgraphs that appear for the first time in the higher traces of the adjacency matrix of the graph. Further, we calculate the upper bound of the graph energy for cyclic and fullerene graphs with higher accuracy.

Eigenvalues of graph-theoretical matrices often reflect structure properties of networks (graphs) meaningfully. In this paper, we explore inequalities for graph distance measures which are based on topological indices. Some of these indices are based on eigenvalues of graph-theoretical matrices. We here consider the adjacency matrix, the Laplacian matrix and signless Laplacian matrix. Besides proving the inequalities, we discuss the usefulness of these measures and state some conjectures.

We give an O ( n ) time and space algorithm for constructing a diagonal matrix congruent to A + x I , where A is the adjacency matrix of a cograph and x ∈ R . Applications include determining the number of eigenvalues of a cograph’s adjacency matrix that lie in any interval, obtaining a formula for the inertia of a cograph, and exhibiting infinitely many pairs of equienergetic cographs with integer energy.

Let G be a graph of order n . The energy E ( G ) of a simple graph G is the sum of absolute values of the eigenvalues of its adjacency matrix. The Laplacian energy, the signless Laplacian energy and the distance energy of graph G are denoted by L E ( G ) , S L E ( G ) and D E ( G ) , respectively. In this paper we introduce a distance Laplacian energy D L E and distance signless Laplacian energy D S L E of a connected graph. We present Nordhaus–Gaddum type bounds on Laplacian energy L E ( G ) and signless Laplacian energy S L E ( G ) in terms of order n of graph G and characterize graphs for which these bounds are best possible. The complete graph and the star give the smallest distance signless Laplacian energy D S L E among all the graphs and trees of order n , respectively. We give lower bounds on distance Laplacian energy D L E in terms of n for graphs and trees, and characterize the extremal graphs. Also we obtain some relations between D E , D S L E and D L E of graph G . Moreover, we give several open problems in this paper.

Let G σ be an oriented graph with skew adjacency matrix S ( G σ ) . The skew energy E S ( G σ ) of G σ is the sum of the norms of all eigenvalues of S ( G σ ) and the skew rank s r ( G σ ) of G σ is the rank of S ( G σ ) . In this paper, it is proved that E S ( G σ ) ≥ 2 μ ( G ) for an arbitrary connected oriented graph G σ of order n , where μ ( G ) is the matching number of G , and the equality holds if and only if G is a complete bipartite graph K n 2 , n 2 with partition ( X , Y ) of equal size and σ is switching-equivalent to the elementary orientation of G which assigns all edges the same direction from vertices of X to vertices of Y . As an application, we prove that E S ( G σ ) ≥ s r ( G σ ) for an oriented graph G σ and the equality holds if and only if G is the disjoint union of some copies of K 2 and some isolated vertices.

The minimum k -way discrepancy md k ( C ) of a rectangular matrix C of nonnegative entries is the minimum of the maxima of the within- and between-cluster discrepancies that can be obtained by simultaneous k -clusterings (proper partitions) of its rows and columns. In Theorem?2, irrespective of the size of C , we give the following estimate for the k th largest nontrivial singular value of the normalized matrix: s k ? 9 md k ( C ) ( k + 2 - 9 k ln md k ( C ) ) , provided 0 < md k ( C ) < 1 and k < rank ( C ) . This statement is a certain converse of Theorem 7 of Bolla (2014), and the proof uses some lemmas and ideas of Butler (2006), where the k = 1 case is treated. The result naturally extends to the singular values of the normalized adjacency matrix of a weighted undirected or directed graph.

The n -vertex graph G ( = ? ( G ) ) with a non-singular real symmetric adjacency matrix G , having a zero diagonal and singular ( n - 1 ) × ( n - 1 ) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G - 1 represent NSSDs ? ( G ) and ? ( G - 1 ) , the value of the nullity of a one-, two- and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in ? ( G - 1 ) . Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G -nutful graphs. We show that their minimum vertex degree is at least 4.

We present some applications of a new matrix approach for studying the properties of the lift of a voltage digraph, which has arcs weighted by the elements of a group. As a main result, when the involved group is Abelian, we completely determine the spectrum of . As some examples of our technique, we study some basic properties of the Alegre digraph, and completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and the Hoffman-Singleton graph The research of the first two authors have been partially supported by the Agency for Management of University and Research Grants of Catalonia (AGAUR) under project 2017SGR1087. The fifth author acknowledges support from the research grants APVV 0136/12, APVV-15-0220, VEGA 1/0026/16, and VEGA 1/0142/17. The first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922.

The importance of the Pfaffian property of a graph stems from the fact that if the graph is Pfaffian, then the number of its perfect matchings can be computed in polynomial time. A graph G is Pfaffian if there exists an orientation of G , denoted by G ? , such that the determinant of the skew adjacency matrix of G ? equals the square of the number of perfect matchings of G . An undirected graph G = ( V , E ) with n vertices is a circulant graph, denoted by C n ( a 1 , a 2 , ? , a m ) , if there exists a labeling of the vertices of G , v 1 , v 2 , ? , v n , and m integers, a 1 , a 2 , ? , a m , such that the edge set E = { v i v j : i - j ? ? a k ( mod n ) for? 1 ? k ? m } . In this paper, the Pfaffian property of circulant graphs is completely characterized, that is, a simple connected circulant graph C n ( a 1 , a 2 , ? , a m ) of even order is Pfaffian if and only if m = 1 or, m = 2 and a 1 + a 2 is odd.

We unify and generalize several inequalities for the number w"k of walks of length k in graphs, and for the entry sum of matrix powers. First, we present a weighted sandwich theorem for Hermitian matrices which generalizes a matrix theorem by Marcus and Newman and which further generalizes our former unification of inequalities for the number of walks in undirected graphs by Lagarias et al. and by Dress and Gutman. The new inequality uses an arbitrary nonnegative weighting of the indices (vertices) which allows to apply the theorem to index (vertex) subsets (i.e., inequalities considering the number w"k(S,S) of walks of length k that start at a vertex of a given vertex subset S and that end within the same subset). We also deduce a stronger variation of the sandwich theorem for the case of positive-semidefinite Hermitian matrices which generalizes another inequality of Marcus and Newman. Further, we show a similar theorem for nonnegative symmetric matrices which is another unification and generalization of inequalities for walk numbers by Erdos and Simonovits, by Dress and Gutman, and by Ilic and Stevanovic. In the last part, we generalize lower bounds for the spectral radius of adjacency matrices and upper bounds for the energy of graphs.

Let G be a graph with adjacency matrix A, and let H(t)=exp(itA). For an eigenvalue @m of A with multiplicity k, a star set for @m in G is a vertex set X of G such that |X|=k and the induced subgraph G-X does not have @m as an eigenvalue. G is said to have perfect state transfer from the vertex u to the vertex v if there is a time @t such that |H(@t)"u","v|=1. The unitary operator H(t) has important applications in the transfer of quantum information. In this paper, we give an expression of H(t). For a star set X of graph G, perfect state transfer does not occur between any two vertices in X. We also give some results for the existence of perfect state transfer in a graph.

Let G be a simple connected graph with n nodes and let f"@a"""k(A) be a communicability function of the adjacency matrix A, which is expressible by the following Taylor series expansion: @?"k"="0^[email protected]"kA^k. We prove here that if f"@a"""k(A) is positive semidefinite then the function @h"p","q=(f"@a"""k(A)"p"p+f"@a"""k(A)"q"q-2f"@a"""k(A)"p"q)^1^2 is a Euclidean distance between the corresponding nodes of the graph. Then, we prove that if f"@a"""k(A) is positive definite, the communicability distance induces an embedding of the graph into a hyperdimensional sphere (hypersphere) such as the distances between the nodes are given by @h"p","q. In addition we give analytic results for the communicability distances for the nodes in paths, cycles, stars and complete graphs, and we find functions of the adjacency matrix for which the main results obtained here are applicable. Finally, we study the ratio of the surface area to volume of the hyperspheres in which a few real-world networks are embedded. We give clear indications about the usefulness of this embedding in analyzing the efficacy of geometrical embeddings of real-world networks like brain networks, airport transportation networks and the Internet.

We introduce a new type of graph called a Fibonomial graph, denoted G"n. Entries of the adjacency matrix of G"n depend on the well-known Fibonomial coefficients modulo 2. We investigate the connectivity properties, eigenvalues, and energy of G"n. We lastly obtain the sum of the Laplacian eigenvalues of G"n.

Let G = ( V , E ) be a simple graph with vertex set V and edge set E . The rank of G , written as r , is defined to be the rank of its adjacency matrix. Let c denote e - v + ? , where e = | E | , v = | V | and ? means the number of connected components of G , and let m , α , ? ' respectively be the matching number, the independence number, and the chromatic index of G . In this paper, it is proved that ? r - c 2 ? ? m ? ? r + 2 c 2 ? , ? 2 e r + 2 c ? ? ? ' , and v - ? r 2 ? - c ? α ? v - ? r 2 ? . Examples are given to show that all the bounds can be attained.

Let G be a simple connected graph on n vertices and λ 1 , λ 2 , ? , λ n be the eigenvalues of the adjacency matrix of G . The Estrada index of G is defined as E E ( G ) = ? i = 1 n e λ i . Let T n be the class of tricyclic graphs G on n vertices. In this paper, the graphs in T n with the maximal Estrada index is characterized.

Large-scale combinatorial scientific computing problems arising in sparse or otherwise structured matrix computation are often expressed using an appropriate graph model, and sometimes the same problem can be given in more than one graph model with similar asymptotic computational complexity. The relative merits of different graph models for the same problem can then be expressed in terms of factors such as generality of the model or ease of computer implementation. We review contemporary graph formulations for large-scale sparse Jacobian matrix determination problem (JMDP) and suggest the pattern graph as a unifying framework for methods that exploit sparsity by matrix compression: row compression, column compression, or a combination of the two. We argue that with the pattern graph, which is structurally close to the underlying matrix, exploitable sparsity and structures in the matrix are unlikely to be lost in ''translation'' from a matrix problem to a graph problem. From an algorithmic view point the structural correspondence between the matrix and its graph, as we demonstrate in this paper, leads to a better exposition of the compression heuristics and their efficient computer realization. Array-based data structures are suggested as the basic building-blocks for the efficient implementation of relevant graph algorithms. Results from the numerical testing of a subset of implemented algorithms on a suite of test instances drawn from the standard test matrix collection are presented.

The Estrada index of a graph G is defined as EE(G)[email protected]?"i"="1^ne^@l^"^i, where @l"1,@l"2,...,@l"n are the eigenvalues of the adjacency matrix of G. It can be used as an efficient measuring tool in a variety of fields. An edge grafting operation on a graph moves a pendent edge between two pendent paths. In this paper, we give an edge grafting theorem on the Estrada index of graphs. We also give some applications of this theorem.

In this paper we obtain several characterizations of the adjacency matrix of a probe interval graph. In course of this study we describe an easy method of obtaining interval representation of an interval bigraph from its adjacency matrix. Finally, we note that if we add a loop at every probe vertex of a probe interval graph, then the Ferrers dimension of the corresponding symmetric bipartite graph is at most 3.

The distance spectral radius @r(G) of a graph G is the largest eigenvalue of the distance matrix D(G). Recently, many researches proposed the use of @r(G) as a molecular structure descriptor of alkanes. In this paper, we introduce general transformations that decrease distance spectral radius and characterize n-vertex trees with given matching number m which minimize the distance spectral radius. The extremal tree A(n,m) is a spur, obtained from the star graph S"n"-"m"+"1 with n-m+1 vertices by attaching a pendent edge to each of certain m-1 non-central vertices of S"n"-"m"+"1. The resulting trees also minimize the spectral radius of adjacency matrix, Hosoya index, Wiener index and graph energy in the same class of trees. In conclusion, we pose a conjecture for the maximal case based on the computer search among trees on n@?24 vertices. In addition, we found the extremal tree that uniquely maximizes the distance spectral radius among n-vertex trees with perfect matching and fixed maximum degree @D.

We present the spectrum of the (normalized) graph Laplacian as a systematic tool for the investigation of networks, and we describe basic properties of eigenvalues and eigenfunctions. Processes of graph formation like motif joining or duplication leave characteristic traces in the spectrum. This can suggest hypotheses about the evolution of a graph representing biological data. To this data, we analyze several biological networks in terms of rough qualitative data of their spectra., Comment: 12 pages, 3 figures, Discrete Applied Mathematics, to appear

A new operation on graphs is introduced and some of its properties are studied. We call it hierarchical product, because of the strong (connectedness) hierarchy of the vertices in the resulting graphs. In fact, the obtained graphs turn out to be subgraphs of the cartesian product of the corresponding factors. Some well-known properties of the cartesian product, such as reduced mean distance and diameter, simple routing algorithms and some optimal communication protocols are inherited by the hierarchical product. We also address the study of some algebraic properties of the hierarchical product of two or more graphs. In particular, the spectrum of the binary hypertree Tm (which is the hierarchical product of several copies of the complete graph on two vertices) is fully characterized; turning out to be an interesting example of graph with all its eigenvalues distinct. Finally, some natural generalizations of the hierarchic product are proposed.