Search

Accurate and real-time traffic forecasting is of great significance for urban traffic planning, traffic control, and traffic management. However, the time-varying dynamic spatial relations and the complicated spatial–temporal dependencies are still open problems to be considered in traffic forecasting. To address these issues, we propose a graph convolutional recurrent network for traffic forecasting with a dynamic adjacency matrix within an encoder–decoder framework, named DAGCRN. The DAGCRN consists of a spatial relation extraction module (SREM), an adjacency matrix update module (AMUM), a dynamic graph convolutional recurrent module (DGCRM), and a global temporal attention module (GTAM). Specifically, SREM and AMUM are proposed to capture nodes' mutual relations at each time step and to model the evolution of the dynamic adjacency matrix, respectively. DGCRM captures the spatial–temporal dependencies of traffic data based on dynamic graph convolution and gated recurrent unit. GTAM is designed to extract the long-range temporal dependencies between future time steps and historical time steps. Extensive experiments on two real-world traffic speed datasets demonstrate that the proposed DAGCRN outperforms a number of representative baselines consistently. [ABSTRACT FROM AUTHOR]

A finite sequence d: d 1 , d 2 , d 3 ,. .. ., d n of nonnegative integers is said to be graphical if there exists some finite simple graph G, having vertex set V={ v 1 , v 2 , v 3 , …., v n } such that each v i has degree d i (1 ≤ i ≤ n). In this paper we have proposed an algorithm that takes a non-increasing sequence as input and determines whether the given degree sequence is graphic by constructing the adjacency matrix from the given sequence in non-increasing order and checking whether it can be orthogonally diagonalizable. The matrix generated in this process can be used to determine a lot of interesting information regarding the characteristic of the graph directly from the given degree sequence. [ABSTRACT FROM AUTHOR]

A mixed graph is a graph with edges and arcs, which can be considered as a hybrid of an undirected graph and a directed graph. In this paper we define the mixed adjacency matrix and the mixed energy of a mixed graph. The mixed adjacency matrix generalizes both the adjacency matrix of an undirected graph and the skew-adjacency matrix of a digraph. Then we compute the characteristic polynomial of the mixed adjacency matrix of a mixed graph and deduce some basic results from it. Furthermore, we give bounds to the mixed energy of a general mixed graph, and we compute the mixed energy of some special mixed graphs. At the end of the paper, we introduce mixed unitary Cayley graphs and compute their spectra. [ABSTRACT FROM AUTHOR]

Abstract: Similarity measurement of XML documents is crucial to meet various needs of approximate searches and document classifications in XML-oriented applications. Some methods have been proposed for this purpose. Nevertheless, few methods can be elegantly exploited to depict structure and semantic information and hence to effectively measure the similarity of XML documents. In this paper, we present a new method of computing the structure and semantic similarity of XML documents based on extended adjacency matrix(EAM). Different from a general adjacency matrix, in an EAM, the structure information of not only the adjacent layers but also the ancestor-descendant layers can be stored. For measuring the similarity of two XML documents, the proposed method firstly stores the structure and semantic information in two extended adjacency matrices(M 1 , M 2 ). Then it computes similarity of the two documents through cos(M 1 , M 2 ) Experimental results on bench-mark data show that the method holds high efficiency and accuracy. [Copyright &y& Elsevier]

Abstract: Back/forward sweep flow algorithm is a optimal way used to calculate loss for distribution economic operation. Combined the unique radial characteristic of distribution network, this paper propose a back/forward sweep distribution load flow algorithm based on network layer structure. Analyze the layer structure of the network nodes through the adjacency matrix multiplication and subtraction and the row vector corresponding to root node in created matrix,based on which get a layer matrix M* . M* as a selection operator simplifies the back/forward load calculation formulas. Reduce the computational complexity and increase the calculation efficiency. The result of IEEE33 nodes indicates that the algorithm proposed is valid. [Copyright &y& Elsevier]

An oriented hypergraph is an oriented incidence structure that generalizes and unifies graph and hypergraph theoretic results by examining its locally signed graphic substructure. In this paper we obtain a combinatorial characterization of the coefficients of the characteristic polynomials of oriented hypergraphic Laplacian and adjacency matrices via a signed hypergraphic generalization of basic figures of graphs. Additionally, we provide bounds on the determinant and permanent of the Laplacian matrix, characterize the oriented hypergraphs in which the upper bound is sharp, and demonstrate that the lower bound is never achieved. [ABSTRACT FROM AUTHOR]

