Search

The relationship between anatomic and resting state functional connectivity of large-scale brain networks is a major focus of current research. In previous work, we introduced a model based on eigen decomposition of the Laplacian which predicts the functional network from the structural network in healthy brains. In this work, we apply the eigen decomposition model to two types of epilepsy; temporal lobe epilepsy associated with mesial temporal sclerosis, and MRI-normal temporal lobe epilepsy. Our findings show that the eigen relationship between function and structure holds for patients with temporal lobe epilepsy as well as normal individuals. These results suggest that the brain under TLE conditions reconfigures and rewires the fine-scale connectivity (a process which the model parameters are putatively sensitive to), in order to achieve the necessary structure-function relationship.

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]

Let G be a graph with vertex set V(G) = {v1,v2,..., vn}. Let A(G) be the adjacency matrix of a graph G. The rows of A(G) corresponding to a vertex v of G, denoted by s(v) is the string. The Hamming index of a graph G is the sum of the Hamming distances between all pairs of vertices of G. In this paper we obtain Hamming index generated by adjacency matrix of some thorn graphs. [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]

We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the g -Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs. [ABSTRACT FROM AUTHOR]

This article provides a new approach to searching solutions of water transport optimization problems. It brings a new tool of the graph theory which is the Weighted Adjacency Matrix. This Weighted Adjacency Matrix is suitable for searching for the Minimum Spanning Tree (MST) of the graph. It describes the Weighted Adjacency Matrix as a new element, and shows how it could be used in cases where weighted edges of the graph are given. This creates a new procedure of searching the MST of the graph and completes previously known algorithms of searching for the MST. In the field of ship transportation it could be succesfully used for solutions of optimizing transportation routes where lowest transport costs are needed. Proposed Weighted Adjacency Matrix could be used in similar issues in the field of graph theory, where graphs with weighted edges are given. The procedure is shown in the given example. The paper discusses the application of such route optimization technique forthe maritime sector. [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]

Graph theory is a branch of mathematics that is crucial to modelling applicable systems and networks using matrix representations. In this article, a novel graph-theoretic model was used to assess an urban water distribution system (WDS) in Saudi Arabia. This graph model is based on representing its elements through nodes and links using a weighted adjacency matrix. The nodes represent the points where there can be a water input or output (sources, treatment plants, tanks, reservoirs, consumers, connections), and links represent the edges of the graph that carry water from one node to another (pipes, pumps, valves). Four WDS benchmarks, pumps, tanks, reservoirs, and external sources were used to validate the framework at first. This validation showed that the worst-case scenarios for vulnerability were provided by the fault sequence iterating the calculation of the centrality measurements. The vulnerability framework’s application to the Saudi Arabian WDS enabled the identification of the system’s most vulnerable junctions and zones. As anticipated, the regions with the fewest reservoirs were most at risk from unmet demand, indicating that this system is vulnerable to the removal of junctions and pipes that are intricately associated with their neighbours. Different centrality metrics were computed, from which the betweenness centrality offered the worst vulnerability prediction measures. The aspects and zones of the WDS that can more significantly impact the water supply in the event of a failure were identified by the vulnerability framework utilising attack tactics.

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]

The paper presents a novel spectral algorithm EVSA (eigenvector structure analysis), which uses eigenvalues and eigenvectors of the adjacency matrix in order to discover clusters. Based on matrix perturbation theory and properties of graph spectra we show that the adjacency matrix can be more suitable for partitioning than other Laplacian matrices. The main problem concerning the use of the adjacency matrix is the selection of the appropriate eigenvectors. We thus propose an approach based on analysis of the adjacency matrix spectrum and eigenvector pairwise correlations. Formulated rules and heuristics allow choosing the right eigenvectors representing clusters, i.e., automatically establishing the number of groups. The algorithm requires only one parameter-the number of nearest neighbors. Unlike many other spectral methods, our solution does not need an additional clustering algorithm for final partitioning. We evaluate the proposed approach using real-world datasets of different sizes. Its performance is competitive to other both standard and new solutions, which require the number of clusters to be given as an input parameter. [ABSTRACT FROM AUTHOR]

In order to discuss the minimum eigenvalue of adjacency matrix in the class of complementary graphs of the tricyclic graph with a given order of n and n－4 pendent vertexes, the unique graph whose minimum eigenvalue reaches the minimum is characterized. Based on the simple undirected connected graph,the minimum eigenvalue of the graph is studied from the structure of the complement graph, and the minimum eigenvalue of the adjacency matrix in the complement graph class of the tricyclic graph with a given order of n and n－4 pendent vertexes reaches the minimum unique graph when the value is λ( G ( 85;P](n-4)/2,(n-4)/2[XC符号2.eps;%90%90;P])C)[WTBZ]. The result shows that the associative graph adjacency matrix is a matrix which represents the adjacency between vertices, and its minimum eigenvalue is the minimum eigenvalue of graph, which can describe the essential properties of graph well. The conclusion from this research shows that the minimum eigenvalue of the complement graph of the tricyclic graph with a given order of n and n－4 pendent vertexes reaches the minimum eigenvalue, which provides certain reference for further study of the minimum eigenvalue of the adjacency matrix in the complement graph class.

