Search

It is shown that the nilpotency of submatrices of a certain class of adjacency matrices is equivalent to the Collatz conjecture. Our main result extends the previous work of Alves et al. and clarifies a conjecture made by Cardon and Tuckfield. [ABSTRACT FROM AUTHOR]

A graph is claw-free if it does not contain a star of order 4 as an induced subgraph. In this paper, we characterize all claw-free connected graphs with all but four eigenvalues equal to 0 or − 1. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new approach to study the spectral properties of Boolean graphs using the zeta and Möbius functions on the Boolean algebra B n of order 2 n. This approach yields new proofs of the previously known results about the reciprocal eigenvalue property of Boolean graphs. Further, this approach allows us to extend the results to a more general setting of the zero-divisor graphs Γ (P) of complement-closed and convex subposets P of B n. To do this, we consider the left linear representation of the incidence algebra of a poset P on the vector space of all real-valued functions V (P) on P. We then write down the adjacency operator A of the graph Γ (P) as the composition of two linear operators on V (P) , namely, the operator that multiplies elements of V (P) on the left by the zeta function ζ of P and the complementation operator. This allows us to obtain the determinant of A and the inverse of A in terms of the Möbius function μ of the complement-closed posets P. Additionally, if we impose convexity on the poset P , then we obtain the strong reciprocal or strong anti-reciprocal eigenvalue property of Γ (P) and also obtain the absolute palindromicity of the characteristic polynomial of A. This produces a large family of examples of graphs having the strong reciprocal or strong anti-reciprocal eigenvalue property. [ABSTRACT FROM AUTHOR]

The (k , r) -fan, denoted by F k , r , is the graph consisting of k copies of the complete graph K r which intersect in a single vertex. Desai et al. [7] proved that E X s p (n , F k , r) ⊆ E X (n , F k , r) for sufficiently large n , where E X s p (n , F k , r) and E X (n , F k , r) are the sets of n -vertex F k , r -free graphs with maximum spectral radius and maximum size, respectively. In this paper, the set E X s p (n , F k , r) is uniquely determined for n large enough. Let H s , t 1 , ... , t k be the graph consisting of s triangles and k odd cycles of lengths t 1 , ... , t k ≥ 5 intersecting in exactly one common vertex, denoted by H s , k for short. Li and Peng [12] showed that E X s p (n , H s , k) ⊆ E X (n , H s , k) for n large enough. In this paper, the set E X s p (n , H s , k) is uniquely characterized for sufficiently large n. [ABSTRACT FROM AUTHOR]

Let G be a finite simple graph with λ as an eigenvalue (i.e. an eigenvalue of the adjacency matrix of G), and let H be a star complement for λ in G. Motivated by a controllability condition, we say that H is a strong star complement for λ if G and H have no eigenvalue in common. We explore this concept in the context of line graphs, exceptional graphs, strongly regular graphs and graphs with a prescribed star complement. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix A (G) , and let τ (G) denote the smallest positive eigenvalue of A (G). Let G n be the class of all connected bipartite graphs on n = 2 k vertices with a unique perfect matching. In this article, we characterize the graphs G in G n such that τ (G) does not exceed 1 2. Using the above characterization, we obtain the unique graphs in G n with the maximum and the second maximum τ , respectively. Further, we prove that the largest and the second largest limit points of the smallest positive eigenvalues of bipartite graphs with a unique perfect matching are 1 2 and the reciprocal of α 3 1 2 + α 3 − 1 2 , respectively, where α 3 is the largest root of x 3 − x − 1. [ABSTRACT FROM AUTHOR]

A graph is called unimodular if its adjacency matrix has determinant ± 1. This article provides a necessary and sufficient condition for a simple connected graph with a unique perfect matching to be unimodular. In particular, we give a complete characterization of bicyclic unimodular graphs with a unique perfect matching. Moreover, the possible values of the determinant of the adjacency matrix of unicyclic, bicyclic, and tricyclic graphs with a unique perfect matching are also provided in this article. For non-bipartite unicyclic graphs with a unique perfect matching, we address the problem of when the inverse of the corresponding adjacency matrix is diagonally similar to a non-negative matrix. A pseudo-unimodular graph is a singular graph whose product of non-zero eigenvalues of the corresponding adjacency matrix is ± 1. We supply a necessary and sufficient condition for a singular graph to be pseudo-unimodular. [ABSTRACT FROM AUTHOR]

