185 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. Minimum eigenvalue of the complement of tricyclic graphs with n-4 pendent vertexes
- Author
-
Hongjuan JU and Yingjie LEI
- Subjects
graph theory ,tricyclic graph ,adjacency matrix ,the minimum eigenvalue ,pendent vertexes ,complement graph ,Technology - Abstract
In order to discuss the minimum eigenvalue of adjacency matrix in the class of complementary graphs of the tricyclic graph with a given order of n and n-4 pendent vertexes, the unique graph whose minimum eigenvalue reaches the minimum is characterized. Based on the simple undirected connected graph,the minimum eigenvalue of the graph is studied from the structure of the complement graph, and the minimum eigenvalue of the adjacency matrix in the complement graph class of the tricyclic graph with a given order of n and n-4 pendent vertexes reaches the minimum unique graph when the value is λ( G ( 85;P](n-4)/2,(n-4)/2[XC符号2.eps;%90%90;P])C)[WTBZ]. The result shows that the associative graph adjacency matrix is a matrix which represents the adjacency between vertices, and its minimum eigenvalue is the minimum eigenvalue of graph, which can describe the essential properties of graph well. The conclusion from this research shows that the minimum eigenvalue of the complement graph of the tricyclic graph with a given order of n and n-4 pendent vertexes reaches the minimum eigenvalue, which provides certain reference for further study of the minimum eigenvalue of the adjacency matrix in the complement graph class.
- Published
- 2019
- Full Text
- View/download PDF
11. A Greedy Technique Based Improved Approach to Solve Graph Colouring Problem.
- Author
-
Shukla, Ajay Narayan, Bharti, Vishal, and Garg, M. L.
- Subjects
GRAPH coloring ,GRAPH theory ,IMAGE processing ,IMAGING systems ,MATRICES (Mathematics) - Abstract
Graph colouring problem is a well-known NP-class optimization problem, studied due to a lot of applications in various real-world problems. Some of these applications are: register allocation, image processing and communication networks. There are various techniques suggested by the researchers to solve the problem which is either exact or approximate in nature. In this paper, a new greedy technique, based on degrees of vertices in the graph is presented to solve the graph colouring problem in an improved manner. The technique involves the use of adjacency matrix along with another matrix generated for the set of possible colours for each vertex in the graph. The generated colour matrix is used to assign the colours among the vertices in the graph based on decreasing degrees of the vertices. Several DIMACS colouring instances solved using the suggested approach in the article and compared with some contemporary techniques for the performance and proves compatible and having better execution time with compared technique. The obtained colouing results are mostly optimal colour values corresponding to the examined colouring instances of the graph. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
12. 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
13. The magnetic discrete Laplacian inferred from the Gauß–Bonnet operator and application.
- Author
-
Athmouni, Nassim, Baloudi, Hatem, Damak, Mondher, and Ennaceur, Marwa
- Subjects
- *
WEIGHTED graphs , *GRAPH theory , *SPECTRAL theory - Abstract
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]
- Published
- 2021
- Full Text
- View/download PDF
14. Null Spaces Dimension of the Eigenvalue -1 in a Graph
- Author
-
Gohdar H. Mohiaddin and Khidir R. Sharaf
- Subjects
graph theory ,high zero sum weighting ,adjacency matrix ,nullity ,corona product ,Science - Abstract
In geographic, the eigenvalues and eigenvectors of transportation network provides many informations about its connectedness. It is proven that the more highly connected in a transportation network G has largest eigenvalue and hence more multiple occurrences of the eigenvalue -1. For a graph G with adjacency matrix A, the multiplicity of the eigenvalue -1 equals the dimension of the null space of the matrix A + I. In this paper, we constructed a high closed zero sum weighting of G and by which its proved that, the dimension of the null space of the eigenvalue -1 is the same as the number of independent variables used in a non-trivial high closed zero sum weighting of the graph. Multiplicity of -1 as an eigenvalue of known graphs and of corona product of certain classes of graphs are determined and two classes of -1- nut graphs are constructed.
- Published
- 2019
- Full Text
- View/download PDF
15. 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
16. A Unified Framework for Structured Graph Learning via Spectral Constraints.
- Author
-
Kumar, Sandeep, Jiaxi Ying, de M. Cardoso, Jose Vinícius, and Palomar, Daniel P.
- Subjects
- *
COMBINATORIAL optimization , *GRAPH theory , *REGULAR graphs , *SPECTRAL theory , *LAPLACIAN matrices , *NP-hard problems , *CONSTRAINT programming - Abstract
Graph learning from data is a canonical problem that has received substantial attention in the literature. Learning a structured graph is essential for interpretability and identification of the relationships among data. In general, learning a graph with a specific structure is an NP-hard combinatorial problem and thus designing a general tractable algorithm is challenging. Some useful structured graphs include connected, sparse, multi-component, bipartite, and regular graphs. In this paper, we introduce a unified framework for structured graph learning that combines Gaussian graphical model and spectral graph theory. We propose to convert combinatorial structural constraints into spectral constraints on graph matrices and develop an optimization framework based on block majorization-minimization to solve structured graph learning problem. The proposed algorithms are provably convergent and practically amenable for a number of graph based applications such as data clustering. Extensive numerical experiments with both synthetic and real data sets illustrate the effectiveness of the proposed algorithms. An open source R package containing the code for all the experiments is available at https://CRAN.R-project.org/package=spectralGraphTopology. [ABSTRACT FROM AUTHOR]
- Published
- 2020
17. 具有n-4个悬挂点的三圈图补图的最小特征值.
- Author
-
剧宏娟 and 雷英杰
- Subjects
GRAPH theory ,MAXIMA & minima ,MATRICES (Mathematics) - Abstract
Copyright of Journal of Hebei University of Science & Technology is the property of Hebei University of Science & Technology, Journal of Hebei University of Science & Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 2019
- Full Text
- View/download PDF
18. 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
19. Uniquely pressable graphs: Characterization, enumeration, and recognition.
- Author
-
Cooper, Joshua and Whitlatch, Hays
- Subjects
- *
GRAPHIC methods , *GRAPH theory , *ALGORITHMS , *MATHEMATICAL models , *NUMERICAL analysis - Abstract
Abstract Motivated by the study of genomes evolving by reversals, we consider pseudograph transformations known as "pressing sequences". In particular, we address the question of when a graph has precisely one pressing sequence resulting in the empty graph, thus answering an question from Cooper and Davis (2015) [13]. We characterize such "uniquely pressable" graphs, count the number of them on a given number of vertices, and provide a polynomial-time recognition algorithm. We conclude with several open questions. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
20. On graphs with prescribed star complements.
- Author
-
Yuan, Xiying, Zhao, Qingqing, Liu, Lele, and Chen, Hongyan
- Subjects
- *
GRAPH theory , *MULTIPLICITY (Mathematics) , *LOCALIZATION (Mathematics) , *FRACTIONAL calculus , *TREE graphs - Abstract
Abstract Let μ be an eigenvalue of a simple graph G with multiplicity k ≥ 1. A star complement for μ in G is an induced subgraph of G of order n − k with no eigenvalue μ. In this paper, we study the maximal graphs with the star S m as a star complement for −2. The maximal graphs with S 3 , S 4 , S 13 and S 21 as a star complement for −2 are described. We also describe the regular graphs with K 2 , s (s ≥ 2) as a star complement for an eigenvalue μ. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
21. Energy of a vertex.
- Author
-
Arizmendi, Octavio, Fernandez Hidalgo, Jorge, and Juarez-Romero, Oliver
- Subjects
- *
MATHEMATICAL equivalence , *CONTINUITY , *GRAPH theory , *GEOMETRIC vertices , *SPECTRAL geometry , *FINITE groups - Abstract
In this paper we develop the concept of energy of a vertex introduced in Arizmendi and Juarez-Romero (2018). We derive basic inequalities, continuity properties, give examples and extend the definition to locally finite graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
22. Spectral characterizations of anti-regular graphs.
- Author
-
Aguilar, Cesar O., Lee, Joon-yeob, Piato, Eric, and Schweitzer, Barbara J.
- Subjects
- *
REGULAR graphs , *CHEBYSHEV polynomials , *EIGENVALUES , *GRAPH theory , *MATRICES (Mathematics) , *ASYMPTOTIC distribution - Abstract
We study the eigenvalues of the unique connected anti-regular graph A n . Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] contains only the trivial eigenvalues λ = − 1 or λ = 0 , and any closed interval strictly larger than Ω will contain eigenvalues of A n for all n sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as n increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of A n , namely, as n increases the eigenvalues are (approximately) symmetric about the number − 1 2 . We also obtain an asymptotic distribution of the eigenvalues as n → ∞ . Finally, the relationship between the eigenvalues of A n and the eigenvalues of a general threshold graph is discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
23. Numerical Range of Simple Graphs and Some Bounds for their Eigenvalues.
- Author
-
Tajarrod, M. and Sistani, T.
- Subjects
- *
CHARTS, diagrams, etc. , *MATRICES (Mathematics) , *APPROXIMATION algorithms , *EIGENVALUE equations , *SUBGRAPHS - Abstract
The numerical range of a simple graph G, named F(G), is the numerical range of its adjacency matrix A(G). The main purpose of this paper is to approximate F(G). Then, using this approximation, bounds for the largest and the smallest eigenvalues of G are proposed. In fact, lower bounds for the largest eigenvalues of G are presented in terms of disjoint induced subgraphs of G and the numerical range of the square of A(G). [ABSTRACT FROM AUTHOR]
- Published
- 2018
24. 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
25. On the α-index of graphs with pendent paths.
- Author
-
Nikiforov, Vladimir and Rojo, Oscar
- Subjects
- *
GRAPH theory , *LINEAR algebra , *LAPLACIAN operator , *MATRICES (Mathematics) , *LAPLACIAN matrices - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper presents some extremal results about the spectral radius ρ α ( G ) of A α ( G ) that generalize previous results about ρ 0 ( G ) and ρ 1 / 2 ( G ) . In particular, write B p , q , r be the graph obtained from a complete graph K p by deleting an edge and attaching paths P q and P r to its ends. It is shown that if α ∈ [ 0 , 1 ) and G is a graph of order n and diameter at least k , then ρ α ( G ) ≤ ρ α ( B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ ) , with equality holding if and only if G = B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ . This result generalizes results of Hansen and Stevanović [5] , and Liu and Lu [7] . [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
26. On the Aα-spectral radius of a graph.
- Author
-
Xue, Jie, Lin, Huiqiu, Liu, Shuting, and Shu, Jinlong
- Subjects
- *
GRAPH theory , *GRAPHIC methods , *MATRICES (Mathematics) , *COMPLEX matrices , *LINEAR algebra - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G . In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d , and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
27. On the Aα-characteristic polynomial of a graph.
- Author
-
Liu, Xiaogang and Liu, Shunyi
- Subjects
- *
POLYNOMIALS , *GRAPH theory , *GEOMETRIC vertices , *COEFFICIENTS (Statistics) - Abstract
Let G be a graph with n vertices, and let A ( G ) and D ( G ) denote respectively the adjacency matrix and the degree matrix of G . Define A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) for any real α ∈ [ 0 , 1 ] . The A α -characteristic polynomial of G is defined to be det ( x I n − A α ( G ) ) = ∑ j c α j ( G ) x n − j , where det ( ⁎ ) denotes the determinant of ⁎, and I n is the identity matrix of size n . The A α -spectrum of G consists of all roots of the A α -characteristic polynomial of G . A graph G is said to be determined by its A α -spectrum if all graphs having the same A α -spectrum as G are isomorphic to G . In this paper, we first formulate the first four coefficients c α 0 ( G ) , c α 1 ( G ) , c α 2 ( G ) and c α 3 ( G ) of the A α -characteristic polynomial of G . And then, we observe that A α -spectra are much efficient for us to distinguish graphs, by enumerating the A α -characteristic polynomials for all graphs on at most 10 vertices. To verify this observation, we characterize some graphs determined by their A α -spectra. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
28. Signed graphs with cut points whose positive inertia indexes are two.
- Author
-
Wang, Xinlei, Wong, Dein, and Tian, Fenglei
- Subjects
- *
LINEAR algebra , *GEOMETRIC vertices , *GRAPH theory , *LAPLACIAN matrices , *GRAPHIC methods - Abstract
A signed graph G σ consists of an underlying graph G and a sign function σ , which assigns each edge uv of G a sign σ ( u v ) , either positive or negative. The adjacency matrix of G σ is defined as A ( G σ ) = ( a u , v σ ) with a u , v σ = σ ( u v ) a u , v , where a u , v = 1 if u , v ∈ V ( G ) are adjacent, and a u , v = 0 otherwise. The positive inertia index of G σ , written as p ( G σ ) , is defined to be the number of positive eigenvalues of A ( G σ ) . Recently, Yu et al. (2016) [12] characterized the signed graphs G σ with pendant vertices such that p ( G σ ) = 2 . In this paper, we extend the above work to a more general case, characterizing the signed graphs G σ with cut points whose positive inertia index is 2. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
29. On the determinant of the Laplacian matrix of a complex unit gain graph.
- Author
-
Wang, Yi, Gong, Shi-Cai, and Fan, Yi-Zheng
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *MATHEMATICAL complexes , *UNDIRECTED graphs , *PATHS & cycles in graph theory - Abstract
Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
30. Improved McClelland and Koolen-Moulton bounds for the energy of graphs.
- Author
-
Sridhara, G., Kanna, M. R. Rajesh, Jagadeesh, R., and Cangul, I. N.
- Subjects
- *
GRAPH theory , *CARBON compounds , *GRAPHIC methods , *ELECTRONS , *CHEMISTRY - Abstract
Given a graph G with n vertices and m edges, the term energy of graph E(G) was introduced by Gutman in chemistry, due to its relevance to the total π ― electron energy of carbon compounds. In 1971 McClelland obtained both lower and upper bounds for π 8213; electron energy. An improved upper bound was obtained by Koolen-Moulton in 2001. The lower and upper bounds for E(G) obtained in this paper are better than McClelland and Koolen-Moulton bounds. Also we obtained an upper bound for graph energy in terms of n as E(G) ≤ n/2[ 1 + √ n-2/2]. [ABSTRACT FROM AUTHOR]
- Published
- 2018
31. Minimizing graph of the connected graphs whose complements are bicyclic with two cycles.
- Author
-
JAVAID, Muhammad
- Subjects
- *
BICYCLIC compounds , *GRAPH connectivity , *GRAPHIC methods , *GRAPH theory , *GEOMETRIC vertices , *EIGENVALUES - Abstract
In a certain class of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum. A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. In this paper, we characterize the minimizing graph among all the connected graphs that belong to a class of graphs whose complements are bicyclic with two cycles. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
32. The spectra of subKautz and cyclic Kautz digraphs.
- Author
-
Dalfó, C.
- Subjects
- *
DIRECTED graphs , *GRAPH theory , *POLYNOMIALS , *INTEGERS , *MATHEMATICAL models - Abstract
Kautz digraphs K ( d , ℓ ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz C K ( d , ℓ ) and the subKautz s K ( d , 2 ) digraphs were recently introduced by Böhmová, Huemer and the author. In this paper we propose a new method to obtain the complete spectra of subKautz s K ( d , 2 ) and cyclic Kautz C K ( d , 3 ) digraphs, for all d ≥ 3 , through the Hoffman–McAndrew polynomial and regular partitions. This approach can be useful to find the spectra of other families of digraphs with high regularity. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
33. Self-inverse unicyclic graphs and strong reciprocal eigenvalue property.
- Author
-
Bapat, R.B., Panda, S.K., and Pati, S.
- Subjects
- *
GRAPH theory , *MATRICES (Mathematics) , *SINGULAR integrals , *ISOMORPHISM (Mathematics) , *EIGENVALUES - Abstract
We consider only simple graphs. A graph G is said to be nonsingular if its adjacency matrix A ( G ) is nonsingular. The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G ) via a diagonal matrix of ±1s. An invertible graph G is said to be a self-inverse graph if G is isomorphic to its inverse. Let H be the class of connected bipartite graphs with unique perfect matchings. We consider the problem of characterizing the graphs in H which are self-inverse graphs. In this article, we answer this problem for the class of unicyclic graphs. The study of the strong reciprocal eigenvalue property is closely related to the study of graphs which are isomorphic to their inverse graphs. A nonsingular graph G is said to satisfy the property (SR) if the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) and they both have the same multiplicities. In this article, we show that if a unicyclic graph G in H has property (SR), then G is invertible and the inverse graph of G is unicyclic. As an application, we show that a noncorona unicyclic graph in H with property (SR) can have one of the five specified structures. Finally, our discussions lead to the following problem. Does there exist a unicyclic graph G ∈ H which has property (SR) but G is not self-inverse? [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
34. On some graphs which satisfy reciprocal eigenvalue properties.
- Author
-
Panda, S.K. and Pati, S.
- Subjects
- *
GRAPH theory , *EIGENVALUES , *BIPARTITE graphs , *MATRICES (Mathematics) , *VERTEX operator algebras - Abstract
We consider only simple graphs. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. On the class H g of such graphs G the equivalence of the following statements are known. i) The reciprocal of the spectral radius of the adjacency matrix A ( G ) is the least positive eigenvalue of the adjacency matrix. ii) The graph is isomorphic to its inverse, where the inverse of a graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A ( G ) via a diagonal matrix of ±1s. iii) The graph has the reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) . iv) The graph has the strong reciprocal eigenvalue property, that is, the reciprocal of each eigenvalue of the adjacency matrix A ( G ) is also an eigenvalue of A ( G ) and they both have the same multiplicities. v) The graph is a corona graph, that is, it is obtained by taking a bipartite graph and then by inserting a new adjacent vertex of degree one at each vertex. It is known that the statements iii) and iv) are not equivalent, if we allow nonbipartite graphs. However, the equivalence of these two is not yet known for the class of bipartite graphs with unique perfect matchings, where we relax the condition of bipartiteness of the contracted graph. In this article, we establish the equivalence of the first four statements for a class larger than H g . We then supply a constructive structural description of those graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
35. Robust Community Detection in Graphs
- Author
-
Bara' M. Ababneh, Mahmood Al-khassaweneh, and Esraa Al-sharoa
- Subjects
Optimization problem ,General Computer Science ,Community detection ,Computer science ,business.industry ,graph theory ,General Engineering ,symmetric nonnegative matrix factorization ,Pattern recognition ,Matrix decomposition ,Non-negative matrix factorization ,TK1-9971 ,robust principal component analysis ,Principal component analysis ,Symmetric matrix ,General Materials Science ,Artificial intelligence ,Adjacency matrix ,Electrical engineering. Electronics. Nuclear engineering ,business ,Robust principal component analysis ,Sparse matrix - Abstract
Community detection in network-type data provides a powerful tool in analyzing and understanding real-world systems. In fact, community detection approaches aim to reduce the network’s dimensionality and partition it into a set of disjoint clusters or communities. However, real networks are usually corrupted with noise or outliers which affect the detected community structure quality. In this paper, a new robust community detection algorithm that is capable of recovering a clean or a smoothed version of the corrupted graph and detecting the correct community structure is introduced. The proposed approach combines robust principal component analysis (RPCA) and symmetric nonnegative matrix factorization (SymNMF) in a single optimization problem. The proposed problem is solved under the framework of alternating direction methods of multipliers (ADMM). In particular, the corrupted adjacency matrix is decomposed into a low-rank and sparse components using RPCA and the community structure is detected by applying SymNMF to the extracted low-rank component. Extensive experiments that have been conducted on real and simulated binary and weighted networks show that the proposed approach significantly outperforms existing algorithms in detecting the correct community structure even in grossly corrupted networks.
- Published
- 2021
36. Comparison between hamming method and modified path matrix approach to identify isomorphism in PGTs
- Author
-
I. Rajasri, V. Mahesh, and Ch. Vinay Kumar Reddy
- Subjects
010302 applied physics ,Discrete mathematics ,Graph theory ,02 engineering and technology ,021001 nanoscience & nanotechnology ,01 natural sciences ,Matrix (mathematics) ,Simple (abstract algebra) ,0103 physical sciences ,Path (graph theory) ,Adjacency matrix ,Isomorphism ,0210 nano-technology ,Hamming code ,Mathematics ,Matrix method - Abstract
Structural Synthesis and Analysis plays a major role in identifying the Isomorphism and Symmetry of a Planetary Gear Train (PGT). In synthesis process, detection of isomorphism in PGTs with given number of links and Degree of Freedom (DOF) is essential. One gear pair and one turning pair will be added to the existing link to generate next level PGT. One isomorphic PGT is selected at random to generate higher link PGTs. Graph theory and matrix methods are used by different kinematicians to identify the symmetry and isomorphism in PGTs. Every method has its own merits and demerits. In this paper a comparison was made between the Hamming number technique and Modified Path Matrix (MPM) approach. For easy analysis, PGTs are converted in to graphs and matrices are extracted from these graphs. In this paper isomorphism is checked by using Adjacency matrix and Modified path Matrix. 4-link and 6-link PGTs were considered for analysis in both the methods and compared the results. It is observed that Hamming Number approach is simple and feasible method among the two to identify the symmetry and isomorphism in PGTs.
- Published
- 2021
37. Application of Graph Theory in DNA similarity analysis of Evolutionary Closed Species
- Author
-
G. S. Wijesiri and W. W. P. M. T. M. Karunasena
- Subjects
Quantitative Biology::Biomolecules ,Mitochondrial DNA ,Graph theory ,Directed graph ,Quantitative Biology::Genomics ,DNA sequencing ,Education ,Combinatorics ,Similarity (network science) ,DNA database ,Developmental and Educational Psychology ,Graph (abstract data type) ,Adjacency matrix ,General Psychology ,Mathematics - Abstract
DNA is a complex molecule that consists of biological information that is passed down from generation to generation. With the evolution over time, there are different kinds of species that evolved from a common ancestor because of the occurrence of DNA sequence rearrangements. DNA sequence similarity analysis is a major challenge since the number of sequences is rapidly increasing in the DNA database. In this research, we based a mathematical method to analyze the similarity of two DNA sequences using Graph Theory. This mathematical method started by modeling a weighted directed graph for each DNA sequence, constructing its adjacency matrix, and converting it to the representative vector for each graph. From these vectors, the similarity was determined by distance measurements such as Euclidean, Cosine, and Correlation. By keeping this method as the based method, we will check whether it is applicable for any DNA fragments in considered genomes and molecular similarity coefficients can be used as distance measurements. We will obtain similarities using the graph spectrum instead of the representative vector. Then we will compare the results from the representative vector and that of the graph spectrum. The modified method is tested by using the mitochondrial DNA of Human, Gorilla, and Orangutan. It gives the same result when the number of nucleotides in DNA fragments is increased.
- Published
- 2021
38. Cryptosystem using double vertex graph
- Author
-
C Beaula and P. Venugopal
- Subjects
Vertex (graph theory) ,Multidisciplinary ,Theoretical computer science ,business.industry ,Computer science ,Cryptography ,Graph theory ,Encryption ,Graph ,Vertex (geometry) ,Secure communication ,Cryptosystem ,Adjacency matrix ,business ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Background/Objective: The Coronavirus Covid-19 has affected almost all the countries and millions of people got infected and more deaths have been reported everywhere. The uncertainty and fear created by the pandemic can be used by hackers to steal the data from both private and public systems. Hence, there is an urgent need to improve the security of the systems. This can be done only by building a strong cryptosystem. So many researchers started embedding different topics of mathematics like algebra, number theory, and so on in cryptography to keep the system, safe and secure. In this study, a cryptosystem using graph theory has been attempted, to strengthen the security of the system. Method: A new graph is constructed from the given graph, known as a double vertex graph. The edge labeling of this double vertex graph is used in encryption and decryption. Findings: A new cryptosystem using the amalgamation of the path, its double vertex graph and edge labeling has been proposed. From the double vertex graph of a path, we have given a method to find the original path. To hack such an encrypted key, the knowledge of graph theory is important, which makes the system stronger. Applications:The one-word encryption method will be useful in every security system that needs a password for secure communication or storage or authentication. Keywords: Double vertex graphs; path; adjacency matrix; encryption; cryptography
- Published
- 2020
39. The graphs with all but two eigenvalues equal to $$-2$$ or 0.
- Author
-
Cioabă, Sebastian, Haemers, Willem, and Vermette, Jason
- Subjects
EIGENVALUES ,GRAPHIC methods ,EIGENVECTORS ,GRAPH theory ,PARALLEL algorithms - Abstract
We determine all graphs for which the adjacency matrix has at most two eigenvalues (multiplicities included) not equal to $$-2$$ , or 0, and determine which of these graphs are determined by their adjacency spectrum. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
40. A note on the positive semidefiniteness of Aα(G).
- Author
-
Nikiforov, Vladimir and Rojo, Oscar
- Subjects
- *
SEMIDEFINITE programming , *GRAPH theory , *EIGENVALUES , *BIPARTITE graphs , *LAPLACIAN matrices - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . Let α 0 ( G ) be the smallest α for which A α ( G ) is positive semidefinite. It is known that α 0 ( G ) ≤ 1 / 2 . The main results of this paper are: (1) if G is d -regular then α 0 = − λ min ( A ( G ) ) d − λ min ( A ( G ) ) , where λ min ( A ( G ) ) is the smallest eigenvalue of A ( G ) ; (2) G contains a bipartite component if and only if α 0 ( G ) = 1 / 2 ; (3) if G is r -colorable, then α 0 ( G ) ≥ 1 / r . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
41. MERGING THE A- AND Q-SPECTRAL THEORIES.
- Author
-
Nikiforov, V.
- Subjects
- *
MATRICES (Mathematics) , *LAPLACIAN operator , *GRAPH theory , *CONVEX functions , *MATHEMATICAL models - Abstract
Let G be a graph with adjacency matrix A(G), and let D(G) be the diagonal matrix of the degrees of G: The signless Laplacian Q(G) of G is defined as Q(G) := A(G) +D(G). Cvetković called the study of the adjacency matrix the A-spectral theory, and the study of the signless Laplacian-the Q-spectral theory. To track the gradual change of A(G) into Q(G), in this paper it is suggested to study the convex linear combinations Aα(G) of A(G) and D(G) defined byAα (G) := αD(G) + (1 - α )A(G) , 0 ≤ α ≤ 1. This study sheds new light on A(G) and Q(G), and yields, in particular, a novel spectral Turán theorem. A number of open problems are discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
42. A NOTE ON THE NORDHAUS-GADDUM TYPE INEQUALITY TO THE SECOND LARGEST EIGENVALUE OF A GRAPH.
- Author
-
Abreu, Nair, Brondani, André E., de Lima, Leonardo, and Oliveira, Carla
- Subjects
- *
EIGENVALUES , *GRAPH theory , *GEOMETRIC vertices , *POLYNOMIALS , *MATHEMATICAL models - Abstract
Let G be a g√aph on n ve√tices and G its complement. In this pape√, we p√ove a No√dhaus-Gaddum type inequality to the second la√gest eigenvalue of a g√aph G, λ2(G), λ2(G) + λ2(G) ≤ -1 + √ n2/2 - n + 1; when G is a g√aph with gi√th at least 5. Also, we show that the bound above is tight. Besides, we p√ove that this √esult holds fo√ some classes of connected g√aphs such as t√ees, k-cyclic, √egula√ bipa√tite and complete multipa√tite g√aphs. Based on these facts, we conjectu√e that ou√ √esult holds to any g√aph. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
43. Graph Similarity and its Applications to Hardware Security
- Author
-
Nicolai Bissantz, Marc Fyrbiak, Sebastian Wallat, Sascha Reinhard, and Christof Paar
- Subjects
Hardware security module ,Theoretical computer science ,Computer science ,Graph theory ,02 engineering and technology ,020202 computer hardware & architecture ,Theoretical Computer Science ,Computational Theory and Mathematics ,Hardware and Architecture ,Hardware Trojan ,Logic gate ,0202 electrical engineering, electronic engineering, information engineering ,Hardware obfuscation ,Netlist ,Adjacency matrix ,Heuristics ,Software - Abstract
Hardware reverse engineering is a powerful and universal tool for both security engineers and adversaries. From a defensive perspective, it allows for detection of intellectual property infringements and hardware Trojans, while it simultaneously can be used for product piracy and malicious circuit manipulations. From a designer's perspective, it is crucial to have an estimate of the costs associated with reverse engineering, yet little is known about this, especially when dealing with obfuscated hardware. The contribution at hand provides new insights into this problem, based on algorithms with sound mathematical underpinnings. Our contributions are threefold: First, we present the graph similarity problem for automating hardware reverse engineering. To this end, we improve several state-of-the-art graph similarity heuristics with optimizations tailored to the hardware context. Second, we propose a novel algorithm based on multiresolutional spectral analysis of adjacency matrices. Third, in three extensively evaluated case studies, namely (1) gate-level netlist reverse engineering, (2) hardware Trojan detection, and (3) assessment of hardware obfuscation, we demonstrate the practical nature of graph similarity algorithms.
- Published
- 2020
44. R3MAT: A Rapid and Robust Graph Generator
- Author
-
Renzo Angles, Rodrigo Paredes, and Roberto Garcia
- Subjects
Discrete mathematics ,data engineering ,021103 operations research ,General Computer Science ,Computer science ,0211 other engineering and technologies ,General Engineering ,Graph theory ,010103 numerical & computational mathematics ,02 engineering and technology ,Graph generator ,01 natural sciences ,Graph ,General Materials Science ,Adjacency matrix ,lcsh:Electrical engineering. Electronics. Nuclear engineering ,0101 mathematics ,performance analysis ,Network theory (graphs) ,lcsh:TK1-9971 - Abstract
One of the main problems when developing graph-based applications is the availability of large and representative datasets. The lack of real graphs has motivated the development of software tools for generating synthetic graphs. R-MAT is a data generation method that was designed to produce synthetic graphs whose characteristics resemble those occurring in real networks. Although the generation model defined by R-MAT is easy to understand, its implementation is not trivial and it has intrinsic memory restrictions that makes the generation of very large graphs difficult. This paper studies the practical implementation of R-MAT. We discuss the issues of the original implementation which works with the adjacency matrix of the graph and analyze the size of the resulting graph obtained with the R-MAT model. Then, we introduce and experimentally evaluate R3MAT, an alternative implementation for R-MAT based on an array of degrees. These experiments show that $(i)$ our R3MAT is able to generate graphs of hundred million nodes and billion edges in a single machine, $(ii)$ our method preserves the characteristic power-law distribution of the edge degrees present in real-world graphs, and $(iii)~\text{R}^{3}$ MAT has the best performance in the current state of the art, when considering a single modest computer in a sequential fashion.
- Published
- 2020
45. 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
46. Hamming index of some thorn graphs with respect to adjacency matrix.
- Author
-
Ramane, Harishchandra S., Gudodagi, Gouramma A., and Yalnaik, Ashwini S.
- Subjects
- *
GRAPH theory , *HAMMING distance , *GEOMETRIC vertices , *MATRICES (Mathematics) , *SET theory - Abstract
Let G be a graph with vertex set V(G) = {v1,v2,..., vn}. Let A(G) be the adjacency matrix of a graph G. The rows of A(G) corresponding to a vertex v of G, denoted by s(v) is the string. The Hamming index of a graph G is the sum of the Hamming distances between all pairs of vertices of G. In this paper we obtain Hamming index generated by adjacency matrix of some thorn graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2016
47. Newly proposed node segregation index is not suitable for analyzing unimode food webs.
- Author
-
Chen, Youhua
- Subjects
FOOD chains ,PROBABILISTIC inference ,PROBABILITY theory ,COMPUTER simulation ,GRAPH theory - Abstract
Strona and Veech (2015) developed a new node segregation (or node overlap) index for analysing ecological network structure based on the Veech (2013)’s species co-occurrence probabilistic model, which was originally applied to species-site matrices. However, a species-site matrix for analysing species co-occurrence patterns and an adjacency matrix for characterising unimode network structures are different. Directly applying Veech’s species co-occurrence probabilistic model to adjacency matrices in unimode food webs is problematic. The central critical problem is related to the number of free species (or nodes/vertices) in the unimode network that can be the neighbors (have links to connect) of a focused species or a focused pair of species. This number is typically less than the total number of species in real food webs. That is, species are not independent from each other in unimode networks. For a simple undirected unimode network without self-loops, based on the criterion whether there is a link between two species for a focused pair, a correct probabilistic model is developed to accurately compute the probability of observing some shared neighbors for a pair of species in the network. Numerical simulation show that the node overlap calculated using the correct and original probabilistic models present remarkable differences, especially when a unimode network is nested and contains generalists. In summary, The correct probabilistic model should be used if ones want Strona and Veech (2015)’s node segregation index to work for unimode food webs. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
48. Using adjacency matrices to lay out larger small-world networks.
- Author
-
Gibson, Helen and Vickers, Paul
- Subjects
COMPUTER network architectures ,GRAPH theory ,COMPUTER algorithms ,MATRICES (Mathematics) ,FUZZY clustering technique ,DATA analysis - Abstract
Many networks exhibit small-world properties. The structure of a small-world network is characterized by short average path lengths and high clustering coefficients. Few graph layout methods capture this structure well which limits their effectiveness and the utility of the visualization itself. Here we present an extension to our novel graphTPP layout method for laying out small-world networks using only their topological properties rather than their node attributes. The Watts–Strogatz model is used to generate a variety of graphs with a small-world network structure. Community detection algorithms are used to generate six different clusterings of the data. These clusterings, the adjacency matrix and edgelist are loaded into graphTPP and, through user interaction combined with linear projections of the adjacency matrix, graphTPP is able to produce a layout which visually separates these clusters. These layouts are compared to the layouts of two force-based techniques. graphTPP is able to clearly separate each of the communities into a spatially distinct area and the edge relationships between the clusters show the strength of their relationship. As a secondary contribution, an edge-grouping algorithm for graphTPP is demonstrated as a means to reduce visual clutter in the layout and reinforce the display of the strength of the relationship between two communities. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
49. Non-Singular graphs with a Singular Deck.
- Author
-
Farrugia, Alexander, Gauci, John Baptist, and Sciriha, Irene
- Subjects
- *
GRAPH theory , *MATHEMATICAL symmetry , *MATRICES (Mathematics) , *MOLECULAR graphs , *ELECTRICAL conductors , *SUBGRAPHS - Abstract
The n -vertex graph G ( = Γ ( G ) ) with a non-singular real symmetric adjacency matrix G , having a zero diagonal and singular ( n − 1 ) × ( n − 1 ) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G − 1 represent NSSDs Γ ( G ) and Γ ( G − 1 ) , the value of the nullity of a one-, two- and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in Γ ( G − 1 ) . Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G -nutful graphs. We show that their minimum vertex degree is at least 4. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
50. Relation between signless Laplacian energy, energy of graph and its line graph.
- Author
-
Das, Kinkar Ch. and Mojallal, Seyed Ahmad
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *ABSOLUTE value , *MATHEMATICAL bounds , *MATHEMATICAL analysis , *NUMERICAL analysis - Abstract
The energy of a simple graph G , E ( G ) , is the sum of the absolute values of the eigenvalues of its adjacency matrix. The energy of line graph and the signless Laplacian energy of graph G are denoted by E ( L G ) ( L G is the line graph of G ) and LE + ( G ) , respectively. In this paper we obtain a relation between E ( L G ) and LE + ( G ) of graph G . From this relation we characterize all the graphs satisfying E ( L G ) = LE + ( G ) + 4 m n − 4 . We also present a relation between E ( G ) and E ( L G ) . Moreover, we give an upper bound on E ( L G ) of graph G and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.