Search

Gain graphs are graphs where the edges are given some orientation and labeled with the elements (called gains) from a group so that the gains are inverted when we reverse the direction of the edges. Generalizing the notion of gain graphs, skew gain graphs have the property that the gain of a reversed edge is the image of edge gain under an anti-involution. In this paper, we deal with the adjacency matrix of skew gain graphs with an involutive automorphism on a field of characteristic zero and their characteristic polynomials. Spectra of some particular skew gain graphs are also discussed. [ABSTRACT FROM AUTHOR]

It was shown in 2006 that among the nonsingular trees T (whose adjacency matrix A(T) is nonsingular), the corona trees (trees that are obtained by taking any tree T and then adding a new pendant vertex at each vertex of T) are the only ones which satisfy the reciprocal eigenvalue property (λ is an eigenvalue of A(T) if and only if 1 λ is an eigenvalue of A(T), where their multiplicities are allowed to be different). A general question remained open. Can there be a tree which has at least one zero eigenvalue and whose nonzero eigenvalues satisfy the reciprocal eigenvalue property? In this note, we show that there are no such trees with at least two vertices. The proof is a beautiful application of the product of graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be its adjacency matrix. The terms singularity, eigenvalues, and characteristic polynomial of G mean those of A (G). A nonsingular graph G is said to have the reciprocal eigenvalue property if the reciprocal of each eigenvalue of G is also an eigenvalue. A graph G (possibly singular) is said to have the weak reciprocal eigenvalue property if the reciprocal of each nonzero eigenvalue of it is also an eigenvalue. In Barik et al. (2022) [3] , the authors proved that there is no nontrivial tree with the weak reciprocal eigenvalue property and posed the following question: "Does there exist a nontrivial graph with the weak reciprocal eigenvalue property?" Suppose that G is singular and the characteristic polynomial of G is x n − k (x k + a 1 x k − 1 + ⋯ + a k). Assume that A (G) has rank k , so that a k ≠ 0. Can we ever have | a k | = 1 ? The answer turns out to be negative. As an application, we settle the question posed in Barik et al. (2022) [3]. Another similar application is also mentioned. It is natural to wonder, "Does there exist a nontrivial, simple, connected weighted graph with the weak reciprocal eigenvalue property?" We provide a class of such graphs. Furthermore, we extend our results to weighted graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A (G) be the adjacency matrix of G. The graph G is said to have the reciprocal eigenvalue property (R) if A (G) is nonsingular and 1 λ is an eigenvalue of A (G) whenever λ is an eigenvalue of A (G). Further, if λ and 1 λ have the same multiplicity, for each eigenvalue λ , then G is said to have the strong reciprocal eigenvalue property (SR). Till date, all the classes of bipartite graphs that are found to have property (R), are found to have property (SR) and it is not known whether these two properties are equivalent even for the bipartite graphs with a unique perfect matching. Among nonbipartite graphs, there is only one known graph class for which these two properties are not equivalent. In this article, we construct some more classes of nonbipartite graphs with property (R) but not (SR). [ABSTRACT FROM AUTHOR]

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5 ⩽ k ⩽ 8 and n ⩾ k + 5) with the minimal least eigenvalue. [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]

Let G be a graph on n vertices and λ 1 ≥ λ 2 ≥ ... ≥ λ n its eigenvalues. The Estrada index of G is defined as E E (G) = ∑ i = 1 n e λ i . In this work, we use an increasing sequence converging to the λ 1 to obtain an increasing sequence of lower bounds for E E (G). In addition, we generalize this succession for the Estrada index of an arbitrary symmetric nonnegative matrix. [ABSTRACT FROM AUTHOR]