For a set of graphs F , a graph is said to be F -free if it does not contain any graph in F as a subgraph. Let Ex s p (n , F) denote the graphs with the maximum spectral radius among all F -free graphs of order n. A linear forest is a graph whose connected components are paths. Denote by L s the family of all linear forests with s edges. In this paper the graphs in Ex s p (n , { K k + 1 , L s }) will be completely characterized when n is appropriately large. [ABSTRACT FROM AUTHOR]

The spectral radius ρ (A) is the maximum absolute value of the eigenvalues of a matrix A. In this paper, we establish some relationship between the spectral radius of a symmetric matrix and its principal submatrices, i.e., if A is partitioned as a 2 × 2 block matrix A = ( 0 A 12 A 21 A 22 ) , then ρ (A) 2 ≤ ρ 2 2 + θ ⁎ , where θ ⁎ is the largest real root of the equation μ 2 = (x − ν) 2 (ρ 2 2 + x) and ρ 2 = ρ (A 22) , μ = ρ (A 12 A 22 A 21) , ν = ρ (A 12 A 21). Furthermore, the results are used to obtain several upper bounds of the spectral radius of graphs, which strengthen or improve some known results. [ABSTRACT FROM AUTHOR]

In this article we establish relationships between Leavitt path algebras, talented monoids and the adjacency matrices of the underlying graphs. We show that indeed the adjacency matrix generates in some sense the group action on the generators of the talented monoid. With the help of this, we deduce a form of the aperiodicity index of a graph via the talented monoid. We classify hereditary and saturated subsets via the adjacency matrix. This then translates to a correspondence between the composition series of the talented monoid and the so-called matrix composition series of the adjacency matrix. In addition, we discuss the number of cycles in a graph. In particular, we give an equivalent characterization of acyclic graphs via the adjacency matrix, the talented monoid and the Leavitt path algebra. Finally, we compute the number of linearly independent paths of certain length in the Leavitt path algebra via adjacency matrices. [ABSTRACT FROM AUTHOR]

The distance between an eigenvalue λ of a signed graph G ̇ and the spectrum of a signed graph H ̇ is defined as min { | λ − μ | : μ is an eigenvalue of H ̇ }. In this paper, we investigate this distance when H ̇ is a largest induced subgraph of G ̇ that does not have λ as an eigenvalue. We estimate the distance in terms of eigenvectors and structural parameters related to vertex degrees. For example, we show that | λ | | λ − μ | ≤ δ G ̇ ∖ H ̇ max { d H ̇ (i) d G ̇ − V (H ̇) (j) : i ∈ V (G ̇) ∖ V (H ̇) , j ∈ V (H ̇) , i ∼ j } , where δ G ̇ ∖ H ̇ is the minimum vertex degree in V (G ̇) ∖ V (H ̇). If H ̇ is obtained by deleting a single vertex i , this bound reduces to | λ | | λ − μ | ≤ d (i). We also consider the case in which λ is a simple eigenvalue and H ̇ is not necessarily a vertex-deleted subgraph, and the case when λ is the largest eigenvalue of an ordinary (unsigned) graph. Our results for signed graphs apply to ordinary graphs. They can be interesting in the context of eigenvalue distribution, eigenvalue location or spectral distances of (signed) graphs. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the adjacency matrices of finite undirected simple graphs over a finite prime field F p. We apply symmetric (row and column) elementary transformations to the adjacency matrix over F p in order to get a direct sum decomposition by other adjacency matrices. In this paper, we give a complete description of the direct sum decomposition of the adjacency matrix of any graph over F p for any odd prime p. Our key tool is quadratic residues of F p. [ABSTRACT FROM AUTHOR]

In this paper, we provide a characterization of fractional revival between twin vertices in a weighted graph with respect to its adjacency, Laplacian and signless Laplacian matrices. As an application, we characterize fractional revival between apexes of double cones. [ABSTRACT FROM AUTHOR]

