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]

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]

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 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]

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]

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]

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]

For a simple connected graph G of order n, the normalized Laplacian is a square matrix of order n, defined as ℒ (G) = D (G) − 1 2 L (G) D (G) − 1 2 , where D (G) − 1 2 is the diagonal matrix whose i-th diagonal entry is 1 d i . In this paper, we find the normalized Laplacian eigenvalues of the joined union of regular graphs in terms of the adjacency eigenvalues and the eigenvalues of quotient matrix associated with graph G. For a finite group , the power graph () of a group is defined as the simple graph in which two distinct vertices are joined by an edge if and only if one is the power of the other. As a consequence of the joined union of graphs, we investigate the normalized Laplacian eigenvalues of the power graphs of the finite cyclic group ℤ n . [ABSTRACT FROM AUTHOR]

In this paper, continuous-time quantum walk is discussed based on the view of quantum probability, i.e. the quantum decomposition of the adjacency matrix A of graph. Regard adjacency matrix A as Hamiltonian which is a real symmetric matrix with elements 0 or 1, so we regard  e − i t A  as an unbiased evolution operator, which is related to the calculation of probability amplitude. Combining the quantum decomposition and spectral distribution  μ  of adjacency matrix A, we calculate the probability amplitude reaching each stratum in continuous-time quantum walk on complete bipartite graphs, finite two-dimensional lattices, binary tree, N -ary tree and N -fold star power G ⋆ N . Of course, this method is also suitable for studying some other graphs, such as growing graphs, hypercube graphs and so on, in addition, the applicability of this method is also explained. [ABSTRACT FROM AUTHOR]

Let U n g be the set of connected unicyclic graphs of order n and girth g. Let C (T 1 , T 2 , ... , T g) ∈ U n g be obtained from a cycle v 1 v 2 ⋯ v g v 1 (in an anticlockwise direction) by identifying V i with the root of a rooted tree T i of order n i for each i = 1 , 2 , ... , g , where n i ≥ 1 and ∑ i = 1 g n i = n. In this note, the graph with the minimal least eigenvalue (and the graph with maximal spread) in C (T 1 , T 2 , ... , T g) is determined. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a class of treelike networks generated by motifs with single root node. We study the spectral properties of treelike networks by studying the behaviors of the corresponding adjacency matrix and Laplacian matrix. First, we get the adjacency matrix and Laplacian matrix of this treelike network. Then, we analyze symmetry of eigenvalues, multiplicity of eigenvalue 0 and prove that its largest eigenvalue is strictly monotonically increasing and convergent. Finally, we introduce a new method to prove that the largest eigenvalue of the Laplacian matrix is strictly monotonically increasing and convergent. Also, we obtain that its smallest nonzero eigenvalue is strictly monotonically decreasing and convergent. [ABSTRACT FROM AUTHOR]

The multiple subdivision graph of a graph G , denoted by S n (G) , is the graph obtained by inserting n paths of length 2 replacing every edge of G. When n = 1 , S 1 (G) = S (G) is the subdivision graph of G. Let G 1 be a graph with n 1 vertices and m 1 edges, G 2 be a graph with n 2 vertices and m 2 edges. The quasi-corona SG-vertex join G 1 △ G 2 of G 1 and G 2 is the graph obtained from S (G 1) ∪ G 1 and n 1 copies of G 2 by joining every vertex of G 1 to every vertex of G 2 , and multiple SG-vertex join G 1 ⊙ G 2 is the graph obtained from S n (G 1) ∪ G 1 and G 2 by joining every vertex of G 1 to every vertex of G 2 . In this paper, we calculate analytic expression of characteristic polynomial of adjacency matrix of the above two types of joins of graphs for the case of G 1 being a regular graph. Then we obtain their adjacency spectra for the case of G 1 and G 2 being regular graphs. [ABSTRACT FROM AUTHOR]

It is much more practical to use the t -norm than the minimum in defining the fuzzy graph. Hence, the concept of t -fuzzy graph was introduced by Mordeson et al. in [J. N. Mordeson and S. Mathew, t -norm Fuzzy Graphs, New Mathematics and Natural Computation14(1) (2018) 129–143]. In this paper, we concentrate on the relatively new concept of fuzzy adjacency matrix of that t -fuzzy graphs. The purpose of this paper is to further develop a product of this fuzzy adjacency matrix based on t -fuzzy graphs. Moreover, two kinds of Boolean matrix are defined and relation between Normal Boolean matrix, product of adjacency matrix and 1-level cut Boolean matrix is obtained. [ABSTRACT FROM AUTHOR]