Abstract: A threshold graph on n vertices is coded by a binary string of length . We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases. [Copyright &y& Elsevier]

The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G , a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F , of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F , we take algebraic route. More formally, given a fixed positive integer r , we define F r as the family of graphs where for each G ∈ F r , the rank of the adjacency matrix of G is at most r . Using the family F r we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r - Rank Vertex Deletion , r - Rank Edge Deletion and r - Rank Editing . These problems generalize the classical Vertex Cover problem and a variant of the d - Cluster Editing problem. We first show that all the three problems are NP-Complete . Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2 O ( k log ⁡ r ) n O ( 1 ) for r - Rank Vertex Deletion , and an algorithm for r - Rank Edge Deletion and r - Rank Editing running in time 2 O ( f ( r ) k log ⁡ k ) n O ( 1 ) . We complement our FPT result by designing polynomial kernels for these problems. [ABSTRACT FROM AUTHOR]

Abstract: Let be an unweighted rooted tree of k levels such that in each level the vertices have equal degree. Let d k−j+1 denotes the degree of the vertices in the level j. We find the eigenvalues of the adjacency matrix and of the Laplacian matrix of . They are the eigenvalues of principal submatrices of two nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for both matrices are , and , while the diagonal entries are zeros, in the case of the adjacency matrix, and d j , 1⩽ j ⩽k, in the case of the Laplacian matrix. Moreover, we give some results concerning to the multiplicity of the above mentioned eigenvalues. [Copyright &y& Elsevier]

Abstract: Let be the smallest number such that the adjacency matrix of any undirected graph with vertices or more has at least nonpositive eigenvalues. We show that is well-defined and prove that the values of for are 1, 3, 6, 10, 16 respectively. In addition, we prove that for all , , in which is the Ramsey number for and , and is the triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the largest eigenvalue is bounded from below the largest degree, which generalizes some prior results. [Copyright &y& Elsevier]

Abstract: Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value of y. We call such graphs -cospectral. It follows that is a rational number, and we prove existence of a pair of -cospectral graphs for every rational . In addition, we generate by computer all -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of -cospectral graphs for all rational , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of , and by computer we find all such pairs of -cospectral graphs on at most eleven vertices. [Copyright &y& Elsevier]

Let G be a graph. An edge orientation of G is called smooth if the in-degree and the out-degree of every vertex differ by at most one. In this paper, we show that if G is a 2-edge-connected non-bipartite graph with δ ( G ) ≥ 3 , then G has a smooth primitive orientation. Among other results, using the spectral radius of digraphs, we show that if D 1 is a primitive regular orientation and D 2 is a non-regular orientation of a given graph, then for sufficiently large t , the number of closed walks of length t in D 1 is more than the number of closed walks of length t in D 2 . [ABSTRACT FROM AUTHOR]

Abstract: Let G =(V, E) be a simple graph and {λ 1(G),…, λ n (G)} be its adjacency spectrum. It is easy to see that if an edge is added between two isolated vertices, then one zero eigenvalue increases by 1, and another zero eigenvalue decreases by 1. Let G + be a connected graph obtained from G by adding an edge e ∉ E(G). In this paper, it will be proved that the spectrum of G + is different from that of G only in two places with one eigenvalue increases by m and another eigenvalue decreases by m, where m >0 is a rational number, if and only if G is an empty graph with order 2. It will also be proved that one cannot construct a new adjacency integral connected graph with order n ⩾3 from a known one by adding an edge. [Copyright &y& Elsevier]

Abstract: We show that the adjacency matrix M of the line digraph of a d-regular digraph D on n vertices can be written as , where the matrix A is the Kronecker product of the all-ones matrix of dimension d with the identity matrix of dimension n and the matrix B is the direct sum of the adjacency matrices of the factors in a dicycle factorization of D. [Copyright &y& Elsevier]