A graph G is divisible by a graph H if the characteristic polynomial of G is divisible by that of H. In this paper, a necessary and sufficient condition for recursive graphs to be divisible by a path is used to show that the H-shape graph P 2 , 2 ; n − 4 2 , n − 7 , known to be (for n large enough) the minimizer of the spectral radius among the graphs of order n and diameter n − 5 , is determined by its adjacency spectrum if and only if n ≠ 10 , 13 , 15. [ABSTRACT FROM AUTHOR]

For a set of graphs F , let ex (n , F) and spex (n , F) denote the maximum number of edges and the maximum spectral radius of an n -vertex F -free graph, respectively. Nikiforov (LAA , 2007) gave the spectral version of the Turán Theorem by showing that spex (n , K k + 1) = λ (T k (n)) , where T k (n) is the k -partite Turán graph on n vertices. In the same year, Feng, Yu and Zhang (LAA) determined the exact value of spex (n , M s + 1) , where M s + 1 is a matching with s + 1 edges. Recently, Alon and Frankl (arXiv:2210.15076) gave the exact value of ex (n , { K k + 1 , M s + 1 }). In this article, we give the spectral version of the result of Alon and Frankl by determining the exact value of spex (n , { K k + 1 , M s + 1 }) when n is large. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a finite undirected graph of order n and of size m. Let Δ and δ be the largest and the smallest degree of G , respectively. The spectral radius of G is the largest eigenvalue of the adjacency matrix of the graph G. In this note we give new bounds on the spectral radius of { C 3 , C 4 } -free graphs in terms of m , n , Δ and δ. Computer search shows that in most of the cases the bounds derived in this note are better than the existing bounds. [ABSTRACT FROM AUTHOR]

Let G be a graph of size m and ρ (G) be the spectral radius of its adjacency matrix. A graph is said to be F -free if it does not contain a subgraph isomorphic to F. Let θ 1 , 2 , 3 denote the graph obtained from three internally disjoint paths with the same pair of endpoints, where the three paths are of lengths 1, 2, 3, respectively. Recently, Li, Sun and Wei showed that for any θ 1 , 2 , 3 -free graph G of size m ≥ 8 , ρ (G) ≤ 1 + 4 m − 3 2 , with equality if and only if G ≅ S m + 3 2 , 2 , where S m + 3 2 , 2 = K 2 ▿ K m − 1 2 ‾. However, this bound is not attainable when m is even. In this paper, we characterize the graphs with the maximum spectral radius over K 2 , r + 1 -free non-star graphs with m ≥ (4 r + 2) 2 + 1 , the graphs with the maximum spectral radius over θ 1 , 2 , 3 -free graphs with m ≥ 22 when m is even, and the graphs with the second largest spectral radius over θ 1 , 2 , 3 -free graphs with m ≥ 22 when m is odd. [ABSTRACT FROM AUTHOR]

We characterize the simple connected graphs with the second largest eigenvalue less than 1/2, which consists of 13 classes of specific graphs. These 13 classes hint that c 2 ∈ [ 1 / 2 , 2 + 5 ] , where c 2 is the minimum real number c for which every real number greater than c is a limit point in the set of the second largest eigenvalues of the simple connected graphs. We leave it as a problem. [ABSTRACT FROM AUTHOR]

In this paper, we characterize all graphs with eigenvectors of the signless Laplacian and adjacency matrices with components equal to { − 1 , 0 , 1 }. We extend the graph parameter max k -cut to square matrices and prove a general sharp upper bound, which implies upper bounds on the max k -cut of a graph using the smallest signless Laplacian eigenvalue, the smallest adjacency eigenvalue, and the largest Laplacian eigenvalue of the graph. In addition, we construct infinite families of extremal graphs for the obtained upper bounds. [ABSTRACT FROM AUTHOR]

