Search

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]

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]

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]

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]

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]

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]

In this article, we undertake the problem of finding the first four trees on a fixed number of vertices with the maximum smallest positive eigenvalue. Let T n , d denote the class of trees on n vertices with diameter d. First, we obtain the bounds on the smallest positive eigenvalue of trees in T n , d for d = 2 , 3 , 4 and then upper bounds on the smallest positive eigenvalue of trees are obtained in general class of all trees on n vertices. Finally, the first four trees on n vertices with the maximum, second maximum, third maximum and fourth maximum smallest positive eigenvalue are characterized. [ABSTRACT FROM AUTHOR]

Isomorphism identification plays an important role in structural design and innovative design. Based on the adjacency matrix and loop theory, a new method is proposed in this paper to identify the isomorphic kinematic chains. It enriches the application of loop-based theory for isomorphism identification. In the kinematic chain, links and joints are connected alternatively and every link corresponds to a fixed link degree. Due to the inherent characteristics, the labeled sequence of links can be random, which does not affect the result of isomorphism identification. By the programming software MATLAB, some examples with 6-, 8-, 10-, 11-, 12-link kinematic chains, and 15-vertex topological graphs are presented. Results show that the proposed method applies to topology graphs and kinematic chains with one or multiple joints. Compared with other methods, the proposed method is confirmed correctly. And there is no counterexample. It lays a solid foundation for structural synthesis in the future. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the conditions for constructing a single deletion error-correcting codes for protecting quantum information. According to the recent study by Nakayama and Hagiwara, this code can be constructed by using two sets of binary sequences satisfying certain three conditions, namely NH conditions. The NH conditions are described only combinatorially, but they are very complicated and only two examples have been given so far. In the present study, we aim to provide many examples of new deletion error-correcting codes by constructing various types of sets that satisfy the NH conditions discussed in the previous research. We show two families of sets satisfying the NH conditions and present a recursive construction method. This allows us to construct n-qubit codes in which the value of n is 4 or more. Furthermore, by discussing the NH conditions in terms of the adjacency matrices of the graph, we obtain all examples with length 5 or less. [ABSTRACT FROM AUTHOR]

We consider the notion of χ -completeness of a locally finite graph and we extend this notion to the weighted magnetic graph. Moreover, we establish a link between the magnetic adjacency matrix on line graph and the magnetic discrete Laplacian on 1-forms. [ABSTRACT FROM AUTHOR]

After Curl, Kroto and Smalley were awarded 1996 the Nobel Prize in chemistry, fullerenes have been subject of much research. One part of that research is the prediction of a fullerene's stability using topological descriptors. It was mainly done by considering the distribution of the twelve pentagonal facets on its surface, calculations mostly were performed on all isomers of C40, C60 and C80. This paper suggests a novel method for the classification of combinatorial fullerene isomers using spectral graph theory. The classification presupposes an invariant scheme for the facets based on the Schlegel diagram. The main idea is to find clusters of isomers by analyzing their graph structure of hexagonal facets only. We also show that our classification scheme can serve as a formal stability criterion, which became evident from a comparison of our results with recent quantum chemical calculations (Sure et al. in Phys Chem Chem Phys 19:14296–14305, 2017). We apply our method to classify all isomers of C60 and give an example of two different cospectral isomers of C44. Calculations are done with our own Python scripts available at (Bille et al. in Fullerene database and classification software, https://www.uni-ulm.de/mawi/mawi-stochastik/forschung/fullerene-database/, 2020). The only input for our algorithm is the vector of positions of pentagons in the facet spiral. These vectors and Schlegel diagrams are generated with the software package Fullerene (Schwerdtfeger et al. in J Comput Chem 34:1508–1526, 2013). [ABSTRACT FROM AUTHOR]

In the current paper, we study the discrete Laplacian acting on 2-forms which was introduced and investigated by Chebbi (Potential Anal 49(2):331–358, 2018). We establish a new criterion of essential self-adjointness using the Nelson lemma. Moreover, we give an upper bound on the infimum of the essential spectrum. Furthermore, we establish a link between the adjacency matrix and the discrete Laplacian on 2-forms. [ABSTRACT FROM AUTHOR]

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5 ⩽ k ⩽ 8 and n ⩾ k + 5) with the minimal least eigenvalue. [ABSTRACT FROM AUTHOR]