Abstract: We define cut-and-paste, a construction which, given a quadriculated disk obtains a disjoint union of quadriculated disks of smaller total area. We provide two examples of the use of this procedure as a recursive step. Tilings of a disk receive a parity: we construct a perfect or near-perfect matching of tilings of opposite parities. Let be the black-to-white adjacency matrix: we factor , where and are lower and upper triangular matrices, is obtained from a larger identity matrix by removing rows and columns and all entries of , and are equal to , or . [Copyright &y& Elsevier]

Abstract: Oscillations are a common type of plant-wide disturbances whose effects propagate to many units and thus may impact overall process performance. It is important to detect and diagnose such oscillations early in order to rectify the situation. Many frequency domain tools such as the power spectrum and spectrum envelope methods are capable of detecting the oscillation frequency. However, few methods are available for locating the root cause which is the main objective of oscillation diagnosis. This paper proposes a new method to diagnose the root cause of plant-wide oscillations using the adjacency matrix. A novel feature of the new method is that it utilizes the information in the process flowsheet. The method is not data-based and it can be carried out without using any data. However, this method complements the data based methods very well and it is best used in combination with other data-based methods to provide powerful diagnosis of plant-wide oscillations. This paper is the subject of a newly proposed complete procedure for detection and diagnosis of plant-wide oscillation. Two industrial case studies are also presented to demonstrate the applicability of the proposed procedure. [Copyright &y& Elsevier]

Let J(λ;n1,…,nk) be the set of matrices A such that λ is an eigenvalue of A and n1⩽⋯⩽nk are the sizes of the Jordan blocks associated with λ. For a given index v of A, denote by A−v the principal submatrix of co-order one obtained from A by deleting the vth row and column. In the present paper, all possible changes of the part of the Jordan form corresponding to λ under the transition from A to A−v are determined for matrices A∈J(λ;n1,…,nk) such that for the eigenvalue λ of both A and A⊤, there exists a Jordan chain of the largest length nk whose eigenvector has nonzero vth entry. In particular, it is shown that for almost every matrix A∈J(λ;n1,…,nk), n1,…,nk−1 are the sizes of Jordan blocks for λ considered as an eigenvalue of A−v. Moreover, it is also proved that if A is the adjacency matrix of a vertex-transitive digraph and k⩾2, then the change n1,…,nk→n1,…,nk−2,2nk−1−1 holds for the eigenvalue λ under the transition from A to A−v. In the case of k=1, λ is a simple eigenvalue of A and does not belong to the spectrum of A−v. [Copyright &y& Elsevier]

Power forecast for each renewable power plant (RPP) in the renewable energy clusters is essential. Though existing graph neural networks (GNN)-based models achieve satisfactory prediction performance by capturing dependencies among distinct RPPs, the static graph structure employed in these models ignores crucial lead-lag correlations among RPPs, resulting from the time difference of the air flow at spatially dispersed RPPs. To address this problem, this paper proposes a novel dynamic graph structure using multiple temporal granularity groups (TGGs) to characterize the lead-lag correlations among RPPs. A granular-based GNN called GGNet is designed to generate an optimal adjacency matrix for the proposed graph structure. Specifically, a two-dimensional convolutional neural network (2D-CNN) is used to quantify the uncertain lead-lag correlations among RPPs; secondly, a gate mechanism is used to calculate a dynamic adjacency matrix; Finally, a graph attention network (GAT) is used to aggregate the information on RPPs based on the well-learned adjacency matrix. Case studies conducted using real-world datasets, with wind power plants and photovoltaic power plants, show our method outperforms state-of-the-art (SoTA) ones with better performance. Compared with the SoTA models, the RMSE N and MAE N of wind power plants for 1–4 h forecast steps decreased on average by 22.925% and 13.18%, respectively; the RMSE N and MAE N of photovoltaic power plants for 1–4 h forecast steps decreased on average by 48.95% and 18.75%, respectively. The results show that the proposed framework can generate improved performance with accuracy and robustness. • Dynamic graph structure can clarify lead-lag power correlation of renewable plants. • A novel model can quantity the lead-lag power correlation of renewable plants. • Memory cell can make the adjacency matrix among renewable plants learnable. • A graph attention network can improve power forecast accuracy of renewable plants. [ABSTRACT FROM AUTHOR]