In a recent paper, we studied the interaction between the automorphism group of a graph and its Tutte polynomial. More precisely, we proved that certain symmetries of graphs are clearly reflected by their Tutte polynomials. The purpose of this paper is to extend this study to other graph polynomials. In particular, we prove that if a graph G has a symmetry of prime order p , then its characteristic polynomial, with coefficients in the finite field 𝔽 p , is determined by the characteristic polynomial of its quotient graph G ¯. Similar results are also proved for some generalization of the Tutte polynomial. [ABSTRACT FROM AUTHOR]

In recent years, weighted networks have been extensively studied in various fields. This paper studies characteristic polynomial of adjacency or Laplacian matrix for weighted treelike networks. First, a class of weighted treelike networks with a weight factor is introduced. Then, the relationships of adjacency or the Laplacian matrix at two successive generations are obtained. Finally, according to the operation of the block matrix, we obtain the analytic expression of the characteristic polynomial of the adjacency or the Laplacian matrix. The obtained results lay the foundation for the future study of adjacency spectrum or Laplacian spectrum. [ABSTRACT FROM AUTHOR]

Let G 1 , G 2 and H be three graphs on disjoint sets of vertices and G 1 has m 1 edges. Let S (G 1 , H) be the graph obtained from G 1 and H in the following way: (1) Delete all the edges of G 1 and consider m 1 disjoint copies of H. (2) Join each vertex of the i th copy of H to the end vertices of the i th edge of G 1 . Let G 1 (∨ H) G 2 be the graph obtained from S (G 1 , H) by joining each vertex of G 1 with each vertex of G 2. In this paper, we determine the adjacency (respectively, Laplacian, signless Laplacian) spectrum of G 1 (∨ H) G 2 in terms of those of G 1 , G 2 and H. As an application, we construct infinite pairs of cospectral graphs. [ABSTRACT FROM AUTHOR]

Let Gw be a weighted graph. The number of the positive, negative and zero eigenvalues in the spectrum of Gw are called positive inertia index, negative inertia index and nullity of Gw, and denoted by i+(Gw), i-(Gw), i0(Gw), respectively. In this paper, sharp lower bound on the positive (respectively, negative) inertia index of weighted bicyclic graphs of order n with pendant vertices is obtained. Moreover, all the weighted bicyclic graphs of order n with at most two positive, two negative and at least n - 4 zero eigenvalues are identified, respectively. [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]

A three-dimensional (3D) theoretical morphospace of gomphonemoid and cymbelloid diatoms was skeletonized using concepts from extended Reeb graph analysis and Morse theory. The resultant skeleton tree was matched to a cladogram of the same group of related taxa using adjacency matrices of the trees and ordinated with multidimensional scaling (MDS) of leaf nodes. From this, an unweighted path matrix based on the number of branches between leaf nodes was ordinated to determine degree of matched tree structures. A constrained MDS of the path matrix, weighted by ranked MDS leaf node groups as facets, was used to interpret taxon environmental tolerances and habitat preferences with respect to adaptive value. The methods developed herein provided a way to combine results from morphological and phylogenetic analyses and interpret those results with respect to an aspect of evolutionary process, namely, adaptation. [ABSTRACT FROM AUTHOR]

Severe thunderstorms are a manifestation of deep convection. Conditional instability is known to be the mechanism by which thunderstorms are formed. The energy that drives conditional instability is convective available potential energy (CAPE), which is computed with radio sonde data at each pressure level. The purpose of the present paper is to identify the pattern or shape of CAPE required for the genesis of severe thunderstorms over Kolkata (22°32′N, 88°20′E) confined within the northeastern part (20°N to 24°N latitude, 85°E to 93°E longitude) of India. The method of chaotic graph theory is adopted for this purpose. Chaotic graphs of pressure levels and CAPE are formed for thunderstorm and non-thunderstorm days. Ranks of the adjacency matrices constituted with the union of chaotic graphs of pressure levels and CAPE are computed for thunderstorm and non-thunderstorm days. The results reveal that the rank of the adjacency matrix is maximum for non-thunderstorm days and a column with all zeros occurs very quickly on severe thunderstorms days. This indicates that CAPE loses connectivity with pressure levels very early on severe thunderstorm days, showing that for the genesis of severe thunderstorms over Kolkata short, and therefore broad, CAPE is preferred. [ABSTRACT FROM AUTHOR]

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]

The adjacency matrix of a comb graph is decomposed into a sum of monotone independent random variables with respect to the vacuum state. The vacuum spectral distribution is shown to be asymptotically the arcsine law as a consequence of the monotone central limit theorem. As an example the comb lattice is studied with explicit calculation. [ABSTRACT FROM AUTHOR]