Search

With the deterioration growth of water pipes, the frequency of identifying segments and unintended isolation in water distribution networks is expected to increase, because it can help identify the number of nodes that cannot be supplied and their locations when a failure occurs. Therefore, a methodology for identifying segments and unintended isolation was developed and verified using examples. In addition, a case study was conducted to confirm that the proposed methodology could be applied to actual fields. The proposed method only requires the node-based adjacency matrix K for identification, where the connectivity of the current network can be intuitively understood with the constructed matrices. Moreover, this methodology is easy to adopt using the single row-first search method. The proposed framework is compatible with the data storage format of hydraulic analysis software. Finally, the proposed methodology can be used in various research on configuring and analyzing water distribution networks. [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.

The fact that the adjacency matrix of every finite graph is diagonalizable plays a fundamental role in spectral graph theory. Since this fact does not hold in general for digraphs, it is natural to ask whether it holds for digraphs with certain level of symmetry. Interest in this question dates back to the early 1980 s, when P. J. Cameron asked for the existence of arc-transitive digraphs with non-diagonalizable adjacency matrix. This was answered in the affirmative by Babai (J Graph Theory 9:363–370, 1985). Then Babai posed the open problems of constructing a 2-arc-transitive digraph and a vertex-primitive digraph whose adjacency matrices are not diagonalizable. In this paper, we solve Babai's problems by constructing an infinite family of s-arc-transitive digraphs for each integer s ≥ 2 , and an infinite family of vertex-primitive digraphs, both of whose adjacency matrices are non-diagonalizable. [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]

Molecular network plays a critical role in determining dynamic elasticity of soft condensed polymers, e.g., their varied cross-linking densities and end-to-end distances with changed Young's moduli. Although it has been studied for decades, the coupling relationship between vertices and edges of molecular networks is not well understood, mainly because the degree of the crosslinking points and asymmetry molecular networks have not been considered in the previously models. In this study, a graph theory was employed to formulate an undirected graphical model and describe the coupling between vertices and edges in molecular networks, based on which the dynamic elasticity of polyelectrolyte hydrogel was modeled. From the Kirchhoff graph theory and bead-spring model, the coupling relationship between vertices and edges was obtained using end-to-end distance and viscosity parameters. Combining the Watts–Strogatz model and kinetic probability, the coupling between vertices and edges for the polyelectrolyte network was studied. Furthermore, an adjacency matrix with eigenvalue, number of vertices and mean degree was proposed to formulate constitutive relationships including dynamic elasticity and stress-strain, according to rubber elasticity theory and Mooney-Rivlin model, respectively. The linking between the vertices and edges determines the network structure and dynamic elasticity of the polyelectrolyte hydrogel. Based on the graph theory, the vertices and edges are encoded by adjacency matrix, which is proposed to describe the dynamic elasticity of symmetric and asymmetric network structures using the crosslinking density and end-to-end distance. Finally, effectiveness of the undirected graphical model was verified using both finite element analysis and experimental results of polyelectrolyte hydrogels reported in literature. Constitutive stress-elongation ratio curves for the polyelectrolyte hydrogel, of which the graph network is determined by the mean degree of d = 2, d = 3, d = 4, d = 5, d = 6 and d = 7, at the same vertex number of N = 8 in molecular network. [Display omitted] • An undirected graphical model and describe the coupling between vertices and edges in molecular networks. • Dynamic elasticity of polyelectrolyte hydrogel has been modeled using the adjacency matrix. • A constitutive relationship is developed to understand the molecular networks and their dynamic elasticities. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n . For i = 1 , 2 , … , n , let d i be the degree of the vertex v i of G . The extended adjacency matrix A ex of G is defined so that its ( i, j )-entry is equal to 1 2 ( d i d j + d j d i ) if the vertices v i and v j are adjacent, and 0 otherwise,Yang et al. (1994). The spectral radius η 1 and the energy E e x of the A ex -matrix are examined. Lower and upper bounds on η 1 and E e x are obtained, and the respective extremal graphs characterized. [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]

A block graph is a graph in which every block is a complete graph. Letbe a block graph and letbe the adjacency matrix of. We first obtain a formula for the determinant ofover reals. It is shown thatis nonsingular overif and only if the removal of any vertex fromproduces a graph with exactly one odd component. A formula for the inverse ofoveris obtained, whenever it exists. We obtain some results for the adjacency matrices over, of claw-free block graphs, which are the same as the line graphs of trees, and for the adjacency matrices of flowers, which are block graphs with only one cut-vertex. [ABSTRACT FROM AUTHOR]

Research on complex networks is becoming a very hot topic in recent years, among which node matching problem is an important issue. The aim of node matching problem is to find out the corresponding relations between the individuals of associated networks. Traditional node matching problem of networks always hypothesize that a proportion of matching nodes are known. However, if the ratio of matched nodes is very small, the matching accuracy of the remaining nodes cannot be evaluated accurately. What is more, we may have not any matched nodes for reference at all. In view of this, this paper established the mathematic model of node matching problem based on the adjacency matrixes of networks, and presented an evolutionary algorithm to solve it. The experimental results show that the proposed method can achieve satisfactory matching precision in the absence of any matched nodes. [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]

The concept of dominance is one of the most important ideas in graph theory for handling random events, and it has drawn the interest from many scholars. Research related to graph energy has garnered a lot focus recently. The application of single-valued neutrosophic graphs (SVNGs) for energy, Laplacian energy, and dominating energy has been recommended by previous studies. In this research, we apply the concepts of single-valued neutrosophic sets (SVNS) to graph structures (GSs) and investigate some intriguing features of single-valued neutrosophic graph structures (SVNGS). Moreover, the notions of λJ-dominating energy GS in an SVNGS environment is analyzed in this study. More specifically, illustrative examples are used to develop the adjacency matrix of a λJ-dominating SVNGS, as well as the spectrum of the adjacency matrix and their related theory. Further, the SVNGS λJ-dominating energy is determined. We go over various characteristics and constraints for the energy of SVNGS with λJ-dominating. Further, we introduce the idea of isomorphic and identical λJ-dominating SVNGS energy, which has been studied using relevant examples, and some of its established properties are presented. [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]

Abstract: Using the spectral distribution associated with the adjacency matrix of graphs, we introduce a new method of calculation of amplitudes of continuous-time quantum walk on some rather important graphs, such as line, cycle graph C n , complete graph K n , graph G n , finite path and some other finite and infinite graphs, where all are connected with orthogonal polynomials such as Hermite, Laguerre, Tchebichef, and other orthogonal polynomials. It is shown that using the spectral distribution, one can obtain the infinite time asymptotic behavior of amplitudes simply by using the method of stationary phase approximation (WKB approximation), where as an example, the method is applied to star, two-dimensional comb lattices, infinite Hermite and Laguerre graphs. Also by using the Gauss quadrature formula one can approximate the infinite graphs with finite ones and vice versa, in order to derive large time asymptotic behavior by WKB method. Likewise, using this method, some new graphs are introduced, where their amplitudes are proportional to the product of amplitudes of some elementary graphs, even though the graphs themselves are not the same as the Cartesian product of their elementary graphs. Finally, by calculating the mean end to end distance of some infinite graphs at large enough times, it is shown that continuous-time quantum walk at different infinite graphs belong to different universality classes which are also different from those of the corresponding classical ones. [Copyright &y& Elsevier]

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]

Graph Theory offers tools for a wide area of fields: mathematics, physics, chemistry, biology, biochemistry, bioinformatics and computer science. Graphical representations have been used not only for comparative studies of genetic material, but also to visualize real or fictional relationships and interactions between vertices. This review aims to highlight some of the most frequently used transdisciplinary applications of graph theory and to present the steps necessary to build such graphs. The development of graphical representations enabled the comparisons of similarities and differences between long DNA sequences. [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]

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.

Graph structure is a developing field with many real-world applications and advancements, particularly effective frameworks for integrative problem-solving in computer networks and artificial intelligence systems. To define the idea of an Interval-Valued Complex Neutrosophic Graph Structure (IVCNGS), the concept of an Interval-Valued Complex Neutrosophic Set (IVCNS) is applied to the graph structure. Using the adjacency matrix to calculate the degree of vertex, we have defined some findings about the IVCNGS. Further, we compute the energy and Laplacian energy of IVCNGS. Moreover, we derive the lower and upper bounds for the energy and Laplacian energy of IVCNGS, and we have discussed their application in IVCNGS. Finally, we develop an algorithm that clarifies the fundamental processes of the application. [ABSTRACT FROM AUTHOR]