• Informed fundamental diagram knowledge into a newly proposed data-driven model. • Applied and evaluated the proposed PI-SGTGCN model through real-world dataset. • Investigated the physical interpretation of the dynamic graph adjacency matrix. Accurate and fine-grained traffic state prediction has always been an important research field. For long-term traffic flow prediction, the high-dimensional and coupled traffic feature evolution patterns are deeply recessive, posing challenges in effectively characterizing and modeling them. This paper proposed a novel spatial–temporal graph convolution network model with traffic Fundamental Diagram (FD) information informed. The model decouples the high-dimensional spatiotemporal relationships in the transportation network and fully leverages the physical evolution laws of traffic states. First, the Graph Convolutional Network (GCN) with a spatial attention mechanism was proposed to capture spatial relations of the road network. The mechanism can better represent the spatial dynamics of the graph adjacency matrix in GCN. Second, this study injected prior physical knowledge into the graph adjacency matrix. This process was achieved by embedding characteristics of FDs from historical traffic data on the diagonal of the matrix, by which the propagation pattern of traffic states in road network could be considered. Third, to further catch the time dependence of the road network, the Gated Recurrent Unit (GRU) structure and the Transformer encoding structure were employed to locally and globally reform traffic state time sequences. Finally, experiments on a revised traffic dataset demonstrated that the proposed method consistently outperforms other baselines regarding Mean Absolute Error and Root Mean Square Error across all cases. Moreover, it achieved the optimal Mean Absolute Percentage Error in the 30- and 60-minute prediction tasks. This study shows a novel solution to inform traffic physical laws into data-driven state prediction models, and the reliability of the proposed method in long-term prediction offers valuable support for improving traffic management and alleviating traffic congestion. [ABSTRACT FROM AUTHOR]

Ergonomic risk assessment (ERA) is commonly used to identify and analyze postures that are detrimental to the health of workers in industrial workplaces, which is vital to prevent work-related musculoskeletal disorders (WMSDs). Among the automatic approaches, algorithms based on graph convolutional networks (GCNs) have shown promising results in ERA using skeleton sequence as input. However, previous GCN-based methods still have certain limitations. First, the separated modeling of spatial and temporal information and the manually pre-defined topology of graph may restrict the representation diversity of the networks. Additionally, RNN-based temporal modeling often incurs high computational costs and fails to capture long-range temporal dependencies, thereby reducing flexibility in describing long videos. To overcome these challenges, in this study, we propose an attention-based adaptive spatial–temporal graph convolutional network (AAST-GCN), aiming to achieve effective and efficient action representation for ERA in long video. First, we employ an alternate modeling strategy to effectively capture the spatial–temporal information, and propose an improved adaptive adjacency matrix scheme to learn various coordination and relations of body-joints, thus enhancing the flexibility to model diverse postures. Furthermore, we introduce an efficient multi-scale temporal convolutional network as a replacement for RNN-based algorithms, enabling the network to extract various granularities of temporal features. Moreover, to make the network focuses on more valuable information, we employ a spatial–temporal interaction attention (STIA) module. Finally, the aforementioned modules are aggregated within a multi-task learning framework, with the action segmentation serving as the auxiliary task to further improve the accuracy of ERA. We conducted the ergonomic risk assessment on the UW-IOM and TUM Kitchen datasets using our network. Extensive experiments conducted on the most popular datasets UW-IOM and TUM Kitchen demonstrated that our proposed AAST-GCN outperforms other GCN-based methods. Ablation studies and visualization also prove the effectiveness of the individual sub-modules. [ABSTRACT FROM AUTHOR]

In this paper we introduce a new class of bounds for the maximum k -cut problem on undirected edge-weighted simple graphs. The bounds involve eigenvalues of the weighted adjacency matrix together with geometrical parameters. They generalize previous results on the maximum (2-)cut problem and we demonstrate that they can strictly improve over other eigenvalue bounds from the literature. We also report computational results illustrating the potential impact of the new bounds. [ABSTRACT FROM AUTHOR]