In this article, we consider the trees for which the adjacency matrix has nullity at most one. We study the smallest positive (adjacency) eigenvalue of these trees. For such trees lower bounds on the smallest positive eigenvalue have already been obtained in literature but the problem of finding an upper bound still remains unsolved. In this article, we find upper bounds on the smallest positive eigenvalue of these trees and obtain corresponding unique maximal trees. Additionally, we study the smallest positive eigenvalue of trees obtained by attaching a pendant at some vertex of a path graph and also identify the trees for the extremal cases. As applications of our earlier results, we show that, for a path of odd order, the smallest positive eigenvalue is maximum, if we add the pendant almost in the middle. As another application, we show that for a path of any order, the smallest positive eigenvalue is minimum, if we add the pendant vertex at the end. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n with domination number γ (G). Wang, Yan, Fang, Geng and Tian [Linear Algebra Appl. 607 (2020), 307-318] showed that for any Laplacian eigenvalue λ of G with multiplicity m G (λ) , it holds that γ (G) ≤ n − m G (λ). Using techniques from the theory of star sets, in this work we prove that the same bound holds when λ is an arbitrary adjacency eigenvalue of a non-regular graph, and we characterize the cases of equality. Moreover, we show a result that gives a relationship between start sets and the p -domination number, and we apply it to extend the aforementioned spectral bound to the p -domination number using the adjacency and Laplacian eigenvalue multiplicities. [ABSTRACT FROM AUTHOR]

In this article, we consider the generalization of the Laplacian matrix for hypergraphs to obtain several results related to spectral properties of hypergraphs. This generalization of Laplacian matrix was defined in 2021 by Anirban Banerjee. We first supply a necessary and sufficient condition on the Laplacian spectral radius of hypergraphs such that the complement of that hypergraph is connected. We give bounds for the Laplacian spectral radius of k -uniform hypergraphs in terms of some invariants of hypergraph, such as the maximum degree, minimum degree, first Zagreb index, and the chromatic number. As an application of these results, some upper bounds of the Nordhaus-Gaddum type are obtained for the sum of Laplacian spectral radius of a k -uniform hypegraphs and its complement, and product of Laplacian spectral radius of a k -uniform hypegraphs and its complement. It is known that the second largest Laplacian eigenvalue for graphs is greater or equal to the second highest degree of graphs. We show by an example that this result is not true for 3-uniform hypergraphs in general. Finally, we supply a class of 3-uniform hypergraphs for which the second largest Laplacian eigenvalue is greater or equal to the second highest degree. [ABSTRACT FROM AUTHOR]

Let D be a strongly connected digraph and α ∈ [ 0 , 1 ]. In Liu et al. (2019) [13] the matrix A α (D) = α D e g (D) + (1 − α) A (D) , where A (D) and D e g (D) are the adjacency matrix and the diagonal matrix of the out-degrees of D , respectively, was defined. In this paper it is established some sharp bounds on the A α (D) -spectral radius in terms of some parameters such as the out-degrees, the maximum out-degree, the second maximum out-degree, the number of vertices, the number of arcs, the average 2-outdegrees of the vertices of D and the parameter α of A α (D). The extremal digraphs attaining these bounds are characterized. It is shown that the bounds obtained improve, in some cases, some of recently given bounds presented in the literature. [ABSTRACT FROM AUTHOR]

Let G ˙ be an unbalanced signed graph. In this paper, we establish that e (G ˙) ⩽ 1 2 (n 2 − n) − (n − 3) and ρ (G ˙) ⩽ n − 2 if G ˙ does not contain unbalanced K 4 as a signed subgraph. Moreover, comprehensive characterizations of the extremal signed graphs have been obtained. • The situation that the index of signed graph equals to the spectral radius of underlying graph has been characterized. • We determine the Turán number of K 4 − in unbalanced signed graph, and we characterize all the extremal signed graphs. • We solve the spectral Turán problem among all K 4 − -free unbalanced signed graphs. [ABSTRACT FROM AUTHOR]