Let G = (V (G) , E (G)) be a simple graph with vertex set V (G) and edge set E (G) , c (G) = | E (G) | − | V (G) | + θ (G) be the dimension of cycle spaces of G with θ (G) the number of connected components of G , m (G) be the matching number of G , and η (G) be the nullity of G. It was shown in Wang and Wong (2014) that the nullity η (G) of G is bounded by an upper bound and a lower bound as | V (G) | − 2 m (G) − c (G) ≤ η (G) ≤ | V (G) | − 2 m (G) + 2 c (G). Graphs with nullity attaining the upper bound and the lower bound have been characterized by Song et al. (2015) and Wang (2016), respectively. In this paper, we prove that there is no graph with nullity η (G) = | V (G) | − 2 m (G) + 2 c (G) − 1. For fixed c (G) , infinitely many connected graphs with nullity | V (G) | − 2 m (G) + 2 c (G) − k , (0 ≤ k ≤ 3 c (G) , k ≠ 1) are also constructed. [ABSTRACT FROM AUTHOR]

The goal of this contribution is to reveal the analytical framework and synthesis guidelines for frontal-attacking targets (FRATs) and flankattacking targets (FLATs) from the point of view of a graph as a mathematical object. The final outcome of this study are three graph models that in many ways describe the shooting targets under consideration. The first graph model characterizes the structure of connections between the vertices using an undirected graph. The model showed that the complexity of silhouettes leads to an increase of the path in the graph and growth of the complexity of its internal structure. The second graph model allows the analysis of the connectivity of the graph vertices. In this case, a bipartite graph is used. As a result, the reviewed FRATs and FLATs are described by the same graph. The second model showed its indifference to the types of the used graphic primitives (GPs). The third graph model was developed for the analysis of the common borders of the neighboring GPs and it uses a bipartite graph. It is also indifferent to the types of the used GPs, but it takes into account the length of the common borders. The third model describes FRATs/FLATs groups in the same way. When using I-III models, one can design GPs and carry out the synthesis of new targets. A full group of flank-attacking targets consisting of five silhouettes and their GPs is offered. [ABSTRACT FROM AUTHOR]

Abstract A (1 , ≤ ℓ) -identifying code in digraph D is a dominating subset C of vertices of D , such that all distinct subsets of vertices of D with cardinality at most ℓ have distinct closed in-neighborhoods within C. As far as we know, it is the very first time that the spectral graph theory has been applied to the identifying codes. We give a new method to obtain an upper bound on ℓ for digraphs. The results obtained here can also be applied to graphs. [ABSTRACT FROM AUTHOR]

A comparison of two groups of plane shooting targets (PSTs) characterizing the shooter-silhouette in different observation and rifle-firing positions was the starting point for this study. Selected infantry targets are used for shooting training in the Russian Federation and in the Swiss Confederation. The comparison results of two target groups (five PSTs in each of them) showed a significant similarity of their geometric shapes. To explain this fact, a targets design system (TDS) was developed. The TDS is based on attributing a certain number of simple geometric shapes - geometric primitives (GP). In our case, the number of GPs was equal to ten (five polygons for Russian and five polygons for Swiss targets). The TDS enabled building a human-like target silhouette. If two sides of two adjoining GPs or their parts become common for them, then such GPs can be combined into one common geometric figure whose area is equal to the sum of the two GPs. The TDS was further transformed into two isomorphic graphs. Their adjacency matrix (AM) was obtained. The AM matrices for the Russian PSTs and the Swiss PSTs were the same. To improve the estimation of the area and the coordinates of the target centroid, a matrix modification of Bourke’s formulas were proposed. The geometric areas for the Russian and Swiss PSTs and the location of their centroids were refined and compared. GNU Octave, GeoGebra and Mathcad were used as mathematical software for computer calculations and for graphic visualizations. [ABSTRACT FROM AUTHOR]

Let be a finite-dimensional Hilbert space and be a finite frame for . For , we associate a simple graph denoted by and called frame graph, with all elements of as vertices, and two distinct vertices are adjacent when the inner product of them is nonzero. The associated graph is called a tight frame graph if the mentioned frame is tight. In this paper, we study some basic properties of and investigate the relation between the frame-theoretic properties of and the graph-theoretic properties of . For example, it is shown that trees on more than two vertices and cycles on more than five vertices are not tight frame graphs while complete graphs, complete graphs minus a single edge and the join of each graph with itself are tight frame graphs. [ABSTRACT FROM AUTHOR]

The k-th power of a graph G, denoted by [ABSTRACT FROM AUTHOR]