Given an undirected edge weighted graph, the graph partitioning problem consists in determining a partition of the node set of the graph into subsets of prescribed sizes, so as to maximize the sum of the weights of the edges having both endpoints in the same subset. We introduce a new class of bounds for this problem relying on the full spectral information of the weighted adjacency matrix A. The expression of these bounds involves the eigenvalues and particular geometrical parameters defined using the eigenvectors of A. A connection is established between these parameters and the maximum cut problem. We report computational results showing that the new bounds compare favorably with previous bounds in the literature. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The rank of a digraph is defined as the rank of its adjacency matrix. In this paper we show how to find all digraphs of rank k from the reduced bipartite graphs of rank 2 k. In particular, since the bipartite graphs of rank 2 , 4 and 6 are known, then we characterize digraphs of rank 1 , 2 and 3. The results are based on rank-preserving operations on digraphs such as splitting and fusion of vertices or twin-deletion and vertex-multiplication. [ABSTRACT FROM AUTHOR]

In an earlier work, the author together with Guo [7] introduced the Hermitian adjacency matrix of directed (and partially directed) graphs. However, it appears that a more natural Hermitian matrix exists, and it is the purpose of this note to bring this new Hermitian matrix to the attention of researchers in algebraic graph theory. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with n vertices v 1 , ... , v n and m edges. Let A (G) = [ a i j ] n × n be the adjacency matrix of G , that is a i j = 1 if v i and v j are adjacent, and a i j = 0 , otherwise. Let λ 1 , ... , λ n be the eigenvalues of A (G). The energy of G , denoted by E (G) , is defined as | λ 1 | + ⋯ + | λ n |. It is well known that 2 m ≤ E (G) ≤ 2 m n. In this paper we improve the latter lower bound and prove that if all eigenvalues of G are non-zero, then E (G) ≥ 2 | λ 1 λ n | | λ 1 | + | λ n | 2 m n , where | λ 1 | ≥ ⋯ ≥ | λ n |. We show that the equality holds if and only if G = n 2 K 2 or G = p K β + 1 ⋃ q T β + 1 , where p and q are some non-negative integers and β ≥ 2 and T β + 1 is the graph K β + 1 , β + 1 ∖ M , where M is a perfect matching of K β + 1 , β + 1. Finally by studying the | λ 1 λ n | | λ 1 | + | λ n | of graphs, we find some lower bounds for the energy of graphs. In particular, we obtain that if G has no eigenvalue in the interval (− 1 , 1) , then E (G) ≥ 2 m 2 n − 2 n , and the equality holds if and only if G is the complete graph K n. [ABSTRACT FROM AUTHOR]

The Gershgorin Circle Theorem is a well-known and efficient method for bounding the eigenvalues of a matrix in terms of its entries. If A is a symmetric matrix, by writing A = B + x 1 , where 1 is the matrix with unit entries, we consider the problem of choosing x to give the optimal Gershgorin bound on the eigenvalues of B , which then leads to one-sided bounds on the eigenvalues of A. We show that this x can be found by an efficient linear program (whose solution can in may cases be written in closed form), and we show that for large classes of matrices, this shifting method beats all existing piecewise linear or quadratic bounds on the eigenvalues. We also apply this shifting paradigm to some nonlinear estimators and show that under certain symmetries this also gives rise to a tractable linear program. As an application, we give a novel bound on the lowest eigenvalue of a adjacency matrix in terms of the "top two" or "bottom two" degrees of the corresponding graph, and study the efficacy of this method in obtaining sharp eigenvalue estimates for certain classes of matrices. [ABSTRACT FROM AUTHOR]

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 Randić 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. [ABSTRACT FROM AUTHOR]

To track the gradual change of the adjacency matrix of a simple graph G into the signless Laplacian matrix, V. Nikiforov in [35] suggested the study of the convex linear combination A α ( α-adjacency matrix ), A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) , for α ∈ [ 0 , 1 ] , where A ( G ) and D ( G ) are the adjacency and the diagonal vertex degrees matrices of G , respectively. Taking this definition as an idea the next matrix was considered for a , b ∈ R . The matrix A a , b defined by A a , b ( G ) = a D ( G ) + b A ( G ) , extends the previous α -adjacency matrix. This matrix is designated the ( a , b ) -adjacency matrix of G . Both adjacency matrices are examples of universal matrices already studied by W. Haemers. In this paper, we study the ( a , b ) -adjacency spectra for a family of compound graphs formed by disjoint balanced trees whose roots are identified to the vertices of a given graph. In consequence, new families of cospectral (adjacency, Laplacian and signless Laplacian) graphs, new hypoenergetic graphs (graphs whose energy is less than its vertex number) and new explicit formulae for Estrada, signless Laplacian Estrada and Laplacian Estrada indices of graphs were obtained. Moreover, sharp upper bounds of the above indices for caterpillars, in terms of length of the path and of the maximum number of its pendant vertices, are given. [ABSTRACT FROM AUTHOR]