• A novel dynamic graph attention network is proposed for EEG emotion recognition. • The high accuracy can be obtained from the DGAT model in EEG emotion recognition. • The channel connectivity can reflect the synergistic relationships within the brain. Deep learning classification models based on electroencephalogram (EEG) emotion recognition have demonstrated considerable proficiency in the categorization of emotional states. However, these models have limitations in their capability to analyze the active states and cooperative relationships among distinct brain regions. This study proposes a dynamic graph attention network (DGAT) for EEG emotion recognition, which learns the features of each channel and leverages multiple-head self-attention mechanisms to capture non-Euclidean relationships between channels. Then, we use differential entropy features of emotions signals on the SJTU emotion EEG dataset (SEED). The DGAT model achieved improved subject-dependent and cross-subject classification accuracy compared to previous models. Moreover, ablation studies show that the channel weight matrix(CWM) and appropriate hyper-parameters can improve the performance of the DGAT model significantly. Furthermore, by conducting interpretable analysis of the new connections and electrode weights learned by the model, we find that these connection weight relationships reflect a certain degree of coordination within the brain for EEG-based emotion recognition. These findings provide a new method for EEG emotion recognition and highlights the potential for using deep learning models to analyze the active state and synergistic relationships among brain regions. [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 S n , 2 be the graph obtained by joining each vertex of K 2 to n − 2 isolated vertices, and let S n , 2 − be the graph obtained from S n , 2 by deleting an edge incident to a vertex of degree two. Recently, Zhai, Lin and Shu [20] showed that ρ (G) ≤ 1 + 4 m − 3 2 for any C 5 -free graph of size m ≥ 8 or C 6 -free graph of size m ≥ 22 , with equality if and only if G ≅ S m + 3 2 , 2 (possibly, with some isolated vertices). However, this bound is sharp only for odd m. Motivated by this, we want to obtain a sharp upper bound of ρ (G) for C 5 -free or C 6 -free graphs with m edges. In this paper, we prove that if G is a C 5 -free graph of even size m ≥ 14 or C 6 -free graph of even size m ≥ 74 , and G contains no isolated vertices, then ρ (G) ≤ ρ ˜ (m) , with equality if and only if G ≅ S m + 4 2 , 2 − , where ρ ˜ (m) is the largest root of x 4 − m x 2 − (m − 2) x + (m 2 − 1) = 0. [ABSTRACT FROM AUTHOR]

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]

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]

A gain graph over a group G , also referred to as G -gain graph, is a graph where an element of a group G , called gain, is assigned to each oriented edge, in such a way that the inverse element is associated with the opposite orientation. Gain graphs can be regarded as a generalization of signed graphs, among others. In this work, we show a new switching method to construct cospectral gain graphs. Some previous methods known for graph cospectrality follow as a corollary of our results. [ABSTRACT FROM AUTHOR]

In 1973 Schwenk [7] proved that almost every tree has a cospectral mate. Inspired by Schwenk's result, in this paper we study the spectrum of two families of trees. The p -sun of order 2 p + 1 is a star K 1 , p with an edge attached to each pendant vertex, which we show to be determined by its spectrum among connected graphs. The (p , q) -double sun of order 2 (p + q + 1) is the union of a p -sun and a q -sun by adding an edge between their central vertices. We determine when the (p , q) -double sun has a cospectral mate and when it is determined by its spectrum among connected graphs. Our method is based on the fact that these trees have few distinct eigenvalues and we are able to take advantage of their nullity to shorten the list of candidates. [ABSTRACT FROM AUTHOR]

A quaternion unit gain graph is a graph where each orientation of an edge is given a quaternion unit, which is the inverse of the quaternion unit assigned to the opposite orientation. In this paper we define the adjacency, Laplacian and incidence matrices for a quaternion unit gain graph and study their properties. These properties generalize several fundamental results from spectral graph theory of ordinary graphs, signed graphs and complex unit gain graphs. Bounds for both the left and right eigenvalues of the adjacency and Laplacian matrix are developed, and the right eigenvalues for the cycle and path graphs are explicitly calculated. [ABSTRACT FROM AUTHOR]

A graph G is F -free, if it contains no F as a subgraph. A Brualdi-Solheid-Turán type problem asks what is the maximum spectral radius of an F -free graph of order n ? Let K a , b • K 3 denote the graph obtained by identifying a vertex of K a , b belonging to the part of size b and a vertex of K 3. In this paper, we consider about a Brualdi-Solheid-Turán type problem on non-bipartite graphs. We prove that if G is a non-bipartite graph with order n ≥ 21 and ρ (G) ≥ ρ (K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3) , then G contains a pentagon unless G ≅ K ⌈ n − 2 2 ⌉ , ⌊ n − 2 2 ⌋ • K 3. [ABSTRACT FROM AUTHOR]