The energy of a simple graph G , E ( G ) , is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted by E ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

For a fixed real number r we give several necessary and/or sufficient conditions for a graph to have the second largest eigenvalue of the adjacency matrix, or signless Laplacian matrix, less then or equal to r . [ABSTRACT FROM AUTHOR]

Let G = G1 ∪ G2 be the sum of two simple graphs G1, G2 having a common edge or G = G1 ∪ e1 ∪ e2 ∪ G2 be the sum of two simple disjoint graphs G1,G2 connected by two edges e1 and e2 which form a cycle C4 inside G. We give a method of computing the determinant detA(G) of the adjacency matrix of G by reducing the calculation of the determinant to certain subgraphs of G1 and G2. To show the scope and effectiveness of our method we give some examples [ABSTRACT FROM AUTHOR]

In a simple connected graph, the average 2-degree of a vertex is the average degree of its neighbors. With the average 2-degree sequence and the maximum degree ratio of adjacent vertices, we present a sharp upper bound of the spectral radius of the adjacency matrix of a graph, which improves a result in [Y. H. Chen, R. Y. Pan and X. D. Zhang, Two sharp upper bounds for the signless Laplacian spectral radius of graphs, Discrete Math. Algorithms Appl. 3(2) (2011) 185-191]. [ABSTRACT FROM AUTHOR]

Abstract: We give upper and lower bounds for the spectral radius of a nonnegative matrix using its row sums and characterize the equality cases if the matrix is irreducible. Then we apply these bounds to various matrices associated with a graph, including the adjacency matrix, the signless Laplacian matrix, the distance matrix, the distance signless Laplacian matrix, and the reciprocal distance matrix. Some known results in the literature are generalized and improved. [Copyright &y& Elsevier]

Approximations of matrix-valued functions of the form WT f(A)W, where A ∈ Rm×m is symmetric, W ∈ Rm×k, with m large and k ≪ m, has orthonormal columns, and f is a function, can be computed by applying a few steps of the symmetric block Lanczos method to A with initial block-vector W ∈ Rm×k. Golub and Meurant have shown that the approximants obtained in this manner may be considered block Gauss quadrature rules associated with a matrix-valued measure. This paper generalizes anti-Gauss quadrature rules, introduced by Laurie for real-valued measures, to matrix-valued measures, and shows that under suitable conditions pairs of block Gauss and block anti-Gauss rules provide upper and lower bounds for the entries of the desired matrix-valued function. Extensions to matrix-valued functions of the form WT f(A)V, where A ∈ Rm×m may be nonsymmetric, and the matrices V,W ∈ Rm×k satisfy VTW = Ik are also discussed. Approximations of the latter functions are computed by applying a few steps of the nonsymmetric block Lanczos method to A with initial block-vectors V and W. We describe applications to the evaluation of functions of a symmetric or nonsymmetric adjacency matrix for a network. Numerical examples illustrate that a combination of block Gauss and anti-Gauss quadrature rules typically provides upper and lower bounds for such problems. We introduce some new quantities that describe properties of nodes in directed or undirected networks, and demonstrate how these and other quantities can be computed inexpensively with the quadrature rules of the present paper. [ABSTRACT FROM AUTHOR]

Abstract: Let G be a simple connected graph of order n with degree sequence in non-increasing order. The spectral radius of G is the largest eigenvalue of its adjacency matrix. For each positive integer at most n, we give a sharp upper bound for by a function of which generalizes a series of previous results. [Copyright &y& Elsevier]

