Search

This work generalizes the recently introduced bubble entropy (BE) algorithm for univariate time series to graph and network analysis. In this paper, we introduce a modified method, called bubble entropy for graph signals (BEG), as an invaluable tool for detecting the irregularity of signals defined on graphs. Our algorithm is based on using the adjacency matrix to combine the signal values with the topology of the graph. Experiments on both synthetic and real data demonstrate the availability of the proposed measures in detecting the irregularity of graph signals and identifying topological changes in graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with the adjacency matrix $ A(G) $ A (G). Let $ \tau (G) $ τ (G) denote the smallest positive eigenvalue of $ A(G) $ A (G). In 1990, Pavlíková and Kr $ \breve{c} $ c ˘ -Jediný proved that among all nonsingular trees on n = 2m vertices, the comb graph (obtained by taking a path on m vertices and adding a new pendant vertex to every vertex of the path) has the maximum τ value. We consider the problem for unicyclic graphs. Let $ \mathscr {U} $ U denote the class of all connected bipartite unicyclic graphs with a unique perfect matching, and for each $ m\geq ~3 $ m ≥ 3 , let $ \mathscr {U}_n $ U n be the subclass of $ \mathscr {U} $ U with graphs on n = 2m vertices. We first obtain the classes of unicyclic graphs U in $ \mathscr {U} $ U such that $ \tau (U)\leq \sqrt {2}-1 $ τ (U) ≤ 2 − 1. We then find the unique graph $ U_o^n $ U o n (resp. $ U_e^n $ U e n ) having the maximum τ value among all graphs in $ \mathscr {U}_n $ U n when m is odd (resp. when m is even). Finally, we prove that $ U_o^6 $ U o 6 (the graph obtained from a cycle of order 4, by adding two pendants to two adjacent vertices) is the graph with maximum τ value among all graphs in $ \mathscr {U} $ U . As a consequence, we obtain a sharp upper bound for $ \tau (U) $ τ (U) when $ U\in \mathscr {U} $ U ∈ U . [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]

The comaximal graph Γ (R) of a commutative ring R is a simple graph with vertex set R and two distinct vertices u and v of Γ (R) are adjacent if and only if u R + v R = R. In this paper, we find the sharp bounds for the Sombor index for comaximal graphs of integer modulo ring ℤ n and give the corresponding extremal graphs. Also, we find the Sombor eigenvalues and the bounds for the Sombor energy of comaximal graphs of ℤ 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]

This paper established the idea of minimum evdominating matrix of semigraph and calculated its energy. The minimum ev-dominating energy EmeD(G) of a semigraph G is the sum of the absolute values of the eigenvalues of the minimum ev-dominating matrix. Here some results are also derived in connection with the energy of minimum evdominating matrix. Some lower bounds are also established. [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]