First we investigate net-biregular signed graphs with spectrum of the form [ ρ , μ m , λ l ] where λ is non-main; such graphs are necessarily biregular with exactly two main eigenvalues. We provide two constructions of signed graphs with three eigenvalues, where the graphs that arise include net-biregular and net-regular signed graphs having spectrum [ ρ , μ , λ l ] , with λ non-main. Secondly we determine all the connected signed graphs with spectrum [ ρ , μ 2 , λ l ] (l ≥ 2) where λ is non-main: these include a new infinite family of signed graphs which are neither net-regular nor net-biregular. Thus, in contrast to the situation for graphs, a signed graph with two main eigenvalues and one non-main eigenvalue is not necessarily net-biregular. [ABSTRACT FROM AUTHOR]

A blow-up of a graph G , is obtained from G by replacing each vertex v i of G with an independent set V i of n i vertices and joining each vertex in V i with each vertex in V j provided v i v j ∈ E (G). Let M n (G) be the set of all the blow-ups of G such that each n i ≥ 1 and ∑ i = 1 | G | n i = n. Monsalve and Rada (2021) [9] proposed three conjectures on the extremal spectral radii of M n (P k) and M n (C k). In this paper, we confirm the first two conjectures and construct an infinite class of graphs to illustrate the third conjecture is not true. [ABSTRACT FROM AUTHOR]

In 1986, Herbert Wilf asked what kind of graphs have an eigenvector with entries formed only by ±1. In this paper, we answer this question for the adjacency, Laplacian, and signless Laplacian matrices of a graph. To this end, we generalize the concept of an exact graph to the adjacency and signless Laplacian matrices. Infinite families of exact graphs for all those matrices are presented. [ABSTRACT FROM AUTHOR]

In this paper we describe two methods, both inspired from Godsil-McKay switching on simple graphs, to build cospectral gain graphs whose gain group consists of the complex numbers of modulus 1 (the circle group). The results obtained here can be also applied to the Hermitian matrix of mixed graphs. [ABSTRACT FROM AUTHOR]

Accurate traffic flow forecasting is an important technical measure to alleviate traffic congestion. Since traffic flow has spatial and temporal characteristics, thus the adequate extraction of its spatio-temporal features is an important prerequisite to promote the forecast accuracy of the model. However, a majority of existing traffic flow prediction models cannot sufficiently consider the neighborhood spatio-temporal relationship for the real road network in the modeling process, which makes it difficult to improve the model prediction accuracy. For this reason, this paper takes improved feature enhancement graph convolution (FEGC), gated recurrent unit (GRU), and improved lightweight particle swarm optimization (ILPSO) algorithm as components, respectively, to construct a combinatorial traffic flow prediction model FEGC-GRU-ILPSO (FGI), aiming to achieve accurate forecast for regional traffic flow through fully learning spatio-temporal correlation characteristics. Firstly, considering that most traffic flow modeling methods are ineffective in characterizing the hidden association information within nodes, we propose the method of constructing the virtual space adjacency matrix based on the improved gray relational analysis (IGRA) algorithm, which achieves the effective characterization of road network neighborhood relationship by fusing it with the original adjacency matrix. Then, based on the idea of matrix decomposition, the weight adjacency matrix is further introduced to realize the dynamic capture of time-varying correlation of node graph structure in realistic road networks. Secondly, to address the performance degradation problem caused by feature assimilation in multi-layer graph convolution, an improved feature enhancement graph convolution component is proposed to alleviate the multi-layer graph convolution over-smoothing by enhancing salient features. Finally, considering the convex optimization problem caused by the way the hyperparameters of the model are determined through subjective experience, we propose the ILPSO algorithm to improve the overall prediction performance in an adaptive optimizing method. In this paper, real-world data acquired by the Caltrans Performance Measurement System (PeMS) is used as the object of study. The experimental results demonstrate that the FGI model has better prediction performance than the current mainstream baseline models. • An adaptive weighted adjacency matrix is proposed to learn road network features. • A feature enhancement graph convolution is proposed to reinforce important features. • An improved particle swarm algorithm is proposed to optimize the model parameters. • The feature capture process of feature enhancement graph convolution is visualized. • The proposed model has superior prediction accuracy than the baseline models. [ABSTRACT FROM AUTHOR]

We consider linear ternary codes generated by A + β I , where A is the adjacency matrix of a strongly regular signed graph, I is the identity matrix and β ∈ F 3. Our results include theoretical examinations on dimension and distance, and the interplay between the codes. We also compute many structural parameters of codes for some infinite families of strongly regular signed graphs and establish more than 60 particular codes of comparatively small dimension. It occurs that some known linear ternary codes are covered by this approach. [ABSTRACT FROM AUTHOR]

