Search

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]

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]