Maximal biclique (also known as complete bipartite) subgraphs can model many applications in Web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that 1) the number of closed patterns in the adjacency matrix of G is even, 2) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G, and 3) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a nonduplicated enumeration, in particular, for enumerating those maximal bicliques with a large size, where m and n are the number of edges and vertices of the graph, respectively. We evaluate the high efficiency of our algorithm by comparing it to state- of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even, but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops. [ABSTRACT FROM AUTHOR]

We explore the relationship between lattice field theory and graph theory, placing special emphasis on the interplay between Dirac and scalar lattice operators and matrices within the realm of spectral graph theory. Beyond delving into fundamental concepts of spectral graph theory, such as adjacency and Laplacian matrices, we introduce a novel matrix called an "antisymmetrized adjacency matrix", specifically tailored for cycle digraphs (T 1 lattice) and simple directed paths (B 1 lattice). The nontrivial relationship between graph theory matrices and lattice operators shows that the graph Laplacian matrix mirrors the lattice scalar operator and the Wilson term in lattice fermions, while the antisymmetrized adjacency matrix, along with its extensions to higher dimensions, is equivalent to naive lattice Dirac operators. Building upon these connections, we provide rigorous proofs for two key assertions: (i) The count of zero-modes in a free lattice scalar operator coincides with the zeroth Betti number of the underlying graph (lattice). (ii) The maximum count of Dirac zero-modes in a free lattice fermion operator is equivalent to the cumulative sum of all Betti numbers when the D -dimensional graph results from a Cartesian product of cycle digraphs (T 1 lattice) and simple directed paths (B 1 lattice). [ABSTRACT FROM AUTHOR]

Let G be a graph with the adjacency matrix A (G) , and let D (G) be the diagonal matrix of the degrees of G. Nikiforov first defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , 0 ≤ α ≤ 1 , which shed new light on A (G) and Q (G) = D (G) + A (G) , and yielded some surprises. The α − adjacency energy E A α (G) of G is a new invariant that is calculated from the eigenvalues of A α (G) . In this work, by combining matrix theory and the graph structure properties, we provide some upper and lower bounds for E A α (G) in terms of graph parameters (the order n, the edge size m, etc.) and characterize the corresponding extremal graphs. In addition, we obtain some relations between E A α (G) and other energies such as the energy E (G) . Some results can be applied to appropriately estimate the α -adjacency energy using some given graph parameters rather than by performing some tedious calculations. [ABSTRACT FROM AUTHOR]

Under elimination of two arcs, spectrum of digraph having ring structure and two Hamiltonian cycles is shown real, if and only if the number of vertices is even and “interval between arcs,” eliminated from the same cycle, is maximal. Possibility to apply the obtained results to evaluate failure-resistance of networks with ring topology is considered. [ABSTRACT FROM AUTHOR]

The relationship between anatomic and resting state functional connectivity of large-scale brain networks is a major focus of current research. In previous work, we introduced a model based on eigen decomposition of the Laplacian which predicts the functional network from the structural network in healthy brains. In this work, we apply the eigen decomposition model to two types of epilepsy; temporal lobe epilepsy associated with mesial temporal sclerosis, and MRI-normal temporal lobe epilepsy. Our findings show that the eigen relationship between function and structure holds for patients with temporal lobe epilepsy as well as normal individuals. These results suggest that the brain under TLE conditions reconfigures and rewires the fine-scale connectivity (a process which the model parameters are putatively sensitive to), in order to achieve the necessary structure-function relationship. [ABSTRACT FROM AUTHOR]

If A(G) and D(G) are respectively the adjacency matrix and the diagonal matrix of vertex degrees of a connected graph G, the generalized adjacency matrix Aα(G) is defined as Aα(G) = α D(G) + (1 - α) A(G), where 0 ≤ α ≤ 1. The Aα (or generalized) spectral radius λ(Aα(G)) (or simply λα) is the largest eigenvalue of Aα(G). In this paper, we show that λα ≤ α Δ + (1 - α)√ 2m ( 1 - 1/ω), where m, Δ and ω = ω(G) are respectively the size, the largest degree and the clique number of G. Further, if G has order n, then we show that ... where di and mi are respectively the degree and the average 2-degree of the vertex Vi. [ABSTRACT FROM AUTHOR]

