Log in

Relevant bibliographies by topics / Spectral graph theory / Journal articles

To see the other types of publications on this topic, follow the link: Spectral graph theory.

Journal articles on the topic 'Spectral graph theory'

Author: Grafiati

Published: 4 June 2021

Last updated: 28 September 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Spectral graph theory.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Cvetkovic, Dragos. "Spectral recognition of graphs." Yugoslav Journal of Operations Research 22, no. 2 (2012): 145–61. http://dx.doi.org/10.2298/yjor120925025c.

Full text

Abstract:

At some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same spectrum (cospectral graphs) were found. Still some graphs are characterized by their spectra and several mathematical papers are devoted to this topic. In applications to computer sciences, spectral graph theory is considered as very strong. The benefit of using graph spectra in treating graphs is that eigenvalues and eigenvectors of several graph matrices can be quickly computed. Spectral graph parameters contain a lot of information on the graph structure (both global and local) including some information on graph parameters that, in general, are computed by exponential algorithms. Moreover, in some applications in data mining, graph spectra are used to encode graphs themselves. The Euclidean distance between the eigenvalue sequences of two graphs on the same number of vertices is called the spectral distance of graphs. Some other spectral distances (also based on various graph matrices) have been considered as well. Two graphs are considered as similar if their spectral distance is small. If two graphs are at zero distance, they are cospectral. In this sense, cospectral graphs are similar. Other spectrally based measures of similarity between networks (not necessarily having the same number of vertices) have been used in Internet topology analysis, and in other areas. The notion of spectral distance enables the design of various meta-heuristic (e.g., tabu search, variable neighbourhood search) algorithms for constructing graphs with a given spectrum (spectral graph reconstruction). Several spectrally based pattern recognition problems appear in many areas (e.g., image segmentation in computer vision, alignment of protein-protein interaction networks in bio-informatics, recognizing hard instances for combinatorial optimization problems such as the travelling salesman problem). We give a survey of such and other graph spectral recognition techniques used in computer sciences.

APA, Harvard, Vancouver, ISO, and other styles

2

Arsic, Branko, Dragos Cvetkovic, Slobodan Simic, and Milan Skaric. "Graph spectral techniques in computer sciences." Applicable Analysis and Discrete Mathematics 6, no. 1 (2012): 1–30. http://dx.doi.org/10.2298/aadm111223025a.

Full text

Abstract:

We give a survey of graph spectral techniques used in computer sciences. The survey consists of a description of particular topics from the theory of graph spectra independently of the areas of Computer science in which they are used. We have described the applications of some important graph eigenvalues (spectral radius, algebraic connectivity, the least eigenvalue etc.), eigenvectors (principal eigenvector, Fiedler eigenvector and other), spectral reconstruction problems, spectra of random graphs, Hoffman polynomial, integral graphs etc. However, for each described spectral technique we indicate the fields in which it is used (e.g. in modelling and searching Internet, in computer vision, pattern recognition, data mining, multiprocessor systems, statistical databases, and in several other areas). We present some novel mathematical results (related to clustering and the Hoffman polynomial) as well.

APA, Harvard, Vancouver, ISO, and other styles

3

Hammond, David K., Pierre Vandergheynst, and Rémi Gribonval. "Wavelets on graphs via spectral graph theory." Applied and Computational Harmonic Analysis 30, no. 2 (March 2011): 129–50. http://dx.doi.org/10.1016/j.acha.2010.04.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Hayat, Sakander, Asad Khan, and Mohammed J. F. Alenazi. "On Some Distance Spectral Characteristics of Trees." Axioms 13, no. 8 (July 23, 2024): 494. http://dx.doi.org/10.3390/axioms13080494.

Full text

Abstract:

Graham and Pollack in 1971 presented applications of eigenvalues of the distance matrix in addressing problems in data communication systems. Spectral graph theory employs tools from linear algebra to retrieve the properties of a graph from the spectrum of graph-theoretic matrices. The study of graphs with “few eigenvalues” is a contemporary problem in spectral graph theory. This paper studies graphs with few distinct distance eigenvalues. After mentioning the classification of graphs with one and two distinct distance eigenvalues, we mainly focus on graphs with three distinct distance eigenvalues. Characterizing graphs with three distinct distance eigenvalues is “highly” non-trivial. In this paper, we classify all trees whose distance matrix has precisely three distinct eigenvalues. Our proof is different from earlier existing proof of the result as our proof is extendable to other similar families such as unicyclic and bicyclic graphs. The main tools which we employ include interlacing and equitable partitions. We also list all the connected graphs on ν ≤ 6 vertices and compute their distance spectra. Importantly, all these graphs on ν ≤ 6 vertices are determined from their distance spectra. We deliver a distance cospectral pair of order 7, thus making it a distance cospectral pair of the smallest order. This paper is concluded with some future directions.

APA, Harvard, Vancouver, ISO, and other styles

5

Cvetkovic, Dragos, and Slobodan Simic. "Towards a spectral theory of graphs based on the signless Laplacian, I." Publications de l'Institut Math?matique (Belgrade) 85, no. 99 (2009): 19–33. http://dx.doi.org/10.2298/pim0999019c.

Full text

Abstract:

A spectral graph theory is a theory in which graphs are studied by means of eigenvalues of a matrix M which is in a prescribed way defined for any graph. This theory is called M-theory. We outline a spectral theory of graphs based on the signless Laplacians Q and compare it with other spectral theories, in particular with those based on the adjacency matrix A and the Laplacian L. The Q-theory can be composed using various connections to other theories: equivalency with A-theory and L-theory for regular graphs, or with L-theory for bipartite graphs, general analogies with A-theory and analogies with A-theory via line graphs and subdivision graphs. We present results on graph operations, inequalities for eigenvalues and reconstruction problems.