Let G be an arbitrary group. We define a gain-line graph for a gain graph (Γ , ψ) through the choice of an incidence G -phase matrix inducing ψ. We prove that the switching equivalence class of the gain function on the line graph L (Γ) does not change if one chooses a different G -phase inducing ψ or a different representative of the switching equivalence class of ψ. In this way, we generalize to any group some results proven by N. Reff in the abelian case. The investigation of the orbits of some natural actions of G on the set H Γ of G -phases of Γ allows us to characterize gain functions on Γ, gain functions on L (Γ) , their switching equivalence classes and their balance property. The use of group algebra valued matrices plays a fundamental role and, together with the matrix Fourier transform, allows us to represent a gain graph with Hermitian matrices and to perform spectral computations. Our spectral results also provide some necessary conditions for a gain graph to be a gain-line graph. [ABSTRACT FROM AUTHOR]

A T -gain graph, Φ = (G , φ) , is a graph in which the function φ assigns a unit complex number to each orientation of an edge of G , and its inverse is assigned to the opposite orientation. The associated adjacency matrix A (Φ) is defined canonically. The energy E (Φ) of a T -gain graph Φ is the sum of the absolute values of all eigenvalues of A (Φ). We study the notion of energy of a vertex of a T -gain graph, and establish bounds for it. For any T -gain graph Φ, we prove that 2 τ (G) − 2 c (G) ≤ E (Φ) ≤ 2 τ (G) Δ (G) , where τ (G) , c (G) and Δ (G) are the vertex cover number, the number of odd cycles and the largest vertex degree of G , respectively. Furthermore, using the properties of vertex energy, we characterize the class of T -gain graphs for which E (Φ) = 2 τ (G) − 2 c (G) holds. Also, we characterize the T -gain graphs for which E (Φ) = 2 τ (G) Δ (G) holds. This characterization solves a general version of an open problem. In addition, we establish bounds for the energy in terms of the spectral radius of the associated adjacency matrix. [ABSTRACT FROM AUTHOR]

Let A n be the connected anti-regular graph of order n. It was conjectured that among all threshold graphs on n vertices, A n has the smallest positive eigenvalue and the largest eigenvalue less than −1. Recently, in [1] was given partial results for this conjecture and identified the critical cases where a more refined method is needed. In this paper, we deal with these cases and confirm that conjecture holds. [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 eccentricity matrix of a connected graph G is obtained from the distance matrix of G by retaining the largest distances in each row and each column, and setting the remaining entries as 0. In this article, a conjecture about the least eigenvalue of eccentricity matrices of trees, presented in the article (Wang et al., 2018), is solved affirmatively. In addition to this, the spectra and the inertia of eccentricity matrices of various classes of graphs are investigated. [ABSTRACT FROM AUTHOR]

A graph is called integral if all the eigenvalues of its adjacency matrix are integers. In this paper, we show that a cograph that has a balanced cotree T G (a 1 , ... , a r − 1 , 0 | 0 , ... , 0 , a r) is integral. We present closed formulas for its eigenvalues. As application, we use the integral cographs to estimate the eigenvalues of any cograph. [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]

It is a well-known fact that a graph of diameter d has at least d + 1 eigenvalues. A graph is d -extremal, if it has diameter d and exactly d + 1 eigenvalues. A graph is split if its vertex set can be partitioned into a clique and a stable set. Such graphs have diameter at most 3. We obtain a complete classification of the connected bidegreed 3-extremal split graphs using the association of split graphs with combinatorial designs. We also construct certain families of non-bidegreed 3-extremal split graphs. [ABSTRACT FROM AUTHOR]

A spectral version of extremal graph theory problem is as follows: what is the maximum spectral radius of an H -free graph of order n ? Nikiforov posed a conjecture on spectral extremal value of cycles. In the past decade, much attention has been paid to this conjecture and other questions on spectral extremal graphs. In order to approach to Nikiforov's conjecture, we provide a new conjecture on spectral extremal value involving fans and wheels. Moreover, we show it is true for k = 2. [ABSTRACT FROM AUTHOR]