Let (G, w) be a weighted graph with the adjacency matrix A. The group inverse of (G, w), denoted by (G # , w #) is the weighted graph with the weight w # (v i v j) of an edge v i v j in G # is defined as the ijth entry of A # , the group inverse of A. We study the group inverse of singular weighted trees. It is shown that if (T, w) is a singular weighted tree, then (T # , w #) is again a weighted tree if and only if (T, w) is a star tree, which in turn holds if and only if (T # , w #) is graph isomorphic to (T, w). A new class T w of weighted trees is introduced and studied here. It is shown that the group inverse of the adjacency matrix of a positively weighted tree in T w is signature similar to a non-negative matrix. [ABSTRACT FROM AUTHOR]

Let A(G) be the adjacency matrix of a simple connected undirected graph G. A graph G of order n is said to be non-singular (respectively singular) if A(G) is non-singular (respectively singular). The spectrum of a graph G is the set of all its eigenvalues denoted by spec(G). The antireciprocal (respectively reciprocal) eigenvalue property for a graph G can be defined as "Let G be a non-singular graph G if the negative reciprocal (respectively positive reciprocal) of each eigenvalue is likewise an eigenvalue of G, then G has anti-reciprocal (respectively reciprocal) eigenvalue property." Furthermore, a graph G is said to have strong anti-reciprocal eigenvalue property (resp. strong reciprocal eigenvalue property) if the eigenvalues and their negative (resp. positive) reciprocals are of same multiplicities. In this article, graphs satisfying anti-reciprocal eigenvalue (or property (-R)) and strong anti-reciprocal eigenvalue property (or property (-SR)) are discussed. [ABSTRACT FROM AUTHOR]

Emotion is one of the most important higher cognitive functions of the human brain and plays an important role in transaction processing and decisions. In traditional emotion recognition studies, the frequency band features in EEG signals have been shown to have a high correlation with emotion production. However, traditional emotion recognition methods cannot satisfactorily solve the problem of individual differences in subjects and data heterogeneity in EEG, and subject-independent emotion recognition based on EEG signals has attracted extensive attention from researchers. In this paper, we propose a subject-independent emotion recognition model based on adaptive extraction of layer structure based on frequency bands (BFE-Net), which is adaptive in extracting EEG map features through the multi-graphic layer construction module to obtain a frequency band-based multi-graphic layer emotion representation. To evaluate the performance of the model in subject-independent emotion recognition studies, extensive experiments are conducted on two public datasets including SEED and SEED-IV. The experimental results show that in most experimental settings, our model has a more advanced performance than the existing studies of the same type. In addition, the visualization of brain connectivity patterns reveals that some of the findings are consistent with previous neuroscientific validations, further validating the model in subject-independent emotion recognition studies. [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]

Let G be a graph, and let $ A(G) $ A (G) be the adjacency matrix of G. The computation of permanent of $ A(G) $ A (G) is #p-complete. Computing permanent of $ A(G) $ A (G) is of great interest in quantum chemistry, statistical physics, among other disciplines. In this paper, we characterize the ordering of permanents of adjacency matrices of all graphs obtained from regular complete bipartite graph $ K_{p, p} $ K p , p by deleting six edges. As an application, we show that all graphs with a perfect matching obtained from $ K_{p, p} $ K p , p with six edges deleted are determined by their permanental polynomials. [ABSTRACT FROM AUTHOR]

In this article, we discuss the spectral properties of the general extended adjacency matrix for chain graphs. In particular, we discuss the eigenvalues of the general extended adjacency matrix of the chain graphs and obtain its general extended adjacency inertia. We obtain bounds for the largest and the smallest general extended adjacency eigenvalues and characterize the extremal graphs. We also obtain a lower bound for the spread of the general extended adjacency matrix. We characterize chain graphs with all the general extended adjacency eigenvalues being simple and chain graphs that are non-singular under the general extended adjacency matrix. Further, we determine the explicit formula for the determinant and the trace of the square of the general extended adjacency matrix of chain graphs. Finally, we discuss the energy of the general extended adjacency matrix and obtain some bounds for it. We characterize the extremal chain graphs attaining these bounds. [ABSTRACT FROM AUTHOR]

Epilepsy is a chronic brain disease, and identifying seizures based on electroencephalogram (EEG) signals would be conducive to implement interventions to help patients reduce impairment and improve quality of life. In this paper, we propose a classification algorithm to apply dynamical graph neural network with attention mechanism to single channel EEG signals. Empirical mode decomposition (EMD) are adopted to construct graphs and the optimal adjacency matrix is obtained by model optimization. A multilayer dynamic graph neural network with attention mechanism is proposed to learn more discriminative graph features. The MLP-pooling structure is proposed to fuse graph features. We performed 12 classification tasks on the epileptic EEG database of the University of Bonn, and experimental results showed that using 25 runs of ten-fold cross-validation produced the best classification results with an average of 99.83 % accuracy, 99.91 % specificity, 99.78 % sensitivity, 99.87 % precision, and 99.47 % F 1 score for the 12 classification tasks. [ABSTRACT FROM AUTHOR]

For a simple graph G , the generalized adjacency matrix A α (G) is defined as A α (G) = α D (G) + (1 − α) A (G) , α ∈ [ 0 , 1 ] , where A (G) is the adjacency matrix and D (G) is the diagonal matrix of vertex degrees of G. This matrix generalizes the spectral theories of the adjacency matrix and the signless Laplacian matrix of G. In this paper, we find the A α -spectrum of the joined union of graphs in terms of the spectrum of the adjacency matrices of its components and the zeros of the characteristic polynomials of an auxiliary matrix determined by the joined union. We determine the A α -spectrum of join of two regular graphs, the join of a regular graph with the union of two regular graphs of distinct degrees. As applications, we investigate the A α -spectrum of certain power graphs of finite groups. [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]

The paper proposes a deep learning model based on Chebyshev Network Gated Recurrent Units, which is called Spectral Graph Convolution Recurrent Neural Network, for multichannel electroencephalogram emotion recognition. First, in this paper, an adjacency matrix capturing the local relationships among electroencephalogram channels is established based on the cosine similarity of the spatial locations of electroencephalogram electrodes. The training efficiency is improved by utilizing the computational speed of the cosine distance. This advantage enables our method to have the potential for real-time emotion recognition, allowing for fast and accurate emotion classification in real-time application scenarios. Secondly, the spatial and temporal dependence of the Spectral Graph Convolution Recurrent Neural Network for capturing electroencephalogram sequences is established based on the characteristics of the Chebyshev network and Gated Recurrent Units to extract the spatial and temporal features of electroencephalogram sequences. The proposed model was tested on the publicly accessible dataset DEAP. Its average recognition accuracy is 88%, 89.5%, and 89.7% for valence, arousal, and dominance, respectively. The experiment results demonstrated that the Spectral Graph Convolution Recurrent Neural Network method performed better than current models for electroencephalogram emotion identification. This model has broad applicability and holds potential for use in real-time emotion recognition scenarios. [ABSTRACT FROM AUTHOR]

We introduce a graph attached to mutually orthogonal Sudoku Latin squares. The spectra of the graphs obtained from finite fields are explicitly determined. As a corollary, we then use the eigenvalues to distinguish non-isomorphic Sudoku Latin squares. [ABSTRACT FROM AUTHOR]

We consider particular weighted directed graphs with edges having colour red, blue or green such that each red edge has weight 1, each blue edge has weight $ -1 $ − 1 and each green edge has weight $ \mathrm {i} $ i (the imaginary unit). Such a directed graph is called a 3-coloured digraph (for short, a 3-CD). Every mixed graph and every signed graph can be interpreted as a 3-CD. We first study some structural properties of 3-CDs by means of the eigenvalues of the adjacency matrix. In particular, we give spectral criteria for singularity of such digraphs. Second, we consider weight-symmetric 3-CDs, i.e. those 3-CDs that are switching isomorphic to their negation. It follows that the class of weight-symmetric 3-CDs is included in the class of 3-CDs whose spectrum is symmetric (with respect to the origin). We give some basic properties and several constructions of weight-symmetric 3-CDs and establish constructions of 3-CDs which have symmetric spectrum but are not weight-symmetric. [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]

Currently, there are two main limitations in single-label text classification tasks based on hierarchical graph attention networks. First, it cannot effectively extract text features. Second, there are few studies that highlight text features through the connection between text and labels. To address these two issues, a hierarchical graph attention network text classification model that integrates label information is proposed. The model constructs an adjacency matrix based on the relevance between sentence keywords and topics, and then uses word-level graph attention network to obtain vector representations of sentences. This method is based on randomly initialized target vectors and utilizes maximum pooling to extract specific target vectors for sentences, making the obtained sentence vectors have more obvious category features. After the word-level graph attention layer, a sentence-level graph attention network is used to obtain new text representations with word weight information, and pooling layers are used to obtain feature information for the text. On the other hand, GloVe pre-trained word vectors are used to initialize vector representations for all text labels, which are then interacted and fused with the feature information of the text to reduce the loss of original features, obtaining feature representations that are distinct from different texts. Experimental results on five public datasets (R52, R8, 20NG, Ohsumed, and MR) show that the classification accuracy of the model significantly exceeds other mainstream baseline models. [ABSTRACT FROM AUTHOR]

In this paper, we prove that every simple connected graph with α > n 2 has 1 as a normalized Laplacian eigenvalue with multiplicity at least 2 α − n , where n and α are the order and the independence number of the graph, respectively. Then we investigate graphs with α ≤ n 2 and having or not having 1 as a normalized Laplacian eigenvalue. [ABSTRACT FROM AUTHOR]

For a simple graph G, the ABC-index is a degree based topological index and is defined as where dv is the degree of the vertex υ in G. Recently, the Laplacian ABC-matrix was introduced in [22] is defined by where is the diagonal matrix of ABC-degrees and Ã(G) is the ABC-matrix of G: The eigenvalues of the matrix are called the Laplacian ABC-eigenvalues of G. In the article, we consider the problem of characterization of connected graphs having exactly three distinct Laplacian ABC-eigenvalues. We solve this problem for bipartite graphs, multipartite graphs, unicyclic graphs, regular graphs and prove the non-existence of such graphs with diameter greater than 2. We introduce the concept of trace norm of the matrix called the Laplacian ABC-energy of G. We obtain some upper and lower bounds for the Laplacian ABC-energy and characterize the extremal graphs which attain these bounds. [ABSTRACT FROM AUTHOR]

Entropy is widely applied to graph theory and complex networks as a powerful tool for measuring uncertainty in a complex system. Due to the fact that traditional probability distribution entropy cannot effectively characterize the global topology information of complex networks, some entropy measures constructed by the adjacency matrix A come into being, such as information-theoretic entropy EE and communicability sequence entropy. Despite substantial efforts to explore the properties of these measures, there remain some imperfections. For instance, the adjacency matrix only reflects the dependence between direct neighbors. Therefore, in this paper, we propose the r -power adjacency matrix entropy ( AME r ) to measure the indirect relationship between nodes in a network. And then, we compare the abilities of AME r , EE, and CSE in capturing the network global topology changes. Furthermore, we establish the Jenson–Shannon divergence based on AME r to quantify the structural dissimilarities of the networks. Finally, we apply the proposed methods to analyze the urban economic connection networks. The results demonstrate the availability of the proposed measures in identifying network topology changes and quantifying network structure differences. [ABSTRACT FROM AUTHOR]

Let Rn be a finite reduced ring with n maximal ideals 픪i and let Γ(Rn) be the zero-divisor graph associated to Rn. The class of rings Rn contains the Boolean rings as a subclass. When Rn/픪i = 픽 for all i where 픽 is a finite field, we associate two (n − 1) × (n − 1) sized matrices P and Q to the graph Γ(Rn) having combinatorial entries and use these matrices to determine the spectrum of this graph. More precisely, we show that every eigenvalue of P and of − Q is an eigenvalue of Γ(Rn). To do this, we give a recursive description of the adjacency matrix of this graph and also exhibit its equitable partition. This is used in computing the determinant, rank and nullity of the adjacency matrix. Further, we propose that the eigenvalues of P, − Q and the eigenvalue 0 exhaust all the eigenvalues of Γ(Rn). [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]

Given that fingerprint localization methods can be effectively modeled as supervised learning problems, machine learning has been employed for indoor localization tasks based on fingerprint methods. However, it is often challenging for popular machine learning models to effectively capture the unstructured data features inherent in fingerprint data that are generated in diverse propagation environments. In this paper, we propose an indoor localization algorithm based on a high-order graph neural network (HoGNNLoc) to enhance the accuracy of indoor localization and improve localization stability in dynamic environments. The algorithm first designs an adjacency matrix based on the spatial relative locations of access points (APs) to obtain a graph structure; on this basis, a high-order graph neural network is constructed to extract and aggregate the features; finally, the designed fully connected network is used to achieve the regression prediction of the location of the target to be located. The experimental results on our self-built dataset show that the proposed algorithm achieves localization accuracy within 1.29 m at 80% of the cumulative distribution function (CDF) points. The improvements are 59.2%, 51.3%, 36.1%, and 22.7% compared to the K-nearest neighbors (KNN), deep neural network (DNN), simple graph convolutional network (SGC), and graph attention network (GAT). Moreover, even with a 30% reduction in fingerprint data, the proposed algorithm exhibits stable localization performance. On a public dataset, our proposed localization algorithm can also show better performance. [ABSTRACT FROM AUTHOR]

In this paper, first we introduce the notions of size, order, and degree of vertices and edges in a soft graph, and we give some examples for a better understanding of these concepts. Then, we define the fundamental concepts of the adjacency matrix of soft graphs, complement of soft graphs, and regularity based on the degree of vertices of soft graphs, and we investigate some related results. Moreover, we introduce the concept of soft multiset and soft multigraph and define the notions of union, intersection, complement, and sum, and then we investigate the relations among them. Finally, we give an application of soft graphs in controlling urban traffic flows. [ABSTRACT FROM AUTHOR]

There is a type of distance-regular graph, said to be Q-polynomial. In this paper, we investigate a generalized Q-polynomial property involving a graph that is not necessarily distance-regular. We give a detailed description of an example associated with the projective geometry L N (q) . [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 n , β be the set of graphs of order n with given matching number β. Let D (G) be the diagonal matrix of the degrees of the graph G and A (G) be the adjacency matrix of the graph G. The largest eigenvalue of the nonnegative matrix A α (G) = α D (G) + A (G) is called the α-spectral radius of G. The graphs with maximal α-spectral radius in G n , β are completely characterized in this paper. In this way, we provide a general framework to attack the problem of extremal spectral radius in G n , β . More precisely, we generalize the known results on the maximal adjacency spectral radius in G n , β and the signless Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

We formalize the notion of a sedentary vertex and present a relaxation of the concept of a sedentary family of graphs introduced by Godsil (Linear Algebra Appl 614:356–375, 2021. https://doi.org/10.1016/j.laa.2020.08.027). We provide sufficient conditions for a given vertex in a graph to exhibit sedentariness. We also show that a vertex with at least two twins (vertices that share the same neighbours) is sedentary. We prove that there are infinitely many graphs containing strongly cospectral vertices that are sedentary, which reveals that, even though strong cospectrality is a necessary condition for pretty good state transfer, there are strongly cospectral vertices which resist high probability state transfer to other vertices. Moreover, we derive results about sedentariness in products of graphs which allow us to construct new sedentary families, such as Cartesian powers of complete graphs and stars. [ABSTRACT FROM AUTHOR]

For a d -regular graph G , an edge-signing σ : E (G) → { − 1 , 1 } is called a good signing if the absolute eigenvalues of its adjacency matrix are at most 2 d − 1 . Bilu and Linial conjectured that for each regular graph there exists a good signing. In this paper, by using the concept of "Equitable Partition", we prove the conjecture for some cases. We show how to find out a good signing for special complete graphs and lexicographic product of two graphs. In particular, if there exist two good signings for graph G , then we can find a good signing for a 2-lift of G. [ABSTRACT FROM AUTHOR]

Let D(G) and A(G), respectively, be the diagonal matrix of vertex de- grees and the adjacency matrix of a connected graph G. The generalized adjacency matrix of G is defined as Aα(G) = αD(G) + (1 − α)A(G), α ∈ [0, 1]. The spread of the generalized adjacency matrix, denoted by S(Aα(G)), is defined as the difference of the largest and smallest eigenvalues of Aα(G). The spread S(Q(G)) of Q(G), the signless Laplacian matrix of G and S(A(G)) of A(G) are similarly defined. In this paper, we establish the relationships between S(Aα(G)), S(Q(G)) and S(A(G)). Further, we find bounds for S(Aα(G)) involving different parameters of G. Also, we obtain lower bounds for S(Aα(G)) in terms of the clique number and independence number of G, and we characterize the extremal graphs in some cases. [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]

To meet the increased customer demands, microgrid evolved. The structure of microgrid changes dynamically due to the intermittent nature of renewable-based generation, status of the distributed generator and opening of breakers for fault/maintenance. Hence, the magnitude of fault current is dynamic in nature. In order to deal with these dynamic changes, this paper addresses an adaptive central microgrid controller-based protection and relay coordination scheme, which revises the relay settings dynamically (both radial and looped configuration) for every change in topology. In the proposed algorithm, the primary relay responds to a fault immediately since the individual relays are given with fault level setting. For any abnormality in the network, the fault location is determined both via local relay and microgrid central controller (MCC). Hence, even though the local relay fails to identify the fault due to high fault impedance, the MCC locates the fault accurately and isolates the minimum faulty part. The coordination between relays is carried out by MCC in a time-graded manner based on microgrid central protection and relay coordination algorithm. The proposed algorithm is tested using Matlab in a microgrid built based on the IEEE 33 bus distribution network. [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]

Applying machine learning algorithms to graph-structured data has garnered significant attention in recent years due to the prevalence of inherent graph structures in real-life datasets. However, the direct application of traditional deep learning algorithms, such as Convolutional Neural Networks (CNNs), is limited as they are designed for regular Euclidean data like 2D grids and 1D sequences. In contrast, graph-structured data are in a non-Euclidean form. Graph Neural Networks (GNNs) are specifically designed to handle non-Euclidean data and make predictions based on connectivity rather than spatial structure. Real-life graph data can be broadly categorized into two types: spatially-invariant graphs, where the link structure between nodes is independent of their spatial positions, and spatially-variant graphs, where node positions provide additional information about the graph's properties. However, there is limited understanding of the effect of spatial variance on the performance of Graph Neural Networks. In this study, we aim to address this issue by comparing the performance of GNNs and CNNs on spatially-variant and spatially-invariant graph data. In the case of spatially-variant graphs, when represented as adjacency matrices, they can exhibit Euclidean-like spatial structure. Based on this distinction, we hypothesize that CNNs may outperform GNNs when working with spatially-variant graphs, while GNNs may excel on spatially-invariant graphs. To test this hypothesis, we compared the performance of CNNs and GNNs under two scenarios: (i) graphs in the training and test sets had the same connectivity pattern and spatial structure, and (ii) graphs in the training and test sets had the same connectivity pattern but different spatial structures. Our results confirmed that the presence of spatial structure in a graph allows for the effective use of CNNs, which may even outperform GNNs. Thus, our study contributes to the understanding of the effect of spatial graph structure on the performance of machine learning methods and allows for the selection of an appropriate algorithm based on the spatial properties of the real-life graph dataset. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a simple connected graph with vertex set V and edge set E, respectively. The term "anti-reciprocal eigenvalue property" refers to a non-singular graph G for which, − 1 λ ∈ σ (G) , whenever λ ∈ σ (G) , ∀ λ ∈ σ (G) . Here, σ (G) is the multiset of all eigenvalues of A (G) . Moreover, if multiplicities of eigenvalues and their negative reciprocals are equal, then that graph is said to have strong anti-reciprocal eigenvalue properties, and the graph is referred to as a strong anti-reciprocal graph (or (− S R) graph). In this article, a new family of graphs F n (k , j) is introduced and the energy of F 5 (k , k 2) k ≥ 2 is calculated. Furthermore, with the help of F 5 (k , k 2) , some families of (− S R) graphs are constructed. [ABSTRACT FROM AUTHOR]

The class of unicyclic non-bipartite graphs with unique perfect matching, denoted by U , is considered in this article. This article provides a complete characterization of unicyclic graphs in U which possess tricyclic inverses. [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]

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]

This paper is devoted to the study of the double domination in vague graphs, and it is a contribution to the Special Issue "Advances in graph theory and Symmetry/Asymmetry" of Symmetry. Symmetry is one of the most important criteria that illustrate the structure and properties of fuzzy graphs. It has many applications in dominating sets and helps find a suitable place for construction. Vague graphs (VGs), which are a family of fuzzy graphs (FGs), are a well-organized and useful tool for capturing and resolving a range of real-world scenarios involving ambiguous data. In the graph theory, a dominating set (DS) for a graph G * = (X , E) is a subset D of the vertices X so that every vertex which is not in D is adjacent to at least one member of D. The subject of energy in graph theory is one of the most attractive topics serving a very important role in biological and chemical sciences. Hence, in this work, we express the notion of energy on a dominating vague graph (DVG) and also use the concept of energy in modeling problems related to DVGs. Moreover, we introduce a new notion of a double dominating vague graph (DDVG) and provide some examples to explain various concepts introduced. Finally, we present an application of energy on DVGs. [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 paper, continuous-time quantum walk on hypercube is discussed in view of Cartesian product structure. We find that the n -fold Cartesian power of the complete graph K 2 is the n -dimensional hypercube, which give us new ideas for the study of quantum walk on hypercube. Combining the product structure, the spectral distribution of the graph and the quantum decomposition of the adjacency matrix, the probability amplitudes of the continuous-time quantum walker's position at time t are given, and it is discussed that the probability distribution for the continuous-time case is uniform when t = (π ∕ 4) n. The application of this product structure greatly improves the study of quantum walk on complex graphs, which has far-reaching influence and great significance. [ABSTRACT FROM AUTHOR]