APA, Harvard, Vancouver, ISO, and other styles

6

Jin, Ming, Heng Chang, Wenwu Zhu, and Somayeh Sojoudi. "Power up! Robust Graph Convolutional Network via Graph Powering." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 9 (May 18, 2021): 8004–12. http://dx.doi.org/10.1609/aaai.v35i9.16976.

Full text

Abstract:

Graph convolutional networks (GCNs) are powerful tools for graph-structured data. However, they have been recently shown to be vulnerable to topological attacks. To enhance adversarial robustness, we go beyond spectral graph theory to robust graph theory. By challenging the classical graph Laplacian, we propose a new convolution operator that is provably robust in the spectral domain and is incorporated in the GCN architecture to improve expressivity and interpretability. By extending the original graph to a sequence of graphs, we also propose a robust training paradigm that encourages transferability across graphs that span a range of spatial and spectral characteristics. The proposed approaches are demonstrated in extensive experiments to simultaneously improve performance in both benign and adversarial situations.

APA, Harvard, Vancouver, ISO, and other styles

7

Abdian, Ali Zeydi, and S. Morteza Mirafzal. "The spectral characterizations of the connected multicone graphs Kw ▽ LHS and Kw ▽ LGQ(3,9)." Discrete Mathematics, Algorithms and Applications 10, no. 02 (April 2018): 1850019. http://dx.doi.org/10.1142/s1793830918500192.

Full text

Abstract:

In the past decades, graphs that are determined by their spectrum have received much more and more attention, since they have been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. An important part of spectral graph theory is devoted to determining whether given graphs or classes of graphs are determined by their spectra or not. So, finding and introducing any class of graphs which are determined by their spectra can be an interesting and important problem. The main aim of this study is to characterize two classes of multicone graphs which are determined by their adjacency, Laplacian and signless Laplacian spectra. A multicone graph is defined to be the join of a clique and a regular graph. Let [Formula: see text] denote a complete graph on [Formula: see text] vertices. In the paper, we show that multicone graphs [Formula: see text] and [Formula: see text] are determined by both their adjacency spectra and their Laplacian spectra, where [Formula: see text] and [Formula: see text] denote the Local Higman–Sims graph and the Local [Formula: see text] graph, respectively. In addition, we prove that these multicone graphs are determined by their signless Laplacian spectra.

APA, Harvard, Vancouver, ISO, and other styles

8

Yu, Guidong, Tao Yu, Xiangwei Xia, and Huan Xu. "Spectral Sufficient Conditions on Pancyclic Graphs." Complexity 2021 (July 15, 2021): 1–8. http://dx.doi.org/10.1155/2021/3630245.

Full text

Abstract:

A pancyclic graph of order n is a graph with cycles of all possible lengths from 3 to n . In fact, it is NP-complete that deciding whether a graph is pancyclic. Because the spectrum of graphs is convenient to be calculated, in this study, we try to use the spectral theory of graphs to study this problem and give some sufficient conditions for a graph to be pancyclic in terms of the spectral radius and the signless Laplacian spectral radius of the graph.

APA, Harvard, Vancouver, ISO, and other styles

9

Lurie, Jacob. "Review of Spectral Graph Theory." ACM SIGACT News 30, no. 2 (June 1999): 14–16. http://dx.doi.org/10.1145/568547.568553.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Li, Dan, Guoping Wang, and Jixiang Meng. "On the distance signless Laplacian spectral radius of graphs and digraphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 438–46. http://dx.doi.org/10.13001/1081-3810.1982.

Full text

Abstract:

Let \eta(G) denote the distance signless Laplacian spectral radius of a connected graph G. In this paper,bounds for the distance signless Laplacian spectral radius of connected graphs are given, and the extremal graph with the minimal distance signless Laplacian spectral radius among the graphs with given vertex connectivity and minimum degree is determined. Furthermore, the digraph that minimizes the distance signless Laplacian spectral radius with given vertex connectivity is characterized.

APA, Harvard, Vancouver, ISO, and other styles

11

Pardo-Guerra, Sebastian, Vivek Kurien George, Vikash Morar, Joshua Roldan, and Gabriel Alex Silva. "Extending Undirected Graph Techniques to Directed Graphs via Category Theory." Mathematics 12, no. 9 (April 29, 2024): 1357. http://dx.doi.org/10.3390/math12091357.

Full text

Abstract:

We use Category Theory to construct a ‘bridge’ relating directed graphs with undirected graphs, such that the notion of direction is preserved. Specifically, we provide an isomorphism between the category of simple directed graphs and a category we call ‘prime graphs category’; this has as objects labeled undirected bipartite graphs (which we call prime graphs), and as morphisms undirected graph morphisms that preserve the labeling (which we call prime graph morphisms). This theoretical bridge allows us to extend undirected graph techniques to directed graphs by converting the directed graphs into prime graphs. To give a proof of concept, we show that our construction preserves topological features when applied to the problems of network alignment and spectral graph clustering.

APA, Harvard, Vancouver, ISO, and other styles

12

Yamada, Hiroshi. "Geary’s c and Spectral Graph Theory." Mathematics 9, no. 19 (October 3, 2021): 2465. http://dx.doi.org/10.3390/math9192465.

Full text

Abstract:

Spatial autocorrelation, of which Geary’s c has traditionally been a popular measure, is fundamental to spatial science. This paper provides a new perspective on Geary’s c. We discuss this using concepts from spectral graph theory/linear algebraic graph theory. More precisely, we provide three types of representations for it: (a) graph Laplacian representation, (b) graph Fourier transform representation, and (c) Pearson’s correlation coefficient representation. Subsequently, we illustrate that the spatial autocorrelation measured by Geary’s c is positive (resp. negative) if spatially smoother (resp. less smooth) graph Laplacian eigenvectors are dominant. Finally, based on our analysis, we provide a recommendation for applied studies.