A threshold graph G of order n is defined by binary sequence of length n. In this paper, we consider the adjacent matrix of a connected threshold graph, and give the eigenvalues distribution in threshold graphs. Moreover, we pick out all the threshold graphs with distinct eigenvalues, and determine the HOMO–LUMO index of threshold graphs. [ABSTRACT FROM AUTHOR]

Connected planar graphs are of interest to a variety of scholars. Being able to simulate a database of such graphs with selected properties would support specific types of inference for spatial analysis and other network-based disciplines. This paper presents a simple, efficient, and flexible connected planar graph generator for this purpose. It also summarizes a comparison between an empirical set of specimen graphs and their simulated counterpart set, and establishes evidence for positing a conjecture about the principal eigenvalue of connected planar graphs. Finally, it summarizes a probability assessment of the algorithm’s outcomes as well as a comparison between the new algorithm and selected existing planar graph generators. [ABSTRACT FROM AUTHOR]

In this paper, a tolerance representation model for generating tolerance specification schemes and corresponding tolerance zones is proposed to meet the requirement of the representation of tolerance information semantics. This model is hierarchically organized and consists of five layers. They are component, geometric feature, variational geometric constraint, tolerance specification scheme, and tolerance zone layers. The mating relations between components in the component layer, the mating relations between geometric features in the geometric feature layer, the variational geometric constraints between geometric features in the variational geometric constraint layer, the tolerance specification schemes of component in the tolerance specification scheme layer, and the tolerance zones of tolerance specification schemes in the tolerance zone layer are formally defined by one or more adjacency matrices, respectively. Based on the model, a method for generating tolerance specification schemes for component and their resultant tolerance zones is designed. This method shows how to adopt a top-down strategy to carry out tolerance specification for an arbitrary assembly designed in a CAD system. The paper also provides a practical example to illustrate how the method works. [ABSTRACT FROM AUTHOR]

In recent years, the number of applications utilizing mobile wireless sensor networks (WSNs) has increased, with the intent of localization for the purposes of monitoring and obtaining data from hazardous areas. Location of the event is very critical in WSN, as sensing data is almost meaningless without the location information. In this paper, two Monte Carlo based localization schemes termed MCL and MSL* are studied. MCL obtains its location through anchor nodes whereas MSL* uses both anchor nodes and normal nodes. The use of normal nodes would increase accuracy and reduce dependency on anchor nodes, but increases communication costs. For this reason, we introduce a new approach called low communication cost schemes to reduce communication cost. Unlike MSL* which chooses all normal nodes found in the neighbor, the proposed scheme uses set theory to only select intersected nodes. To evaluate our method, we simulate in our proposed scheme the use of the same MSL* settings and simulators. From the simulation, we find out that our proposed scheme is able to reduce communication cost-the number of messages sent-by a minimum of 0.02 and a maximum of 0.30 with an average of 0.18, for varying node densities from 6 to 20, while nonetheless able to retain similar MSL* accuracy rates. [ABSTRACT FROM AUTHOR]

A Hamiltonian cycle in a graph is a cycle that visits each node/vertex exactly once. A graph containing a Hamiltonian cycle is called a Hamiltonian graph. There have been several researches to find the number of Hamiltonian cycles of a Hamilton graph. As the number of vertices and edges grow, it becomes very difficult to keep track of all the different ways through which the vertices are connected. Hence, analysis of large graphs can be efficiently done with the assistance of a computer system that interprets graphs as matrices. And, of course, a good and well written algorithm will expedite the analysis even faster. The most convenient way to quickly test whether there is an edge between two vertices is to represent graphs using adjacent matrices. In this paper, a new algorithm is proposed to find fuzzy Hamiltonian cycle using adjacency matrix and the degree of the vertices of a fuzzy graph. A fuzzy graph structure is also modeled to illustrate the proposed algorithms with the selected air network of Indigo airlines. [ABSTRACT FROM AUTHOR]

A quantum particle evolving by Schrödinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences. [ABSTRACT FROM AUTHOR]