A signed graph is a pair Γ = (G , σ) , where x = (V (G) , E (G)) is a graph and σ : E (G) → { + 1 , − 1 } is the sign function on the edges of G. For any α ∈ [ 0 , 1 ] we consider the matrix A α (Γ) = α D (G) + (1 − α) A (Γ) , where D (G) is the diagonal matrix of the vertex degrees of G , and A (Γ) is the adjacency matrix of Γ. Let m A α (Γ) (α) be the multiplicity of α as an A α (Γ) -eigenvalue, and let G have p (G) pendant vertices, q (G) quasi-pendant vertices, and no components isomorphic to K 2. It is proved that m A α (Γ) (α) = p (G) − q (G) whenever all internal vertices are quasi-pendant. If this is not the case, it turns out that m A α (Γ) (α) = p (G) − q (G) + m N α (Γ) (α) , where m N (Γ) (α) denotes the multiplicity of α as an eigenvalue of the matrix N α (Γ) obtained from A α (Γ) taking the entries corresponding to the internal vertices which are not quasi-pendant. Such results allow to state a formula for the multiplicity of 1 as an eigenvalue of the Laplacian matrix L (Γ) = D (G) − A (Γ). Furthermore, it is detected a class G of signed graphs whose nullity – i.e. the multiplicity of 0 as an A (Γ) -eigenvalue – does not depend on the chosen signature. The class G contains, among others, all signed trees and all signed lollipop graphs. It also turns out that for signed graphs belonging to a subclass G ′ ⊂ G the multiplicity of 1 as Laplacian eigenvalue does not depend on the chosen signatures. Such subclass contains trees and circular caterpillars. [ABSTRACT FROM AUTHOR]

Abstract The spectral radius of a graph is the largest eigenvalue of the adjacency matrix corresponding to this graph. Let G be a graph with long pendant paths. In this note, we estimate the spectral radius of G , by obtaining appropriate upper and lower bounds. As an application, the spectral radius of some k-ary trees are estimated. [ABSTRACT FROM AUTHOR]

Abstract It is proved that for any finite connected graph G , there exists an orientation of G such that the spectral radius of the corresponding Hermitian adjacency matrix is smaller or equal to the spectral radius of the universal cover of G (with equality if and only if G is a tree). This provides a suitable answer to a problem proposed by Mohar. The proof uses the method of interlacing families of polynomials that was developed by Marcus, Spielman, and Srivastava in their seminal work on the existence of infinite families of Ramanujan graphs. [ABSTRACT FROM AUTHOR]

Abstract Finding a diagonal matrix congruent to A − c I for constants c , where A is the adjacency matrix of a graph G allows us to quickly tell the number of eigenvalues in a given interval. If G has clique-width k and a corresponding k -expression is known, then diagonalization can be done in time O (poly (k) n) where n is the order of G. [ABSTRACT FROM AUTHOR]

In this paper, we study 24 possibilities of directed strongly regular graphs with adjacency matrix of rank 6, our proof is based on two effective algorithms. At last, we get 4 families of directed strongly regular graphs with realizable parameter sets, exclude 20 families of directed strongly regular graphs with feasible parameter sets; partially solve the classification problem of directed strongly regular graphs with adjacency matrix of rank 6. [ABSTRACT FROM AUTHOR]

Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G . In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d , and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained. [ABSTRACT FROM AUTHOR]

In this work, we introduce balance-binomial graphs, whose entries of adjacency matrix are balance-binomial coefficients. Then we obtain some characteristic properties of the graph. [ABSTRACT FROM AUTHOR]