In geographic, the eigenvalues and eigenvectors of transportation network provides many informations about its connectedness. It is proven that the more highly connected in a transportation network G has largest eigenvalue and hence more multiple occurrences of the eigenvalue -1. For a graph G with adjacency matrix A, the multiplicity of the eigenvalue -1 equals the dimension of the null space of the matrix A + I. In this paper, we constructed a high closed zero sum weighting of G and by which its proved that, the dimension of the null space of the eigenvalue -1 is the same as the number of independent variables used in a non-trivial high closed zero sum weighting of the graph. Multiplicity of -1 as an eigenvalue of known graphs and of corona product of certain classes of graphs are determined and two classes of -1- nut graphs are constructed.

A Modular Reconfigurable Robot (MRR) composed of standard joint and link modules has the advantages of rapid changeover of assembly configurations for a diversity of application requirements. To tackle the kinematics analysis issues for an MRR, it is essential to develop a generic method to mathematically represent all possible assembly configurations and automatically generate their kinematic models. In this paper, two types of robot modules, i.e., revolute joint modules and rigid link modules, are considered as the basic building blocks of an MRR. The topological structure of an MRR is represented by a graph, termed an Assembly Graph (AG), in which all robot modules, regardless of their types, are treated as vertices, while the connecting interfaces between any two robot modules are treated as edges. Based on graph theory, a modified adjacency matrix, termed an Assembly Adjacency Matrix (AAM), is proposed to represent the assembly configuration of an MRR, in which the three-dimensional assembly information is specified with connecting port vectors for the adjacent modules. A path matrix derived from the AAM of an MRR is employed to describe the connecting sequence of its constituting modules. The local frame representation of the Product-of-Exponentials (POE) formula is employed, which is configuration-independent. Therefore, for an MRR configuration represented with an AAM, its kinematic model will be automatically generated according to its path matrix. The proposed assembly configuration representation and kinematic modeling method are validated through a dual-branch MRR configuration. [ABSTRACT FROM AUTHOR]

The traditional modelling and simulation analysis methods based on graph theory are difficult to present the structural characteristics and dynamic laws of cyber-physical power systems (CPPS). In order to reduce the complexity of the attack graph, this paper proposes a CPPS robustness analysis method based on the reachable matrix. Based on the evolution of the augmented adjacency matrix of cyber-physical power system, this method uses the reachable matrix to obtain the maximum connectivity matrix of the system (the adjacency matrix corresponding to the largest connected subgraph of cyber-physical power system), and then, evaluates and analyses the robustness of cyber-physical power system. The IEEE118 node standard model is taken as an example to carry out the simulation experiment. The experimental results show that the reachable matrix has feasibility in the robustness analysis of cyber-physical power systems. Further through the contrast experiment found that compared with the robustness analysis method based on graph theory, the proposed method in this paper can reduce the modelling complexity of the mutual coupling network, reduce the complexity of the attack graph, and clearly and intuitively show the structural characteristics and dynamic laws of the network connection in the system. [ABSTRACT FROM AUTHOR]

For the adjacency matrix A(G) and diagonal matrix of the vertex degrees D(G) of a simple graph G, the A(G) matrix is the convex combinations of D(G) and A(G), and is defined as A(G) = D(G)+(1)A(G), for 0 n be the eigenvalues of A(G) (which we call -adjacency eigenvalues of the graph G). The generalized adjacency energy also called -adjacency energy of the graph G is defined as EA (G) = is the average vertex degree, m is the size and n is the order of G. The -adjacency energy of a graph G merges the theory of energy (adjacency energy) and the signless Laplacian energy, as EA0 (G) = E (G) and 2E A 12 (G) = QE(G), where E (G) is the energy and QE(G) is the signless Laplacian energy of G. In this paper, we obtain some new upper and lower bounds for the generalized adjacency energy of a graph, in terms of different graph parameters like the vertex covering number, the Zagreb index, the number of edges, the number of vertices, etc. We characterize the extremal graphs attained these bounds. [ABSTRACT FROM AUTHOR]

Graph theory is one of the neglected branches of mathematics in Nigeria but with the most applications in other fields of research. This article shows the paucity, importance, and necessity of graph theory in the development of Nigeria. The adjacency matrix and dual graph of the Nigeria map were presented. The graph spectrum and energies (graph energy and Laplacian energy) of the dual graph were computed. Then the chromatic number, maximum degree, minimum spanning tree, graph radius, and diameter, the Eulerian circuit and Hamiltonian paths from the dual graph were obtained and discussed. [ABSTRACT FROM AUTHOR]

The nullity of a graph G is the multiplicity of zero as an eigenvalue of its adjacency matrix. An assignment of weights to the vertices of a graph, that satisfies a zero sum condition over the neighbors of each vertex, and uses maximum number of independent variables is denoted by a high zero sum weighting of the graph. This applicable tool is used to determine the nullity of the graph. Two types of graphs are defined, and the change of their nullities is studied, namely, the graph G+ab constructed from G by adding a new vertex ab which is joint to all neighbors of both vertices a and b of G, and G•ab which is obtained from G+ab by removing both vertices a and b. [ABSTRACT FROM AUTHOR]