Let $$\fancyscript{B}(n,r)$$ be the set of all bicyclic graphs with $$n$$ vertices and $$r$$ cut edges. In this paper we determine the unique graph with maximal adjacency spectral radius or signless Laplacian spectral radius among all graphs in $$\fancyscript{B}(n,r)$$ . [ABSTRACT FROM AUTHOR]

In the process of mechanism creative design, structure synthesis is the primary and the most important issue. This paper proposes a systematic and automatic synthesizing method of fixed-axle gear sets by means of morphological analysis. And the process is implemented to synthesize Electrified Mechanical Transmission (EMT) schemes which are parallel hybrid electric transmission composed of fixed-axle gear sets. First, independent design parameters as well as feasibility constraints and consistency conditions are defined by analyzing the structure and functions of EMT. According to these boundary conditions, structure variables such as the quantity of components and their connection relationship are solved. Then, the scheme quantity of each structure type is synthesized. Secondly, based on the abstraction of practical mechanisms with topology models, the corresponding adjacency matrixes are derived, and they are used to filtering unqualified schemes and retrieve all potential transmission paths of the remaining schemes. These potential transmission paths are further used to find out the layout and operating mode of each scheme. Finally, all schemes satisfying the structural and functional requirements are synthesized. For example, one EMT prototype is built based on one of the final schemes found and an ICE car is modified to adapt to such transmission. Vehicle test results verify the effectiveness and feasibility of the chosen transmission scheme. [ABSTRACT FROM AUTHOR]

The weighted graphs, where the edge weights are positive numbers, are considered. The authors obtain some lower bounds on the spectral radius and the Laplacian spectral radius of weighted graphs, and characterize the graphs for which the bounds are attained. Moreover, some known lower bounds on the spectral radius and the Laplacian spectral radius of unweighted graphs can be deduced from the bounds. [ABSTRACT FROM AUTHOR]

We consider correspondence analysis (CA) and taxicab correspondence analysis (TCA) of relational datasets that can mathematically be described as weighted loopless graphs. Such data appear in particular in network analysis. We present CA and TCA as relaxation methods for the graph partitioning problem. Examples of real datasets are provided. [ABSTRACT FROM AUTHOR]

A procedure of searching the characteristic images of clouds of different types based on a comparison of data archive of meteorological stations with MODIS satellite images is presented. 14 cloud types that have unique texture of MODIS images recorded with 250 m resolution in the visible spectral range are identified. The texture approach to determination of image characteristics of cloudy cover based on satellite information is stated. A procedure of forming a system of informative texture parameters is described. Results of analysis of cloudiness types from satellite images that confirm the uniqueness of their textures are presented and discussed. [ABSTRACT FROM AUTHOR]

We study spectral properties of the Manhattan products of the path graphs and show the concentration of zero-eigenvelues. [ABSTRACT FROM AUTHOR]

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

This paper proposes an efficient parallel implementation of the Ramalingam algorithm for dynamically updating the single-sink shortest-path subgraph of a directed graph after adding an edge to the graph with the use of a model of associative (content addressable) parallel systems with vertical processing (the STAR machine). An associative version of this algorithm is described as the InsertNewArc procedure whose correctness is proved. We also consider the main advantages of the associative version of the Ramalingam incremental algorithm. [ABSTRACT FROM AUTHOR]

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx: Ax≥ b, 0≤ x≤ d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A, b, c, d are nonnegative.) For any k≥2 and ε>0, if P≠ NP this ratio cannot be improved to k−1− ε, and under the unique games conjecture this ratio cannot be improved to k− ε. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx: Ax≤ b, 0≤ x≤ d} where A has at most k nonzeroes per column, we give a (2 k+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A is small compared to b. Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column. [ABSTRACT FROM AUTHOR]

In this paper we present an O( nlog n) time algorithm for finding a maximum flow in a directed planar graph, where the vertices are subject to capacity constraints, in addition to the arcs. If the source and the sink are on the same face, then our algorithm can be implemented in O( n) time. For general (not planar) graphs, vertex capacities do not make the maximum flow problem more difficult, as there is a simple reduction that eliminates vertex capacities. However, this reduction does not preserve the planarity of the graph. The essence of our algorithm is a different reduction that does preserve the planarity and can be implemented in linear time. For the special case of undirected planar graphs, an algorithm with the same time complexity was recently claimed, but we show that it has a flaw. We also apply our technique to obtain a linear-time algorithm to convert a flow to an acyclic flow, and a linear-time algorithm to find a largest set of vertex-disjoint s− t paths, in a directed planar graph. [ABSTRACT FROM AUTHOR]

We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J. Comb. 15(1), ), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199-233, ) and by Aigner and van der Holst (Linear Algebra Appl., ). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J. Comb. 15(1), ) employs a general logical framework and leads to an algorithm with running time f( k)⋅ n, where f( k) is doubly exponential in k. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses $2^{3k^{2}+O(k)}\cdot n$ arithmetic operations and can be efficiently implemented in parallel. [ABSTRACT FROM AUTHOR]

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