Abstract: Let be a connected graph with vertex set and a weight function that assigns a nonnegative number to each of its vertices. Then, the -moment of at vertex is defined to be , where stands for the distance function. Adding up all these numbers, we obtain the -moment of : This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the Wiener index , when for every , and the degree distance , obtained when , the degree of vertex . In this paper we derive some exact formulas for computing the -moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding -moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same -moment for every (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product. [Copyright &y& Elsevier]

Modeling of Business processes is essential in many areas. Workflows represent the Business processes. It is possible to identify potential problems while performing verification of workflows. One of the objectives of the verification is to assure reachability. This includes analysis of the deadlock and tempo blocking freeness properties. The paper presents verification approach based on using an adjacency matrix. Spreadsheets are used as a verification tool. The approach is illustrated by the examples which justify the importance of verification in workflow processes. [ABSTRACT FROM PUBLISHER]

Abstract: In this paper we introduce a new parameter for a graph called the minimum universal rank. This parameter is similar to the minimum rank of a graph. For a graph G the minimum universal rank of G is the minimum rank over all matrices of the form where A is the adjacency matrix of G, J is the all ones matrix and D is the matrix with the degrees of the vertices in the main diagonal, and are scalars. Bounds for general graphs based on known graph parameters are given, as is a formula for the minimum universal rank for regular graphs based on the multiplicity of the eigenvalues of A. The exact value of the minimum universal rank of some families of graphs are determined, including complete graphs, complete bipartite graph, paths and cycles. Bounds on the minimum universal rank of a graph obtained by deleting a single vertex are established. It is shown that the minimum universal rank is not monotone on induced subgraphs, but bounds based on certain induced subgraphs, including bounds on the union of two graphs, are given. [Copyright &y& Elsevier]

In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut edges. [ABSTRACT FROM AUTHOR]

Abstract: The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: what is the structure of a connected graph G with rank 5? or equivalently, what is the structure of a connected n-vertex graph G whose adjacency matrix has nullity ? In this paper, we completely characterize connected graphs G whose adjacency matrix has rank 5. [Copyright &y& Elsevier]

Abstract: Of interest here is a characterization of the undirected graphs G such that the Laplacian matrix associated with G can be diagonalized by some Hadamard matrix. Many interesting and fundamental properties are presented for such graphs along with a partial characterization of the cographs that have this property. [Copyright &y& Elsevier]

Let G be a connected graph of order n. The diameter of a graph is the maximum distance between any two vertices of G. In this paper, we will give some bounds on the diameter of G in terms of eigenvalues of adjacency matrix and Laplacian matrix, respectively. [ABSTRACT FROM AUTHOR]

Abstract: The rank of a graph G is defined to be the rank of its adjacency matrix. In this paper, we consider the following problem: What is the structure of a connected graph with rank 4? This question has not yet been fully answered in the literature, and only some partial results are known. In this paper we resolve this question by completely characterizing graphs G whose adjacency matrix has rank 4. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The adjacency matrix of a graph is denoted by and defined as the matrix , where for and 0 otherwise. The largest eigenvalue () of is called the spectral radius or the index of . The Laplacian matrix of is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity () of a graph [12]. In [1,2], Aouchiche et al. have given a series of conjectures on index () and algebraic connectivity () of (see also [3]). Here we prove two conjectures and disprove one by a counter example. [Copyright &y& Elsevier]

Abstract: The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we characterize the graphs with maximum signless Laplacian or adjacency spectral radius among all graphs with fixed order and given vertex or edge connectivity. We also discuss the minimum signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity. Consequently we give an upper bound of signless Laplacian or adjacency spectral radius of graphs in terms of connectivity. In addition we confirm a conjecture of Aouchiche and Hansen involving adjacency spectral radius and connectivity. [Copyright &y& Elsevier]

Abstract: In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all graphs of a fixed order and a given vertex (edge) independence number or vertex (edge) cover number, and get some bounds for the vertex (edge) independence number, vertex (edge) cover number of a graph in terms of the least eigenvalue of the graph. [Copyright &y& Elsevier]

Abstract: In this paper we characterize the unique graph whose least eigenvalue attains the minimum among all connected graphs of fixed order and given number of cut vertices, and then obtain a lower bound for the least eigenvalue of a connected graph in terms of the number of cut vertices. During the discussion we also get some results for the spectral radius of a connected bipartite graph and its upper bound. [Copyright &y& Elsevier]

In this article we follow the study of the hierarchical product of graphs, an operation recently introduced in the context of networks. A well-known example of such a product is the binomial tree which is the (hierarchical) power of the complete graph on two vertices. An appealing property of this structure is that all the eigenvalues are distinct. Here we show how to obtain a graph with this property by applying the hierarchical product. In particular, we propose a generalization of the binomial tree and study some of its main properties. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we focus on some operations of graphs and give a kind of eigenvalue interlacing in terms of the adjacency matrix, standard Laplacian, and normalized Laplacian. Also, we explore some applications of this interlacing. [Copyright &y& Elsevier]

Abstract: Let G be a weighted rooted graph of k levels such that, for [(1)] each vertex at level j is adjacent to one vertex at level and all edges joining a vertex at level j with a vertex at level have the same weight, where the weight is a positive real number; [(2)] if two vertices at level j are adjacent then they are adjacent to the same vertex at level and all edges joining two vertices at level j have the same weight; [(3)] two vertices at level j have the same degree; [(4)] there is not a vertex at level j adjacent to others two vertices at the same level; We give a complete characterization of the eigenvalues of the Laplacian matrix and adjacency matrix of G. They are the eigenvalues of leading principal submatrices of two nonnegative symmetric tridiagonal matrices of order and the roots of some polynomials related with the characteristic polynomial of the referred submatrices. By application of the above mentioned results, we derive an upper bound on the largest eigenvalue of a graph defined by a weighted tree and a weighted triangle attached, by one of its vertices, to a pendant vertex of the tree. [Copyright &y& Elsevier]

Abstract: In this note we study some properties of the spectrum of a connected graph G with four different eigenvalues, and (spectrally maximum) diameter three. When G is regular, this is the case, for instance, when G is a distance-regular graph. [Copyright &y& Elsevier]

We consider free bosons hopping on a network (infinite graph). The condition for Bose–Einstein condensation is given in terms of the random walk on a graph. In case of periodic lattices, we also consider boson moving in an external periodic potential and obatin the criterion for Bose–Einstein condensation. [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]

Something between an expository note and an extended research problem, this article is an invitation to expand the existing literature on a family of graph invariants rooted in linear and multilinear algebra. There are a variety of ways to assign a real n×n matrix K(G) to each n-vertex graph G, so that G and H are isomorphic if and only if K(G) and K(H) are permutation similar. It follows that G and H are isomorphic only if K(G) and K(H) are similar, i.e., that similarity invariants of K(G) are graph theoretic invariants of G, an observation that helps to explain the enormous literature on spectral graph theory. The focus of this article is the permutation part, i.e., on matrix functions that are preserved under permutation similarity if not under all similarity. [Copyright &y& Elsevier]

Given an alphabet Σ and a finite minimal set B of forbidden words, the authors in [1-11] deal with enumerating strings of a given length which do not contain any string in B as substring. The author together with Yang and Wen have recently given a polynomial time algorithm by modifying the power of adjacency matrix in graph theory in [10]. In this paper, we consider the case that B contains only one forbidden word. An important recursive relation between the number sequences Lk (the number of good words) and ε(k) (the number of bad words) is deduced and a more efficient algorithm is developed. The relation is more direct to the topic of counting and overlapping of the forbidden word, in the sense of combinatorics; We will also highlight the reason why chaotic or fractal properties showed in [11], from the view point of the recursive process between the two number sequences. [ABSTRACT FROM AUTHOR]

The eigenvalues of a graph are the eigenvalues of its adjacency matrix. This paper presents some upper and lower bounds on the greatest eigenvalue and a lower bound on the smallest eigenvalue. [Copyright &y& Elsevier]

Let G be a graph on n vertices and λ 1 , λ 2 , ... , λ n its eigenvalues. The Estrada index of G is an invariant that is calculated from the eigenvalues of the adjacency matrix of a graph. In this paper, we present some new lower bounds for the Estrada index of graphs and in particular of bipartite graphs that only depend on the number of vertices, the number of edges, Randić index, maximum and minimum degree and diameter. [ABSTRACT FROM AUTHOR]

Abstract: This note deals with the relationship between the total number of -walks in a graph, and the sum of the -th powers of its vertex degrees. In particular, it is shown that the the number of all -walks is upper bounded by the sum of the -th powers of the degrees. [Copyright &y& Elsevier]