APA, Harvard, Vancouver, ISO, and other styles

13

Goh, Hung Lik, Wan Heng Fong, and Sherzod Turaev. "Spectral Bipartition via Gap Cut on DNA Sequences." Semarak International Journal of Fundamental and Applied Mathematics 3, no. 1 (September 20, 2024): 11–27. http://dx.doi.org/10.37934/sijfam.3.1.1127.

Full text

Abstract:

Deoxyribonucleic Acid (DNA) and graph partitioning are two distinct fields of study which can be linked in the structure of biological networks. Graph partitioning has been extensively studied but not its application in the biological field. This research explored on the application of spectral graph partitioning in DNA splicing, aiming to simulate the cleavage of DNA by performing spectral bipartition on DNA sequences in a DNA splicing system. This research incorporates Fiedler theory and algebraic graph theory, which are commonly utilized in network analysis and the analysis of graph connectivity. Some DNA sequences of even length are selected and expressed in graphical representations. The adjacency matrix, Laplacian matrix, and degree matrix are computed from the graphs, as well as the Fiedler value and Fiedler vector associated with the graphs. Gap cut is used as a method of spectral bipartition which produces two partitions of DNA sequence of unequal lengths. The generalizations of gap cut on DNA sequences of even length are provided as lemmas and theorem.

APA, Harvard, Vancouver, ISO, and other styles

14

Adiga, Chandrashekar, Kinkar Das, and B. R. Rakshith. "Some Graphs Determined by their Signless Laplacian (Distance) Spectra." Electronic Journal of Linear Algebra 36, no. 36 (July 21, 2020): 461–72. http://dx.doi.org/10.13001/ela.2020.4951.

Full text

Abstract:

In literature, there are some results known about spectral determination of graphs with many edges. In [M.~C\'{a}mara and W.H.~Haemers. Spectral characterizations of almost complete graphs. {\em Discrete Appl. Math.}, 176:19--23, 2014.], C\'amara and Haemers studied complete graph with some edges deleted for spectral determination. In fact, they found that if the deleted edges form a matching, a complete graph $K_m$ provided $m \le n-2$, or a complete bipartite graph, then it is determined by its adjacency spectrum. In this paper, the graph $K_{n}\backslash K_{l,m}$ $(n>l+m)$ which is obtained from the complete graph $K_{n}$ by removing all the edges of a complete bipartite subgraph $K_{l,m}$ is studied. It is shown that the graph $K_{n}\backslash K_{1,m}$ with $m\ge4$ is determined by its signless Laplacian spectrum, and it is proved that the graph $K_{n}\backslash K_{l,m}$ is determined by its distance spectrum. The signless Laplacian spectral determination of the multicone graph $K_{n-2\alpha}\vee \alpha K_{2}$ was studied by Bu and Zhou in [C.~Bu and J.~Zhou. Signless Laplacian spectral characterization of the cones over some regular graphs. {\em Linear Algebra Appl.}, 436:3634--3641, 2012.] and Xu and He in [L. Xu and C. He. On the signless Laplacian spectral determination of the join of regular graphs. {\em Discrete Math. Algorithm. Appl.}, 6:1450050, 2014.] only for $n-2\alpha=1 ~\text{or}~ 2$. Here, this problem is completely solved for all positive integer $n-2\alpha$. The proposed approach is entirely different from those given by Bu and Zhou, and Xu and He.

APA, Harvard, Vancouver, ISO, and other styles

15

Granziol, Diego, Binxin Ru, Xiaowen Dong, Stefan Zohren, Michael Osborne, and Stephen Roberts. "Maximum Entropy Approach to Massive Graph Spectrum Learning with Applications." Algorithms 15, no. 6 (June 15, 2022): 209. http://dx.doi.org/10.3390/a15060209.

Full text

Abstract:

We propose an alternative maximum entropy approach to learning the spectra of massive graphs. In contrast to state-of-the-art Lanczos algorithm for spectral density estimation and applications thereof, our approach does not require kernel smoothing. As the choice of kernel function and associated bandwidth heavily affect the resulting output, our approach mitigates these issues. Furthermore, we prove that kernel smoothing biases the moments of the spectral density. Our approach can be seen as an information-theoretically optimal approach to learning a smooth graph spectral density, which fully respects moment information. The proposed method has a computational cost linear in the number of edges, and hence can be applied even to large networks with millions of nodes. We showcase the approach on problems of graph similarity learning and counting cluster number in the graph, where the proposed method outperforms existing iterative spectral approaches on both synthetic and real-world graphs.

APA, Harvard, Vancouver, ISO, and other styles

16

NATH, MILAN, and SOMNATH PAUL. "GRAPH TRANSFORMATION AND DISTANCE SPECTRAL RADIUS." Discrete Mathematics, Algorithms and Applications 05, no. 03 (September 2013): 1350014. http://dx.doi.org/10.1142/s1793830913500146.

Full text

Abstract:

Trees are very common in the theory and applications of combinatorics. In this paper, we consider graphs whose underlying structure is a tree and study the behavior of the distance spectral radius under a graph transformation. As an application, we find the corona tree that maximizes the distance spectral radius among all corona trees with a fixed maximum degree. We also find the graph with minimal (maximal) distance spectral radius among all corona trees. Finally, we determine the graph with minimal distance spectral radius in a special class of corona trees.

APA, Harvard, Vancouver, ISO, and other styles

17

Kaliuzhnyi-Verbovetskyi, D., and V. Pivovarchik. "RECOVERING THE SHAPE OF A QUANTUM CATERPILLAR TREE BY TWO SPECTRA." Mechanics And Mathematical Methods 5, no. 1 (June 30, 2023): 14–24. http://dx.doi.org/10.31650/2618-0650-2023-5-1-14-24.

Full text

Abstract:

existence of co-spectral (iso-spectral) graphs is a well-known problem of the classical graph theory. However, co-spectral graphs exist in the theory of quantum graphs also. In other words, the spectrum of the Sturm-Liouville problem on a metric graph does not determine alone the shape of the graph. Сo-spectral trees also exist if the number of vertices exceeds eight. We consider two Sturm-Liouville spectral problems on an equilateral metric caterpillar tree with real L2 (0,l) potentials on the edges. In the first (Neumann) problem we impose standard conditions at all vertices: Neumann boundary conditions at the pendant vertices and continuity and Kirchhoff’s conditions at the interior vertices. The second (Dirichlet) problem differs from the first in that in the second problem we set the Dirichlet condition at the root (one of the pendant vertices of the stalk of the caterpillar tree, i.e. the central path of it). Using the asymptotics of the eigenvalues of these two spectra we find the determinant of the normalized Laplacian of the tree and the determinant of the prime submatrix of the normalized laplacian obtained by deleting the row and the column corresponding to the root. Expanding the fraction of these determinants into continued fraction we receive full information on the shape of the tree. In general case this continued fraction is branched. We prove that in the case of a caterpillar tree the continued fraction does not branch and the spectra of the Neumann and Dirichlet problems uniquely determine the shape of the tree. A concrete example is shown. The known pair of co-spectral trees with minimal number (eight) of vertices belongs to the class of caterpillar trees. Keywords: metric graph, tree, pendant vertex, interior vertex, edge, caterpillar tree, Sturm-Liouville equation, potential, eigenvalues, spectrum, Dirichlet boundary condition, Neumann boundary condition, root, continued fraction, adjacency matrix, prime submatrix, normalized Laplacian

APA, Harvard, Vancouver, ISO, and other styles

18

Yurttas Gunes, Aysun, Muge Togan, Musa Demirci, and Ismail Naci Cangul. "Harmonic Index and Zagreb Indices of Vertex-Semitotal Graphs." European Journal of Pure and Applied Mathematics 13, no. 5 (December 27, 2020): 1260–69. http://dx.doi.org/10.29020/nybg.ejpam.v13i5.3725.

Full text

Abstract:

Graph theory is one of the rising areas in mathematics due to its applications in many areas of science. Amongst several study areas in graph theory, spectral graph theory and topological descriptors are in front rows. These descriptors are widely used in QSPR/QSAR studies in mathematical chemistry. Vertex-semitotal graphs are one of the derived graph classes which are useful in calculating several physico-chemical properties of molecular structures by means of molecular graphs modelling the molecules. In this paper, several topological descriptors of vertex-semitotal graphs are calculated. Some new relations on these values are obtained by means of a recently defined graph invariant called omega invariant.

APA, Harvard, Vancouver, ISO, and other styles

19

Paul, Somnath. "On distance and distance Laplacian spectra of corona of two graphs." Discrete Mathematics, Algorithms and Applications 08, no. 01 (February 26, 2016): 1650007. http://dx.doi.org/10.1142/s1793830916500075.

Full text

Abstract:

Corona of two graphs has been defined in [F. Harary, Graph Theory (Addison-Wesley, 1969)]. In this paper, we study the distance and the distance Laplacian spectra of corona of two graphs and describe the complete distance (distance Laplacian) spectrum for some particular cases. As an application, we show that the corona operation can be used to create distance singular graphs. We also show that these results enable us to construct infinitely many pairs of distance (respectively, distance Laplacian) cospectral graphs. Last, we give a graph transformation and discuss its effect on the distance Laplacian spectral radius.

APA, Harvard, Vancouver, ISO, and other styles

20

Liu, Fangmeng, Wei Li, and Yiwen Zhong. "A Further Study on the Degree-Corrected Spectral Clustering under Spectral Graph Theory." Symmetry 14, no. 11 (November 16, 2022): 2428. http://dx.doi.org/10.3390/sym14112428.

Full text

Abstract:

Spectral clustering algorithms are often used to find clusters in the community detection problem. Recently, a degree-corrected spectral clustering algorithm was proposed. However, it is only used for partitioning graphs which are generated from stochastic blockmodels. This paper studies the degree-corrected spectral clustering algorithm based on the spectral graph theory and shows that it gives a good approximation of the optimal clustering for a wide class of graphs. Moreover, we also give theoretical support for finding an appropriate degree-correction. Several numerical experiments for community detection are conducted in this paper to evaluate our method.

APA, Harvard, Vancouver, ISO, and other styles

21

LIU, XIAOGANG. "SELECTED TOPICS IN SPECTRAL GRAPH THEORY." Bulletin of the Australian Mathematical Society 93, no. 3 (February 17, 2016): 511–12. http://dx.doi.org/10.1017/s0004972715001768.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Raj, Ashish, Chang Cai, Xihe Xie, Eva Palacios, Julia Owen, Pratik Mukherjee, and Srikantan Nagarajan. "Spectral graph theory of brain oscillations." Human Brain Mapping 41, no. 11 (March 23, 2020): 2980–98. http://dx.doi.org/10.1002/hbm.24991.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Coutino, Mario, Sundeep Prabhakar Chepuri, Takanori Maehara, and Geert Leus. "Fast Spectral Approximation of Structured Graphs with Applications to Graph Filtering." Algorithms 13, no. 9 (August 31, 2020): 214. http://dx.doi.org/10.3390/a13090214.

Full text

Abstract:

To analyze and synthesize signals on networks or graphs, Fourier theory has been extended to irregular domains, leading to a so-called graph Fourier transform. Unfortunately, different from the traditional Fourier transform, each graph exhibits a different graph Fourier transform. Therefore to analyze the graph-frequency domain properties of a graph signal, the graph Fourier modes and graph frequencies must be computed for the graph under study. Although to find these graph frequencies and modes, a computationally expensive, or even prohibitive, eigendecomposition of the graph is required, there exist families of graphs that have properties that could be exploited for an approximate fast graph spectrum computation. In this work, we aim to identify these families and to provide a divide-and-conquer approach for computing an approximate spectral decomposition of the graph. Using the same decomposition, results on reducing the complexity of graph filtering are derived. These results provide an attempt to leverage the underlying topological properties of graphs in order to devise general computational models for graph signal processing.

APA, Harvard, Vancouver, ISO, and other styles

24

Yu, Guanglong, Jianyong Wong, and Shu-guang Guo. "Maxima of the signless Laplacian spectral radius for planar graphs." Electronic Journal of Linear Algebra 30 (February 8, 2015): 795–811. http://dx.doi.org/10.13001/1081-3810.2023.

Full text

Abstract:

The signless Laplacian spectral radius of a graph is the largest eigenvalue of its signless Laplacian. In this paper, we prove that the graph $K_{2}\nabla P_{n-2}$ has the maximal signless Laplacian spectral radius among all planar graphs of order $n\geq 456$.

APA, Harvard, Vancouver, ISO, and other styles

25

Celik, Feriha, Utkum Sanli, and Ismail Naci Cangul. "The spectral polynomials of two joining graphs: splices and links." Boletim da Sociedade Paranaense de Matemática 40 (January 26, 2022): 1–12. http://dx.doi.org/10.5269/bspm.48651.

Full text

Abstract:

Energy of a graph, firstly defined by E. Hückel as the sum of absolute values of the eigenvalues of the adjacency matrix, in other words the sum of absolute values of the roots of the characteristic (spectral) polynomials, is an important sub area of graph theory. Symmetry and regularity are two important and desired properties in many areas including graphs. In many molecular graphs, we have a pointwise symmetry, that is the graph corresponding to the molecule under investigation has two identical subgraphs which are symmetrical at a vertex. Therefore, in this paper, we shall study only the vertex joining graphsIn this article we study the characteristic polynomials of the two kinds of joining graphs called splice and link graphs of some well known graph classes.

APA, Harvard, Vancouver, ISO, and other styles

26

Li, Yu, Meng Qu, Jian Tang, and Yi Chang. "Signed Laplacian Graph Neural Networks." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 4 (June 26, 2023): 4444–52. http://dx.doi.org/10.1609/aaai.v37i4.25565.

Full text

Abstract:

This paper studies learning meaningful node representations for signed graphs, where both positive and negative links exist. This problem has been widely studied by meticulously designing expressive signed graph neural networks, as well as capturing the structural information of the signed graph through traditional structure decomposition methods, e.g., spectral graph theory. In this paper, we propose a novel signed graph representation learning framework, called Signed Laplacian Graph Neural Network (SLGNN), which combines the advantages of both. Specifically, based on spectral graph theory and graph signal processing, we first design different low-pass and high-pass graph convolution filters to extract low-frequency and high-frequency information on positive and negative links, respectively, and then combine them into a unified message passing framework. To effectively model signed graphs, we further propose a self-gating mechanism to estimate the impacts of low-frequency and high-frequency information during message passing. We mathematically establish the relationship between the aggregation process in SLGNN and signed Laplacian regularization in signed graphs, and theoretically analyze the expressiveness of SLGNN. Experimental results demonstrate that SLGNN outperforms various competitive baselines and achieves state-of-the-art performance.

APA, Harvard, Vancouver, ISO, and other styles

27

Das, Kinkar, and SHAOWEI SUN. "Extremal graph on normalized Laplacian spectral radius and energy." Electronic Journal of Linear Algebra 29 (September 20, 2015): 237–53. http://dx.doi.org/10.13001/1081-3810.3263.

Full text

Abstract:

Let $G=(V,\,E)$ be a simple graph of order $n$ and the normalized Laplacian eigenvalues $\rho_1\geq \rho_2\geq \cdots\geq\rho_{n-1}\geq \rho_n=0$. The normalized Laplacian energy (or Randi\'c energy) of $G$ without any isolated vertex is defined as $$RE(G)=\sum_{i=1}^{n}|\rho_i-1|.$$ In this paper, a lower bound on $\rho_1$ of connected graph $G$ ($G$ is not isomorphic to complete graph) is given and the extremal graphs (that is, the second minimal normalized Laplacian spectral radius of connected graphs) are characterized. Moreover, Nordhaus-Gaddum type results for $\rho_1$ are obtained. Recently, Gutman et al.~gave a conjecture on Randi\'c energy of connected graph [I. Gutman, B. Furtula, \c{S}. B. Bozkurt, On Randi\'c energy, Linear Algebra Appl. 442 (2014) 50--57]. Here this conjecture for starlike trees is proven.

APA, Harvard, Vancouver, ISO, and other styles

28

Triyani, Triyani, Mashuri Mashuri, Bunga Tirai Anarkis, and Slamet Riyadi. "The spectrum on prism graph using circulant matrix." Bulletin of Applied Mathematics and Mathematics Education 2, no. 1 (May 18, 2022): 1–10. http://dx.doi.org/10.12928/bamme.v2i1.5129.

Full text

Abstract:

Spectral graph theory discusses about the algebraic properties of graphs based on the spectrum of a graph. This article investigated the spectrum of prism graph. The method used in this research is the circulant matrix. The results showed that prism graph P2,s is a regular graph of degree 3, for s odd and s ≥ 3, P2,s is a circulantt graph with regular spectrum.

APA, Harvard, Vancouver, ISO, and other styles

29

SUNTORNPOCH, BORWORN, and YOTSANAN MEEMARK. "CAYLEY GRAPHS OVER A FINITE CHAIN RING AND GCD-GRAPHS." Bulletin of the Australian Mathematical Society 93, no. 3 (January 22, 2016): 353–63. http://dx.doi.org/10.1017/s0004972715001380.

Full text

Abstract:

We extend spectral graph theory from the integral circulant graphs with prime power order to a Cayley graph over a finite chain ring and determine the spectrum and energy of such graphs. Moreover, we apply the results to obtain the energy of some gcd-graphs on a quotient ring of a unique factorisation domain.

APA, Harvard, Vancouver, ISO, and other styles

30

Kang, Ming-Hsuan, and Jing-Wen Gu. "Toroidal Spectral Drawing." Axioms 11, no. 3 (March 16, 2022): 137. http://dx.doi.org/10.3390/axioms11030137.

Full text

Abstract:

We give a deterministic drawing algorithm to draw a graph onto a torus, which is based on the usual spectral drawing algorithm. For most of the well-known toroidal vertex-transitive graphs, the result drawings give an embedding of the graphs onto the torus.

APA, Harvard, Vancouver, ISO, and other styles

31

Aydın, Büşra, Nihat Akgüneş, and İsmail Naci Cangül. "On the Wiener Index of the Dot Product Graph over Monogenic Semigroups." European Journal of Pure and Applied Mathematics 13, no. 5 (December 27, 2020): 1231–40. http://dx.doi.org/10.29020/nybg.ejpam.v13i5.3745.

Full text

Abstract:

Algebraic study of graphs is a relatively recent subject which arose in two main streams: One is named as the spectral graph theory and the second one deals with graphs over several algebraic structures. Topological graph indices are widely-used tools in especially molecular graph theory and mathematical chemistry due to their time and money saving applications. The Wiener index is one of these indices which is equal to the sum of distances between all pairs of vertices in a connected graph. The graph over the nite dot product of monogenic semigroups has recently been dened and in this paper, some results on the Wiener index of the dot product graph over monogenic semigroups are given.

APA, Harvard, Vancouver, ISO, and other styles

32

Chen, Haiyan, and Fuji Zhang. "Spectral Dynamics of Graph Sequences Generated by Subdivision and Triangle Extension." Electronic Journal of Linear Algebra 32 (February 6, 2017): 454–63. http://dx.doi.org/10.13001/1081-3810.3583.

Full text

Abstract:

For a graph G and a unary graph operation X, there is a graph sequence \G_k generated by G_0=G and G_{k+1}=X(G_k). Let Sp({G_k}) denote the set of normalized Laplacian eigenvalues of G_k. The set of limit points of \bigcup_{k=0}^\infty Sp(G_k)$, $\liminf_{k\rightarrow\infty}Sp(G_k) and $\limsup_{k\rightarrow \infty}Sp(G_k)$ are considered in this paper for graph sequences generated by two operations: subdivision and triangle extension. It is obtained that the spectral dynamic of graph sequence generated by subdivision is determined by a quadratic function, which is closely related to the the well-known logistic map; while that generated by triangle extension is determined by a linear function. By using the knowledge of dynamic system, the spectral dynamics of graph sequences generated by these two operations are characterized. For example, it is found that, for any initial non-trivial graph $G$, chaos takes place in the spectral dynamics of iterated subdivision graphs, and the set of limit points is the entire closed interval [0,2].

APA, Harvard, Vancouver, ISO, and other styles

33

Simic, Slobodan, and Dragan Stevanovic. "Two shorter proofs in spectral graph theory." Publikacije Elektrotehnickog fakulteta - serija: matematika, no. 14 (2003): 94–98. http://dx.doi.org/10.2298/petf0314094s.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Stanic, Zoran. "A game based on spectral graph theory." Publikacije Elektrotehni?kog fakulteta - serija: matematika, no. 16 (2005): 88–93. http://dx.doi.org/10.2298/petf0516088s.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Das, Kinkar Ch, and Muhuo Liu. "On Two Conjectures of Spectral Graph Theory." Bulletin of the Iranian Mathematical Society 44, no. 1 (February 2018): 43–51. http://dx.doi.org/10.1007/s41980-018-0003-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Simpson, Olivia. "The geometric origins of spectral graph theory." XRDS: Crossroads, The ACM Magazine for Students 21, no. 1 (October 14, 2014): 15–17. http://dx.doi.org/10.1145/2667615.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Tait, Michael, and Josh Tobin. "Three conjectures in extremal spectral graph theory." Journal of Combinatorial Theory, Series B 126 (September 2017): 137–61. http://dx.doi.org/10.1016/j.jctb.2017.04.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Lee, S. L., and F. Y. Li. "Net sign approach in graph spectral theory." Journal of Molecular Structure: THEOCHEM 207, no. 3-4 (June 1990): 301–17. http://dx.doi.org/10.1016/0166-1280(90)85032-i.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Jog, S. R., and Raju Kotambari. "On the Adjacency, Laplacian, and Signless Laplacian Spectrum of Coalescence of Complete Graphs." Journal of Mathematics 2016 (2016): 1–11. http://dx.doi.org/10.1155/2016/5906801.

Full text

Abstract:

Coalescence as one of the operations on a pair of graphs is significant due to its simple form of chromatic polynomial. The adjacency matrix, Laplacian matrix, and signless Laplacian matrix are common matrices usually considered for discussion under spectral graph theory. In this paper, we compute adjacency, Laplacian, and signless Laplacian energy (Qenergy) of coalescence of pair of complete graphs. Also, as an application, we obtain the adjacency energy of subdivision graph and line graph of coalescence from itsQenergy.

APA, Harvard, Vancouver, ISO, and other styles

40

Belardo, Francesco, Maurizio Brunetti, and Suliman Khan. "NEPS of complex unit gain graphs." Electronic Journal of Linear Algebra 39 (December 9, 2023): 621–43. http://dx.doi.org/10.13001/ela.2023.8015.

Full text

Abstract:

A complex unit gain graph (or $\mathbb T$-gain graph) is a gain graph with gains in $\mathbb T$, the multiplicative group of complex units. Extending a classical construction for simple graphs due to Cvektovic, suitably defined noncomplete extended $p$-sums (NEPS, for short) of $\mathbb T$-gain graphs are considered in this paper. Structural properties of NEPS like balance and some spectral properties and invariants of their adjacency and Laplacian matrices are investigated, including the energy and the possible symmetry of the adjacency spectrum. It is also shown how NEPS are useful to obtain infinitely many integral graphs from the few at hands.Moreover, it is studied how NEPS of $\mathbb T$-gain graphs behave with respect to the property of being nut, i.e., having $0$ as simple adjacency eigenvalue and nowhere zero $0$-eigenvectors. Finally, a family of new products generalizing NEPS is introduced, and their few first spectral properties explored.

APA, Harvard, Vancouver, ISO, and other styles

41

Cvetkovic, Dragos, and Slobodan Simic. "Towards a spectral theory of graphs based on the signless Laplacian, III." Applicable Analysis and Discrete Mathematics 4, no. 1 (2010): 156–66. http://dx.doi.org/10.2298/aadm1000001c.

Full text

Abstract:

This part of our work further extends our project of building a new spectral theory of graphs (based on the signless Laplacian) by some results on graph angles, by several comments and by a short survey of recent results.

APA, Harvard, Vancouver, ISO, and other styles

42

Alazemi, Abdullah, Milica Andjelic, and Slobodan Simic. "On the spectral invariants of symmetric matrices with applications in the spectral graph theory." Filomat 31, no. 10 (2017): 2925–32. http://dx.doi.org/10.2298/fil1710925a.

Full text

Abstract:

We first prove a formula which relates the characteristic polynomial of a matrix (or of a weighted graph), and some invariants obtained from its principal submatrices (resp. vertex deleted subgraphs). Consequently, we express the spectral radius of the observed objects in the form of power series. In particular, as is relevant for the spectral graph theory, we reveal the relationship between spectral radius of a simple graph and its combinatorial structure by counting certain walks in any of its vertex deleted subgraphs. Some computational results are also included in the paper.

APA, Harvard, Vancouver, ISO, and other styles

43

Islam, Sk Rabiul, and Madhumangal Pal. "Hyper-Wiener index for fuzzy graph and its application in share market." Journal of Intelligent & Fuzzy Systems 41, no. 1 (August 11, 2021): 2073–83. http://dx.doi.org/10.3233/jifs-210736.

Full text

Abstract:

Topological indices have an important role in molecular chemistry, network theory, spectral graph theory and several physical worlds. Most of the topological indices are defined in a crisp graph. As fuzzy graphs are more generalization of crisp graphs, those indices have more application in fuzzy graphs also. In this article, we introduced the fuzzy hyper-Wiener index (FHWI) and studied this index for various fuzzy graphs like path, cycle, star, etc and provided some interesting bounds of FHWI for that fuzzy graph. A lower bound of FHWI is established for n-vertex connected fuzzy graph depending on strength of a strong edges. A relation between FHWI of a tree and its maximum spanning tree is established and this index is calculated for the saturated cycle. Also, at the end of the article, an application in the share market of this index is presented.

APA, Harvard, Vancouver, ISO, and other styles

44

Yin, Jun, Haixing Zhao, and Sun Xie. "Spectral Invariants and Their Application on Spectral Characterization of Graphs." Axioms 11, no. 6 (May 29, 2022): 260. http://dx.doi.org/10.3390/axioms11060260.

Full text

Abstract:

In this paper, we give a method to characterize graphs determined by their adjacency spectrum. At first, we give two parameters Π1(G) and Π2(G), which are related to coefficients of the characteristic polynomial of graph G. All connected graphs with Π1(G)∈{1,0,−1,−2,−3} and Π2(G)∈{0,−1,−2,−3} are characterized. Some interesting properties of Π1(G) and Π2(G) are also given. We then find the necessary and sufficient conditions for two classes of graphs to be determined by their adjacency spectrum.

APA, Harvard, Vancouver, ISO, and other styles

45

Nair, Aditya G., and Kunihiko Taira. "Network-theoretic approach to sparsified discrete vortex dynamics." Journal of Fluid Mechanics 768 (March 10, 2015): 549–71. http://dx.doi.org/10.1017/jfm.2015.97.

Full text

Abstract:

We examine discrete vortex dynamics in two-dimensional flow through a network-theoretic approach. The interaction of the vortices is represented with a graph, which allows the use of network-theoretic approaches to identify key vortex-to-vortex interactions. We employ sparsification techniques on these graph representations based on spectral theory to construct sparsified models and evaluate the dynamics of vortices in the sparsified set-up. Identification of vortex structures based on graph sparsification and sparse vortex dynamics is illustrated through an example of point-vortex clusters interacting amongst themselves. We also evaluate the performance of sparsification with increasing number of point vortices. The sparsified-dynamics model developed with spectral graph theory requires a reduced number of vortex-to-vortex interactions but agrees well with the full nonlinear dynamics. Furthermore, the sparsified model derived from the sparse graphs conserves the invariants of discrete vortex dynamics. We highlight the similarities and differences between the present sparsified-dynamics model and reduced-order models.

APA, Harvard, Vancouver, ISO, and other styles

46

da Silva Jr., Celso M., Renata R. Del-Vecchio, and Bruno B. Monteiro. "Relating centralities in graphs and the principal eigenvector of its distance matrix." Proyecciones (Antofagasta) 40, no. 1 (February 1, 2021): 217–37. http://dx.doi.org/10.22199/issn.0717-6279-2021-01-0014.

Full text

Abstract:

In this work a new centrality measure of graphs is presented, based on the principal eigenvector of the distance matrix: spectral closeness. Using spectral graph theory, we show some of its properties and we compare the results of this new centrality with closeness centrality. In particular, we prove that for threshold graphs these two centralities always coincide. In addition we construct an infinity family of graphs for which these centralities never coincide.

APA, Harvard, Vancouver, ISO, and other styles

47

Díaz, Roberto, and Oscar Rojo. "Effects on the distance Laplacian spectrum of graphs with clusters by adding edges." Electronic Journal of Linear Algebra 35 (November 26, 2019): 511–23. http://dx.doi.org/10.13001/ela.2019.5163.

Full text

Abstract:

All graphs considered are simple and undirected. A cluster in a graph is a pair of vertex subsets (C, S), where C is a maximal set of cardinality |C| ≥ 2 of independent vertices sharing the same set S of |S| neighbors. Let G be a connected graph on n vertices with a cluster (C, S) and H be a graph of order |C|. Let G(H) be the connected graph obtained from G and H when the edges of H are added to the edges of G by identifying the vertices of H with the vertices in C. It is proved that G and G(H) have in common n −|C| + 1 distance Laplacian eigenvalues, and the matrix having these common eigenvalues is given, if H is the complete graph on |C| vertices then ∂ −|C| + 2 is a distance Laplacian eigenvalue of G(H) with multiplicity|C| − 1, where ∂ is the transmission in G of the vertices in C. Furthermore, it is shown that if G is a graph of diameter at least 3, then the distance Laplacian spectral radii of G and G(H) are equal, and if G is a graph of diameter 2, then conditions for the equality of these spectral radii are established. Finally, the results are extended to graphs with two or more disjoint clusters.

APA, Harvard, Vancouver, ISO, and other styles

48

Ceulemans, A., E. Lijnen, P. W. Fowler, R. B. Mallion, and T. Pisanski. "Graph theory and the Jahn–Teller theorem." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 468, no. 2140 (November 30, 2011): 971–89. http://dx.doi.org/10.1098/rspa.2011.0508.

Full text

Abstract:

The Jahn–Teller (JT) theorem predicts spontaneous symmetry breaking and lifting of degeneracy in degenerate electronic states of (nonlinear) molecular and solid-state systems. In these cases, degeneracy is lifted by geometric distortion. Molecular problems are often modelled using spectral theory for weighted graphs, and the present paper turns this process around and reformulates the JT theorem for general vertex- and edge-weighted graphs themselves. If the eigenvectors and eigenvalues of a general graph are considered as orbitals and energy levels (respectively) to be occupied by electrons, then degeneracy of states can be resolved by a non-totally symmetric re-weighting of edges and, where necessary, vertices. This leads to the conjecture that whenever the spectrum of a graph contains a set of bonding or anti-bonding degenerate eigenvalues, the roots of the Hamiltonian matrix over this set will show a linear dependence on edge distortions, which has the effect of lifting the degeneracy. When the degenerate level is non-bonding, distortions of vertex weights have to be included to obtain a full resolution of the eigenspace of the degeneracy. Explicit treatments are given for examples of the octahedral graph, where the degeneracy to be lifted is forced by symmetry, and the phenalenyl graph, where the degeneracy is accidental in terms of the automorphism group.

APA, Harvard, Vancouver, ISO, and other styles

49

SALIMI, S. "STUDY OF CONTINUOUS-TIME QUANTUM WALKS ON QUOTIENT GRAPHS VIA QUANTUM PROBABILITY THEORY." International Journal of Quantum Information 06, no. 04 (August 2008): 945–57. http://dx.doi.org/10.1142/s0219749908004171.

Full text

Abstract:

In the present paper, we study the continuous-time quantum walk on quotient graphs. On such graphs, there is a straightforward reduction of the problem to a subspace that can be considerably smaller than the original one. Along the lines of reductions, by using the idea of calculation of the probability amplitudes for continuous-time quantum walk in terms of the spectral distribution associated with the adjacency matrix of graphs [Jafarizadeh and Salimi (Ann. Phys.322 (2007))], we show that the continuous-time quantum walk on original graph Γ induces a continuous-time quantum walk on quotient graph ΓH. Finally, for example, we investigate the continuous-time quantum walk on some quotient Cayley graphs.

APA, Harvard, Vancouver, ISO, and other styles

50

Huang, Hezan, and Bo Zhou. "Distance spectral radius of unicyclic graphs with fixed maximum degree." Journal of Algebra and Its Applications 19, no. 04 (May 3, 2019): 2050068. http://dx.doi.org/10.1142/s0219498820500681.

Full text

Abstract:

The distance spectral radius of a connected graph is the largest eigenvalue of its distance matrix. For integers [Formula: see text] and [Formula: see text] with [Formula: see text], we prove that among the connected graphs on [Formula: see text] vertices of given maximum degree [Formula: see text] with at least one cycle, the graph [Formula: see text] uniquely maximizes the distance spectral radius, where [Formula: see text] is the graph obtained from the disjoint star on [Formula: see text] vertices and path on [Formula: see text] vertices by adding two edges, one connecting the star center with a path end, and the other being a chord of the star.

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!