The Hoffman-Singleton graph is the unique strongly regular graph with parameters (50, 7, 0, 1). A well-known hypothesis states that a distance-regular graph in which the neighborhood of each vertex is isomorphic to the Hoffman-Singleton graph has intersection array {50, 42, 1; 1, 2, 50} or {50, 42, 9; 1, 2, 42}. In the present paper, we prove this hypothesis under the assumption that a distance-regular graph is a Terwilliger graph and the graph diameter is at most 5. [ABSTRACT FROM AUTHOR]

Given a locally finite simple graph so that its degree is not bounded, every self-adjoint realization of the adjacency matrix is unbounded from above. In this note, we give an optimal condition to ensure it is also unbounded from below. We also consider the case of weighted graphs. We discuss the question of self-adjoint extensions and prove an optimal criterium. [ABSTRACT FROM AUTHOR]

Possible orders and fixed-point subgraphs of automorphisms of a generalized octagon of order (2, 4) are found. The vertex-symmetric generalized octagon of order (2, 4) is proved to be classical. [ABSTRACT FROM AUTHOR]

The vast numbers of molecular objects and chemical transformations of a substrate cannot be evaluated even intuitively, which necessitates the development of simple reaction monitoring methods. Here this problem is formulated for the first time, and possible solutions are substantiated. [ABSTRACT FROM AUTHOR]

This paper presents a new MSDI (mold surface data integration) method for presenting ruled mold-surface data for CAPP applications. The method makes use of adjacency and feature-data matrices to establish a framework of feature-based data. The MSDI method enables the storage, retrieval and operations of geometries, topologies, and machining information of a given ruled mold surface. The matrices of adjacency and feature-data effectively represent the relations. Boolean algebra and group technology (GT) methods are introduced to generate the desired process plans. A sample mold made of ruled surfaces is made and used to show the effectiveness of the proposed data representation and the integrated mold surface processing method. A compact computer program is implemented to enhance the speed and accuracy of the MSDI method. The numerical results indicate that the mold surface decomposition and integration procedure presented in this paper are systematic and effective. The paper provides a novel modular mold surface modeling tool and procedure that can be further extended to accommodate more features appearing in complicated ruled mold surfaces. [ABSTRACT FROM AUTHOR]

Text retrieval systems require an index to allow efficient retrieval of documents at the cost of some storage overhead. This paper proposes a novel full-text indexing model for Chinese text retrieval based on the concept of adjacency matrix of directed graph. Using this indexing model, on one hand, retrieval systems need to keep only the indexing data, instead of the indexing data and the original text data as the traditional retrieval systems always do. On the other hand, occurrences of index term are identified by labels of the so-calleds-stringswhere the index term appears, rather than by its positions as in traditional indexing models. Consequently, system space cost as a whole can be reduced drastically while retrieval efficiency is maintained satisfactory. Experiments over several real-world Chinese text collections are carried out to demonstrate the effectiveness and efficiency of this model. In addition to Chinese, The proposed indexing model is also effective and efficient for text retrieval of other Oriental languages, such as Japanese and Korean. It is especially useful for digital library application areas where storage resource is very limited (e.g., e-books and CD-based text retrieval systems). [ABSTRACT FROM AUTHOR]

It is proved that any set of finite pairwise nonisomorphic weakly cospectral connected pseudographs, as well as any set of pseudodigraphs satisfying various additional conditions, is finite. [ABSTRACT FROM AUTHOR]