Abstract: For a simple graph G, let rank(G) and dnzr(G) denote respectively the rank and the number of distinct nonzero rows of the adjacency matrix A(G) of G. Equivalent conditions are given for the join of two vertex-disjoint graphs to satisfy . A new proof is provided for the known relation rank(G)=dnzr(G) for cographs G. Our approach relies on the concepts of neighborhood equivalence classes, reduced graph and reduced adjacency matrix, and also on a known result that relates the spectrum of the adjacency matrix of a graph with that of its reduced adjacency matrix as well as a new characterization of the nonsingularity of a real symmetric matrix in a special 2×2 block form. Our treatment provides ways to construct graphs G, other than cographs, that satisfy rank(G)=dnzr(G). As a side result we also show that every rational number is equal to the sum of the entries of the inverse of the adjacency matrix of a connected nonsingular graph. [Copyright &y& Elsevier]

Hop Count Matrix (HCM) contains rich connectivity information, which is very important for various Internet of Things (IoT) applications, especially for obtaining the locations of sensor nodes. However, some items of HCMs may be missing due to attacks by malicious nodes or unexpected termination of flooding operations. To solve this problem, two methods, called HCMR-AM and HCMR-DT, are proposed to recover the missing items. In HCMR-AM, the collected partial hop counts are employed to construct Adjacency Matrix (AM), and then the constructed AM is used to obtain the complete HCM. In HCMR-DT, the recovery of HCM is transformed into a classification problem, where multi-dimensional features are used for joint prediction to achieve more accurate recovery performance. Extensive experimental results demonstrate that compared to the original SVT and HCMR-NBC, our proposed algorithms have significant improvement in recovery performance and execution efficiency. In addition, the complete HCM is used for node localization, and experimental results show that the HCM recovered by the proposed methods can achieve the same localization performance as the HCM without missing value when the observation ratio of HCM is greater than 30%, which cannot be achieved by other recovery algorithms. • A hop count matrix recovery scheme based on adjacency matrix is proposed. • A hop count matrix recovery method using Decision Tree is developed. • The complete hop count matrices are suitable for range-free localization. [ABSTRACT FROM AUTHOR]

Abstract: Consider a graph on vertices with adjacency matrix and degree sequence . A universal adjacency matrix of is any matrix in Span with a nonzero coefficient for , where and and are the identity and all-ones matrix, respectively. Thus a universal adjacency matrix is a common generalization of the adjacency, the Laplacian, the signless Laplacian and the Seidel matrix. We investigate graphs for which some universal adjacency matrix has just two eigenvalues. The regular ones are strongly regular, complete or empty, but several other interesting classes occur. [Copyright &y& Elsevier]

Abstract: Neural regression provides a rapid solution to modeling complex systems with minimal computation effort. Recurrent structures such as fuzzy cognitive map (FCM) enable for drawing cause–effect relationships among system variables assigned to graph nodes. Accordingly, the obtained matrix of edges, known as adjacency model, represents the overall behavior of the system. With this, there are many applications of semantic networks in data mining, computational geometry, physics-based modeling, pattern recognition, and forecast. This article examines a methodology for drawing application-specific adjacency models. The idea is to replace crisp neural weights with functions such as polynomials of desired degree, a property beyond the current scope of neural regression. The notion of natural adjacency matrix is discussed and examined as an alternative to classic neural adjacency matrix. There are examples of stochastic and complex engineering systems mainly in the context of modeling residential electricity demand to examine the proposed methodology. [Copyright &y& Elsevier]

Abstract: A weighted directed graph is a directed graph G whose underlying undirected graph is simple and whose edges have nonzero (directional) complex weights, that is, the presence of an edge of weight is as good as the presence of the edge with weight , the complex conjugate of . Let G be a weighted directed graph on vertices . Denote by the weight of an edge . The adjacency matrix of G is an matrix with entries or or 0, depending on whether or or otherwise, respectively. We supply a characterization of those unicyclic weighted directed graphs G whose edges have weights from the set and whose adjacency matrix satisfies the following property: ‘λ is an eigenvalue of with multiplicity k if and only if is an eigenvalue of with the same multiplicity’. [Copyright &y& Elsevier]

Abstract: We calculate the Smith normal form of the adjacency matrix of each of the following graphs or their complements (or both): complete graph, cycle graph, square of the cycle, power graph of the cycle, distance matrix graph of cycle, Andrásfai graph, Doob graph, cocktail party graph, crown graph, prism graph, Möbius ladder. The proofs operate by finding the abelianization of a cyclically presented group whose relation matrix is column equivalent to the required adjacency matrix. [Copyright &y& Elsevier]