18 results on '"Adjacency matrix"'
Search Results
2. BOUNDS FOR THE α-ADJACENCY ENERGY OF A GRAPH.
- Author
-
SHABAN, REZWAN UL, IMRAN, MUHAMMAD, and GANIE, HILAL A.
- Subjects
GRAPH theory ,EIGENVALUES ,CONVEX functions ,RAYLEIGH quotient ,GRAPH connectivity - Abstract
For the adjacency matrix A(G) and diagonal matrix of the vertex degrees D(G) of a simple graph G, the A(G) matrix is the convex combinations of D(G) and A(G), and is defined as A(G) = D(G)+(1)A(G), for 0 n be the eigenvalues of A(G) (which we call -adjacency eigenvalues of the graph G). The generalized adjacency energy also called -adjacency energy of the graph G is defined as EA (G) = is the average vertex degree, m is the size and n is the order of G. The -adjacency energy of a graph G merges the theory of energy (adjacency energy) and the signless Laplacian energy, as EA0 (G) = E (G) and 2E A 12 (G) = QE(G), where E (G) is the energy and QE(G) is the signless Laplacian energy of G. In this paper, we obtain some new upper and lower bounds for the generalized adjacency energy of a graph, in terms of different graph parameters like the vertex covering number, the Zagreb index, the number of edges, the number of vertices, etc. We characterize the extremal graphs attained these bounds. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Some Properties of Double Domination in Vague Graphs with an Application.
- Author
-
Rao, Yongsheng, Cai, Ruiqi, Talebi, Ali Asghar, and Mojahedfar, Masomeh
- Subjects
- *
GRAPH theory , *DOMINATING set , *FUZZY graphs , *ENERGY consumption , *SYMMETRY - Abstract
This paper is devoted to the study of the double domination in vague graphs, and it is a contribution to the Special Issue "Advances in graph theory and Symmetry/Asymmetry" of Symmetry. Symmetry is one of the most important criteria that illustrate the structure and properties of fuzzy graphs. It has many applications in dominating sets and helps find a suitable place for construction. Vague graphs (VGs), which are a family of fuzzy graphs (FGs), are a well-organized and useful tool for capturing and resolving a range of real-world scenarios involving ambiguous data. In the graph theory, a dominating set (DS) for a graph G * = (X , E) is a subset D of the vertices X so that every vertex which is not in D is adjacent to at least one member of D. The subject of energy in graph theory is one of the most attractive topics serving a very important role in biological and chemical sciences. Hence, in this work, we express the notion of energy on a dominating vague graph (DVG) and also use the concept of energy in modeling problems related to DVGs. Moreover, we introduce a new notion of a double dominating vague graph (DDVG) and provide some examples to explain various concepts introduced. Finally, we present an application of energy on DVGs. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. Some New Bounds for α -Adjacency Energy of Graphs.
- Author
-
Zhang, Haixia and Zhang, Zhuolin
- Subjects
- *
GRAPH theory , *EIGENVALUES , *STRUCTURAL analysis (Engineering) , *ENERGY consumption - Abstract
Let G be a graph with the adjacency matrix A (G) , and let D (G) be the diagonal matrix of the degrees of G. Nikiforov first defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , 0 ≤ α ≤ 1 , which shed new light on A (G) and Q (G) = D (G) + A (G) , and yielded some surprises. The α − adjacency energy E A α (G) of G is a new invariant that is calculated from the eigenvalues of A α (G) . In this work, by combining matrix theory and the graph structure properties, we provide some upper and lower bounds for E A α (G) in terms of graph parameters (the order n, the edge size m, etc.) and characterize the corresponding extremal graphs. In addition, we obtain some relations between E A α (G) and other energies such as the energy E (G) . Some results can be applied to appropriately estimate the α -adjacency energy using some given graph parameters rather than by performing some tedious calculations. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. Spectrum of prism graph and relation with network related quantities.
- Author
-
Raza, Ali, Munir, Mobeen, Abbas, Tasawar, Eldin, Sayed M., and Khan, Ilyas
- Subjects
GRAPH theory ,STABILITY theory ,POLYHEDRA ,SPANNING trees ,RADIUS (Geometry) - Abstract
Spectra of network related graphs have numerous applications in computer sciences, electrical networks and complex networks to explore structural characterization like stability and strength of these different real-world networks. In present article, our consideration is to compute spectrum based results of generalized prism graph which is well-known planar and polyhedral graph family belongs to the generalized Petersen graphs. Then obtained results are applied to compute some network related quantities like global mean-first passage time, average path length, number of spanning trees, graph energies and spectral radius. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
6. Graph Theory: A Lost Component for Development in Nigeria.
- Author
-
Babarinsa, Olayiwola
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICS , *RESEARCH - Abstract
Graph theory is one of the neglected branches of mathematics in Nigeria but with the most applications in other fields of research. This article shows the paucity, importance, and necessity of graph theory in the development of Nigeria. The adjacency matrix and dual graph of the Nigeria map were presented. The graph spectrum and energies (graph energy and Laplacian energy) of the dual graph were computed. Then the chromatic number, maximum degree, minimum spanning tree, graph radius, and diameter, the Eulerian circuit and Hamiltonian paths from the dual graph were obtained and discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
7. Aα matrix of commuting graphs of non-abelian groups.
- Author
-
Rather, Bilal A., Ali, Fawad, Ullah, Nasim, Mohammad, Al-Sharef, Din, Anwarud, and Sehra
- Subjects
EIGENVALUES ,EIGENANALYSIS ,EXPONENTIAL stability ,LAPLACIAN matrices ,GRAPH theory - Abstract
For a finite group G and a subset X≠ 0 of G, the commuting graph, indicated by G = C(G, X), is the simple connected graph with vertex set X and two distinct vertices x and y are edge connected in G if and only if they commute in X. The Aα matrix of G is specified as A
α (G) = αD(G) + (1-α)A(G), α ∈ [0, 1], where D(G) is the diagonal matrix of vertex degrees while A(G) is the adjacency matrix of G. In this article, we investigate the Aα matrix for commuting graphs of finite groups and we also find the Aα eigenvalues of the dihedral, the semidihedral and the dicyclic groups. We determine the upper bounds for the largest Aα eigenvalue for these graphs. Consequently, we get the adjacency eigenvalues, the Laplacian eigenvalues, and the signless Laplacian eigenvalues of these graphs for particular values of α. Further, we show that these graphs are Laplacian integral. [ABSTRACT FROM AUTHOR]- Published
- 2022
- Full Text
- View/download PDF
8. Two upper bounds on the Aα-spectral radius of a connected graph.
- Author
-
Pirzada, Shariefuddin
- Subjects
- *
GRAPH theory , *GEOMETRIC vertices , *EIGENVALUES , *SUBGRAPHS , *GENERALIZATION - Abstract
If A(G) and D(G) are respectively the adjacency matrix and the diagonal matrix of vertex degrees of a connected graph G, the generalized adjacency matrix Aα(G) is defined as Aα(G) = α D(G) + (1 - α) A(G), where 0 ≤ α ≤ 1. The Aα (or generalized) spectral radius λ(Aα(G)) (or simply λα) is the largest eigenvalue of Aα(G). In this paper, we show that λα ≤ α Δ + (1 - α)√ 2m ( 1 - 1/ω), where m, Δ and ω = ω(G) are respectively the size, the largest degree and the clique number of G. Further, if G has order n, then we show that ... where di and mi are respectively the degree and the average 2-degree of the vertex Vi. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
9. Change of nullity of a graph under two operations.
- Author
-
Mohiaddin, Gohdar H. and Sharaf, Khidir R.
- Subjects
- *
INDEPENDENT variables , *GRAPH theory , *EIGENVALUES , *MULTIPLICITY (Mathematics) - Abstract
The nullity of a graph G is the multiplicity of zero as an eigenvalue of its adjacency matrix. An assignment of weights to the vertices of a graph, that satisfies a zero sum condition over the neighbors of each vertex, and uses maximum number of independent variables is denoted by a high zero sum weighting of the graph. This applicable tool is used to determine the nullity of the graph. Two types of graphs are defined, and the change of their nullities is studied, namely, the graph G+ab constructed from G by adding a new vertex ab which is joint to all neighbors of both vertices a and b of G, and G•ab which is obtained from G+ab by removing both vertices a and b. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
10. A spherical evolution algorithm with two-stage search for global optimization and real-world problems.
- Author
-
Wang, Yirui, Cai, Zonghui, Guo, Lijun, Li, Guoqing, Yu, Yang, and Gao, Shangce
- Subjects
- *
GLOBAL optimization , *SEARCH algorithms , *TIME complexity , *GRAPH theory , *COMPUTATIONAL complexity - Abstract
This paper proposes a spherical evolution algorithm with two-stage search. Spherical search and hypercube search are combined to achieve individuals' evolution. A self-adaptive Gaussian scale factor and a variable scale factor are designed to adaptively control individuals' spherical and hypercube search area according to their search situations. Two search stages frequently switch with four search cases to enhance the balance between exploration and exploitation processes. A directed adjacency matrix is devised to analyze the relationship among individuals from the perspective of graph theory. Experiments compare the proposed algorithm with five algorithms with distinctive search patterns on twenty nine CEC2017 benchmark functions. The diversity analysis and graph theory analysis show the good population diversity and effective information spreading of the proposed algorithm. Twenty two real-world problems evaluate the practicality and optimization ability of the proposed algorithm. Finally, the computational time complexity demonstrates that the proposed algorithm is more efficient than the original spherical evolution algorithm. • A spherical evolution algorithm with two-stage search is proposed. • Spherical search and hypercube search are combined to adaptively guide individuals' evolution. • A directed adjacency matrix is firstly introduced to analyze the relationship among individuals. • Functions and real-world problems verify the superior search performance of the proposed algorithm. • The computational efficiency of the proposed algorithm is enhanced. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
11. A Poisson multi-Bernoulli mixture filter for tracking multiple resolvable group targets.
- Author
-
Zhou, Yusong, Zhao, Jin, Wu, Sunyong, and Liu, Chang
- Subjects
- *
FILTERS & filtration , *GRAPH theory , *MIXTURES , *FUNCTIONALS , *DYNAMIC models - Abstract
This paper presents a novel Poisson multi-Bernoulli mixture (PMBM) filter for tracking multiple resolvable group targets (MRGT) based on graph theory. Firstly, the number of groups and the relationships between members within the group are modelled by the adjacency matrix. Then, considering that a single dynamic evolution model is insufficient to guarantee stable tracking performance for group targets, the virtual leader-follower model (VLFM) is introduced to predict the evolution trend of unknown and potentially detected targets, respectively. Furthermore, we prove the conjugation of the proposed algorithm with the probability generating functionals (PGF) and give a detailed implementation of the Gaussian mixture (GM). Based on the coexistence scenario of splitting, merging and non-linear motion of the group targets, the simulation results show the effectiveness of the proposed algorithm in comparison with the existing methods. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
12. Cospectral graphs : What properties are determined by the spectrum of a graph?
- Author
-
Sundström, Erik
- Subjects
graphs ,graph spectrum ,Matematik ,cospectral graphs ,adjacency matrix ,spectra ,graph theory ,adjacency matrices ,graph spectra ,graph ,spectral graph theory ,Mathematics ,spectrum - Abstract
This paper was written as a bachelor thesis in mathematics. We study adjacency matrices and their eigenvalues to investigate what properties of the corresponding graphs can be determined by those eigenvalues, the spectrum of the graph. The question of which graphs are uniquely determined by their spectra is also covered. Later on we study some methods of finding examples of graphs with shared spectra, also referred to as cospectral graphs.
- Published
- 2023
13. Algebraic methods in graph theory
- Author
-
Kurtoić, Tomislav and Kožić, Slaven
- Subjects
linearna algebra ,Laplace matrix ,incidence matrix ,adjacency matrix ,resistance matrix ,matrica susjedstva ,graph theory ,matrica otpora ,matrica udaljenosti stabla ,teorija grafova ,linear algebra ,PRIRODNE ZNANOSTI. Matematika ,Laplaceova matrica ,distance matrix of a tree ,NATURAL SCIENCES. Mathematics ,matrica incidencije - Abstract
Glavna svrha ovog rada je pokazati na koji način su povezana područja linearne algebre i teorije grafova te kako njihovu vezu možemo iskoristiti za rješavanje problema u stvarnom životu. U prvom poglavlju navodimo definicije, teoreme i rezultate iz linearne algebre i teorije grafova koji su nužni za shvaćanje glavnog dijela rada. Drugo, treće i četvrto poglavlje bavi se proučavanjem matrice susjedstva, matrice incidencije i Laplaceove matrice. Definiramo svaku od navedenih matrica, na stvarnim primjerima prikazujemo načine njihovog određivanja te prezentiramo njihove primjene u proučavanju pripadnih grafova. U petom i šestom poglavlju promatramo matricu udaljenosti stabla i matricu otpora. Definiramo navedene matrice i proučavamo njihova svojstva i primjene. Poseban naglasak je dan na rezultate vezane uz njihove svojstvene vrijednosti, determinante i povezanosti s Laplaceovom matricom. The main purpose of this thesis is to show the connections between linear algebra and graph theory and their applications to solving real life problems. In the first chapter we give basic definitions, theorems and results from linear algebra and graph theory which are vital for further understanding of the thesis. In chapters two, three and four we are focused on adjacency and incidence matrices along with the Laplacian matrix. We define each of these matrices, we show how to determine them by using real life examples and we present their applications to the study of the underlying graphs. In the last two chapters, chapters five and six, we examine the distance matrix of a tree and the resistance matrix. We introduce the aforementioned matrices and study their properties and applications. Special emphasis is given to the results concerning their eigenvalues, determinants and connections with the Laplacian matrix.
- Published
- 2022
14. Change of nullity of a graph under two operations
- Author
-
Khidir R. Sharaf and Gohdar H. Mohiaddin
- Subjects
Combinatorics ,Mathematics::Combinatorics ,Multidisciplinary ,Spectrum (functional analysis) ,Zero (complex analysis) ,Order (group theory) ,Graph theory ,Mathematics::Differential Geometry ,Adjacency matrix ,Multiple edges ,Eigenvalues and eigenvectors ,Vertex (geometry) ,Mathematics - Abstract
Two adjacent or non-adjacent vertices of a graph G are said to be identified, if they are combined to form one vertex whose neighbor is the union of their neighborhoods (ignoring any loops or multiple edges formed). The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. A graph is a nullity critical if identifying any pair of vertices decreases or increases the nullity. On the other hand, a graph is a nullity- stable if identifying any pair of distinct vertices leaves the nullity unchanged. It is proved that in general, identifying any pair of distinct vertices cannot increase or decrease the nullity by at most 2. Also, nut graphs are constructed from old ones with smaller order and larger maximum degree. Our main tools to obtain such results are the interlacing theorem, the end vertex Lemma, the assignment of appropriate weights to the vertices which are going to be identified in a high zero sum weighting of the graph. The distance between vertices with the same weight plays an important role in the study of the change in the nullity on vertex identification in a graph.
- Published
- 2021
15. On fast enumeration of maximal cliques in large graphs
- Author
-
Bowen Xiong, Yi Zhou, Yan Jin, Yangming Zhou, and Kun He
- Subjects
Theoretical computer science ,Artificial Intelligence ,Computer science ,General Engineering ,Benchmark (computing) ,Enumeration ,Adjacency list ,Graph theory ,Adjacency matrix ,Clique (graph theory) ,Upper and lower bounds ,Degeneracy (graph theory) ,Computer Science Applications - Abstract
Maximal Clique Enumeration (MCE) is a fundamental and challenging problem in graph theory and various network applications. Numerous algorithms have been proposed in the past decades, however, only a few of them focus on improving the practical efficiency in large graphs. To this end, we propose an efficient algorithm called FACEN based on the Bron–Kerbosch framework. To optimize the memory and time consumption, we apply a hybrid data structure with adjacency list and partial adjacency matrix, and introduce a dynamic pivot selection rule based on the degeneracy order. FACEN is evaluated on a total of 64 benchmark instances from various sources. Computational results indicate that the proposed algorithm is highly competitive with the current leading MCE methods. In particular, our algorithm is able to enumerate all maximal cliques on the tested real-world social networks with millions of vertices and edges. For very large graphs, we provide an additional experiment for solving the MCE variant with lower bound, and investigate the benefits of FACEN.
- Published
- 2022
16. Adjacency eigenvalues of graphs without short odd cycles
- Author
-
Wanting Sun, Shuchao Li, and Yuantian Yu
- Subjects
Discrete mathematics ,Spectral radius ,Graph theory ,Girth (graph theory) ,Type (model theory) ,Upper and lower bounds ,Theoretical Computer Science ,Combinatorics ,Integer ,Computer Science::Discrete Mathematics ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Adjacency list ,Combinatorics (math.CO) ,Adjacency matrix ,05C50, 05C35 ,Mathematics - Abstract
It is well known that spectral Tur\'{a}n type problem is one of the most classical {problems} in graph theory. In this paper, we consider the spectral Tur\'{a}n type problem. Let $G$ be a graph and let $\mathcal{G}$ be a set of graphs, we say $G$ is \textit{$\mathcal{G}$-free} if $G$ does not contain any element of $\mathcal{G}$ as a subgraph. Denote by $\lambda_1$ and $\lambda_2$ the largest and the second largest eigenvalues of the adjacency matrix $A(G)$ of $G,$ respectively. In this paper we focus on the characterization of graphs without short odd cycles according to the adjacency eigenvalues of the graphs. Firstly, an upper bound on $\lambda_1^{2k}+\lambda_2^{2k}$ of $n$-vertex $\{C_3,C_5,\ldots,C_{2k+1}\}$-free graphs is established, where $k$ is a positive integer. All the corresponding extremal graphs are identified. Secondly, a sufficient condition for non-bipartite graphs containing an odd cycle of length at most $2k+1$ in terms of its spectral radius is given. At last, we characterize the unique graph having the maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3,$ which solves an open problem proposed by Lin, Ning and Wu [Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258-270]., Comment: 15 pages. It is accepted by Discrete Mathematics
- Published
- 2022
17. The effect of fish life-history structures on the topologies of aquatic food webs
- Author
-
Anna Kuparinen, Milko Vesterinen, and Tommi Perälä
- Subjects
0106 biological sciences ,adjacency matrix ,Computer science ,graph theory ,Network theory ,Network topology ,010603 evolutionary biology ,01 natural sciences ,03 medical and health sciences ,symbols.namesake ,life-history structure ,niche model ,Statistics ,Ecology, Evolution, Behavior and Systematics ,kalat ,030304 developmental biology ,Apex predator ,Trophic level ,0303 health sciences ,Biomass (ecology) ,food web ,Ecology ,verkkoteoria ,vesiekosysteemit ,Food web ,Pearson product-moment correlation coefficient ,ekologinen lokero ,elinkierto ,random network ,symbols ,Allometry ,matemaattiset mallit ,ravintoverkot - Abstract
Biological organisms can vastly change their ecological functionality due to changes in body size and diet across their life. Consequently, it has been increasingly recognized that to attain sufficient biological realism, food webs may need to include life-history structures. The objective of the work is to study theoretically whether and how the inclusion of life-history structures affects the food web topology. Topological research was done by applying network theory metrics for three different food web types with two different sizes that were generated by using the niche-model. The dynamical modeling was performed by using an allometric trophic network modeling approach. The different types included food webs with and without the life-history structure for top predators (three fish species). Each of the generated random food webs analyzed reached dynamical equilibrium conditions with respect to the biomass densities of the species prior to the network analysis. Our results suggest that food web topologies are not largely affected by the inclusion of age- or stage-structure. In addition to the topological study, the relationship between the metrics used in this work was investigated by using Pearson correlation. Results suggested that only a few pairs of metrics had a strong positive correlation and most of the correlations did not change with food web size or type. peerReviewed
- Published
- 2021
18. Network Theory and Switching Behaviors: A User Guide for Analyzing Electronic Records Databases
- Author
-
Marco Raglianti, Giorgio Gronchi, and Fabio Giovannelli
- Subjects
Database ,Computer Networks and Communications ,Computer science ,Generalization ,Control (management) ,health ,Graph theory ,Information technology ,Network theory ,Python (programming language) ,T58.5-58.64 ,computer.software_genre ,Field (computer science) ,network theory ,switching behaviors ,Adjacency matrix ,Cluster analysis ,computer ,database ,computer.programming_language - Abstract
As part of studies that employ health electronic records databases, this paper advocates the employment of graph theory for investigating drug-switching behaviors. Unlike the shared approach in this field (comparing groups that have switched with control groups), network theory can provide information about actual switching behavior patterns. After a brief and simple introduction to fundamental concepts of network theory, here we present (i) a Python script to obtain an adjacency matrix from a records database and (ii) an illustrative example of the application of network theory basic concepts to investigate drug-switching behaviors. Further potentialities of network theory (weighted matrices and the use of clustering algorithms), along with the generalization of these methods to other kinds of switching behaviors beyond drug switching, are discussed.
- Published
- 2021
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.