2,466 results on '"Adjacency matrix"'
Search Results
2. Graceful labeling for some supercaterpillar graphs using adjacency matrix
- Author
-
R. N. Pakpahan and K. A. Sugeng
- Subjects
Discrete mathematics ,symbols.namesake ,Conjecture ,Graph labeling ,Graceful labeling ,Euler's formula ,symbols ,Graph theory ,Adjacency matrix ,Graph ,Injective function ,Mathematics - Abstract
Graph theory was first introduced by Leonhard Euler in 1736 and still being one of the mathematic’s topics which is rapidly developing and can be used to simplify mathematic problems. There are many interesting topics in graph theory; one of them is graph labeling. There are many ways of labeling a graph, and one of them is graceful labeling. Let G(V, E is a graph. The injective mapping f: V → {0,1, …, |E|} is called graceful if the weights of edge w(uv) = |f(u) – f(v)| are all different for every edge uv. There is a famous conjecture in graceful labeling. It is said that all trees are graceful. To prove this conjecture, then we must show that every tree is graceful. There are many research papers dealing with the special cases of trees. Many classes of trees have been proven graceful, and one of them is supercaterpillar. Previous research had proved that supercaterpillars with certain conditions are also graceful. In this paper, we generalize the concept of supercaterpillar, and show that the subclass of supercaterpillar graphs that has not been discussed earlier is also graceful, using an adjacency matrix for the construction.
- Published
- 2018
3. Analyzing the Realization of Degree Sequence by Constructing Orthogonally Diagonalizable Adjacency Matrix.
- Author
-
Biswas, Prantik, Paul, Abhisek, and Bhattacharya, Paritosh
- Subjects
ORTHOGONALIZATION ,MATHEMATICAL sequences ,INTEGERS ,GRAPH theory ,COMPUTER algorithms - Abstract
A finite sequence d: d 1 , d 2 , d 3 ,. .. ., d n of nonnegative integers is said to be graphical if there exists some finite simple graph G, having vertex set V={ v 1 , v 2 , v 3 , …., v n } such that each v i has degree d i (1 ≤ i ≤ n). In this paper we have proposed an algorithm that takes a non-increasing sequence as input and determines whether the given degree sequence is graphic by constructing the adjacency matrix from the given sequence in non-increasing order and checking whether it can be orthogonally diagonalizable. The matrix generated in this process can be used to determine a lot of interesting information regarding the characteristic of the graph directly from the given degree sequence. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
4. Vertex colouring using the adjacency matrix
- Author
-
Ika Hesti Agustin, Dafik, Ridho Alfarisi, Kiswara Agung Santoso, and R. M. Prihandini
- Subjects
Vertex (graph theory) ,History ,Flowchart ,Backtracking ,Graph colouring ,Graph theory ,Astrophysics::Cosmology and Extragalactic Astrophysics ,Square matrix ,Graph ,Computer Science Applications ,Education ,law.invention ,Combinatorics ,law ,Adjacency matrix ,Astrophysics::Galaxy Astrophysics ,Mathematics - Abstract
Recently, graph theory is one of the most rapidly developing sciences. Graphs in its applications are generally used to represent discrete objects and relationships between these objects. The visual representation of a graph is to declare an object as a vertex, while the relationship between objects is expressed as an edge. One topic in graph theory is colouring. This graph colouring is divided into vertex colouring, edge colouring and area colouring. The problem of the vertex colouring is to determine the minimum number of colours to colour the vertex so that the interconnected vertex has different colours. The problem of edge colouring is to determine the minimum number of colours to colour the edge so that the interconnected edge has different colours. The problem with area colouring is to determine the minimum number of colours to colour the area so that the adjacent area has a different colour. In this article the discussion will focus on the problem of vertex colouring. Previously there have been several vertex colouring methods, such as the Welch Powell method and the backtracking method. In this paper we will discuss the method of vertex colouring using the adjacent matrix. Adjacent matrix (M) is a square matrix where the element Mij is 1 if ViVj is connected and element Mij is 0 if ViVj is not connected. In the discussion, this method is presented in the form of the pseducode and flowchart so that it can be computerized more easily. The novelty of this research is to detect the character of the adjacency matrix so that it can apply to vertex colouring through the matrix.
- Published
- 2019
5. Role of Adjacency Matrix & Adjacency List in Graph Theory
- Author
-
Harmanjit Singh and Richa Sharma
- Subjects
Combinatorics ,Computer science ,Adjacency list ,Graph theory ,Adjacency matrix - Abstract
Today, graph theory has become major instrument that is used in an array of fields. Some of these include electrical engineering, mathematical research, sociology, economics, computer programming/networking, business administration and marketing. Indeed, many problems can be modeled with paths formed by traveling along the edges of a certain graph. Frequently referenced problems are efficiently planning routes for mail delivery, garbage pickup and snow removal, which can be solved using models that involve paths in graphs. Given these kinds of problems, graphs can become extremely complex, and a more efficient way of representing them is needed in practice. This is where the concept of the adjacency matrix & adjacency list comes into play.
- Published
- 2012
6. 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
7. On the mixed adjacency matrix of a mixed graph.
- Author
-
Adiga, Chandrashekar, Rakshith, B.R., and So, Wasin
- Subjects
- *
GRAPH theory , *POLYNOMIALS , *HYBRID systems , *MATHEMATICAL models , *MATRICES (Mathematics) - Abstract
A mixed graph is a graph with edges and arcs, which can be considered as a hybrid of an undirected graph and a directed graph. In this paper we define the mixed adjacency matrix and the mixed energy of a mixed graph. The mixed adjacency matrix generalizes both the adjacency matrix of an undirected graph and the skew-adjacency matrix of a digraph. Then we compute the characteristic polynomial of the mixed adjacency matrix of a mixed graph and deduce some basic results from it. Furthermore, we give bounds to the mixed energy of a general mixed graph, and we compute the mixed energy of some special mixed graphs. At the end of the paper, we introduce mixed unitary Cayley graphs and compute their spectra. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
8. Balance theory: An extension to conjugate skew gain graphs.
- Author
-
Koombail, Shahul Hameed and K. O., Ramakrishnan
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *EIGENVALUES , *MATHEMATICAL notation , *COMPLEX numbers , *EDGES (Geometry) - Abstract
We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the g -Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
9. Cospectral graphs and the generalized adjacency matrix
- Author
-
Willem H. Haemers, Jack H. Koolen, Edwin van Dam, Research Group: Operations Research, and Econometrics and Operations Research
- Subjects
Discrete mathematics ,Numerical Analysis ,Rational number ,Algebra and Number Theory ,cospectral graphs ,generalized spectrum ,generalized adjacency matrix ,Spectrum (functional analysis) ,Multigraph ,Graph theory ,ComputingMilieux_LEGALASPECTSOFCOMPUTING ,Cospectral graphs ,Graph ,Combinatorics ,Matrix (mathematics) ,Generalized spectrum ,jel:C0 ,Discrete Mathematics and Combinatorics ,Regular graph ,Geometry and Topology ,Adjacency matrix ,Generalized adjacency matrix ,Mathematics - Abstract
Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value y ˆ of y. We call such graphs y ˆ -cospectral. It follows that y ˆ is a rational number, and we prove existence of a pair of y ˆ -cospectral graphs for every rational y ˆ . In addition, we generate by computer all y ˆ -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of y ˆ -cospectral graphs for all rational y ˆ ∈ ( 0 , 1 ) , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of y ˆ , and by computer we find all such pairs of y ˆ -cospectral graphs on at most eleven vertices.
- Published
- 2007
10. The Use of Weighted Adjacency Matrix for Searching Optimal Ship Transportation Routes.
- Author
-
Antoš, Karel
- Subjects
- *
MARITIME shipping , *TRADE routes , *SPANNING trees , *GRAPH theory , *TRAFFIC flow - Abstract
This article provides a new approach to searching solutions of water transport optimization problems. It brings a new tool of the graph theory which is the Weighted Adjacency Matrix. This Weighted Adjacency Matrix is suitable for searching for the Minimum Spanning Tree (MST) of the graph. It describes the Weighted Adjacency Matrix as a new element, and shows how it could be used in cases where weighted edges of the graph are given. This creates a new procedure of searching the MST of the graph and completes previously known algorithms of searching for the MST. In the field of ship transportation it could be succesfully used for solutions of optimizing transportation routes where lowest transport costs are needed. Proposed Weighted Adjacency Matrix could be used in similar issues in the field of graph theory, where graphs with weighted edges are given. The procedure is shown in the given example. The paper discusses the application of such route optimization technique forthe maritime sector. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
11. On the adjacency matrix of a threshold graph.
- Author
-
Bapat, R.B.
- Subjects
- *
MATRICES (Mathematics) , *GRAPH theory , *EIGENVALUES , *MATHEMATICAL formulas , *GENERALIZATION , *EXISTENCE theorems - Abstract
Abstract: A threshold graph on n vertices is coded by a binary string of length . We obtain a formula for the inertia of (the adjacency matrix of) a threshold graph in terms of the code of the graph. It is shown that the number of negative eigenvalues of the adjacency matrix of a threshold graph is the number of ones in the code, whereas the nullity is given by the number of zeros in the code that are preceded by either a zero or a blank. A formula for the determinant of the adjacency matrix of a generalized threshold graph and the inverse, when it exists, of the adjacency matrix of a threshold graph are obtained. Results for antiregular graphs follow as special cases. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
12. Reducing rank of the adjacency matrix by graph modification.
- Author
-
Meesum, S.M., Misra, Pranabendu, and Saurabh, Saket
- Subjects
- *
GEOMETRIC vertices , *GRAPH theory , *INTEGERS , *PROBLEM solving , *PARAMETERIZATION , *COMPUTER algorithms , *KERNEL (Mathematics) - Abstract
The main topic of this article is to study a class of graph modification problems. A typical graph modification problem takes as input a graph G , a positive integer k and the objective is to add/delete k vertices (edges) so that the resulting graph belongs to a particular family, F , of graphs. In general the family F is defined by forbidden subgraph/minor characterization. In this paper rather than taking a structural route to define F , we take algebraic route. More formally, given a fixed positive integer r , we define F r as the family of graphs where for each G ∈ F r , the rank of the adjacency matrix of G is at most r . Using the family F r we initiate algorithmic study, both in classical and parameterized complexity, of following graph modification problems: r - Rank Vertex Deletion , r - Rank Edge Deletion and r - Rank Editing . These problems generalize the classical Vertex Cover problem and a variant of the d - Cluster Editing problem. We first show that all the three problems are NP-Complete . Then we show that these problems are fixed parameter tractable (FPT) by designing an algorithm with running time 2 O ( k log r ) n O ( 1 ) for r - Rank Vertex Deletion , and an algorithm for r - Rank Edge Deletion and r - Rank Editing running in time 2 O ( f ( r ) k log k ) n O ( 1 ) . We complement our FPT result by designing polynomial kernels for these problems. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
13. Cut-and-paste of quadriculated disks and arithmetic properties of the adjacency matrix
- Author
-
Nicolau C. Saldanha and Carlos Tomei
- Subjects
Quadriculated disk ,05B45, 05C70 ,05B20, 05C50 ,Discrete mathematics ,Numerical Analysis ,Algebra and Number Theory ,Matchings ,Identity matrix ,Triangular matrix ,Graph theory ,Row and column spaces ,Combinatorics ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Adjacency matrix ,Geometry and Topology ,Tilings by dominoes ,Dimers ,Parity (mathematics) ,Mathematics - Abstract
We define cut-and-paste, a construction which, given a quadriculated disk obtains a disjoint union of quadriculated disks of smaller total area. We provide two examples of the use of this procedure as a recursive step. Tilings of a disk $\Delta$ receive a parity: we construct a perfect or near-perfect matching of tilings of opposite parities. Let $B_\Delta$ be the black-to-white adjacency matrix: we factor $B_\Delta = L\tilde DU$, where $L$ and $U$ are lower and upper triangular matrices, $\tilde D$ is obtained from a larger identity matrix by removing rows and columns and all entries of $L$, $\tilde D$ and $U$ are equal to 0, 1 or -1., Comment: 20 pages, 17 figures
- Published
- 2009
14. Assessment of the Water Distribution Networks in the Kingdom of Saudi Arabia: A Mathematical Model
- Author
-
Aiman Albarakati, Asifa Tassaddiq, and Rekha Srivastava
- Subjects
graph theory ,weighted adjacency matrix ,water distribution systems or networks ,centrality measures ,Mathematics ,QA1-939 - Abstract
Graph theory is a branch of mathematics that is crucial to modelling applicable systems and networks using matrix representations. In this article, a novel graph-theoretic model was used to assess an urban water distribution system (WDS) in Saudi Arabia. This graph model is based on representing its elements through nodes and links using a weighted adjacency matrix. The nodes represent the points where there can be a water input or output (sources, treatment plants, tanks, reservoirs, consumers, connections), and links represent the edges of the graph that carry water from one node to another (pipes, pumps, valves). Four WDS benchmarks, pumps, tanks, reservoirs, and external sources were used to validate the framework at first. This validation showed that the worst-case scenarios for vulnerability were provided by the fault sequence iterating the calculation of the centrality measurements. The vulnerability framework’s application to the Saudi Arabian WDS enabled the identification of the system’s most vulnerable junctions and zones. As anticipated, the regions with the fewest reservoirs were most at risk from unmet demand, indicating that this system is vulnerable to the removal of junctions and pipes that are intricately associated with their neighbours. Different centrality metrics were computed, from which the betweenness centrality offered the worst vulnerability prediction measures. The aspects and zones of the WDS that can more significantly impact the water supply in the event of a failure were identified by the vulnerability framework utilising attack tactics.
- Published
- 2023
- Full Text
- View/download PDF
15. Nonpositive eigenvalues of the adjacency matrix and lower bounds for Laplacian eigenvalues.
- Author
-
Charles, Zachary B., Farber, Miriam, Johnson, Charles R., and Kennedy-Shaffer, Lee
- Subjects
- *
EIGENVALUES , *MATRICES (Mathematics) , *MATHEMATICAL bounds , *LAPLACIAN matrices , *UNDIRECTED graphs , *GRAPH theory - Abstract
Abstract: Let be the smallest number such that the adjacency matrix of any undirected graph with vertices or more has at least nonpositive eigenvalues. We show that is well-defined and prove that the values of for are 1, 3, 6, 10, 16 respectively. In addition, we prove that for all , , in which is the Ramsey number for and , and is the triangular number. This implies new lower bounds for eigenvalues of Laplacian matrices: the largest eigenvalue is bounded from below the largest degree, which generalizes some prior results. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
16. Cospectral graphs and the generalized adjacency matrix
- Author
-
van Dam, E.R., Haemers, W.H., and Koolen, J.H.
- Subjects
- *
MATRICES (Mathematics) , *REAL numbers , *GRAPH theory , *SPECTRUM analysis - Abstract
Abstract: Let J be the all-ones matrix, and let A denote the adjacency matrix of a graph. An old result of Johnson and Newman states that if two graphs are cospectral with respect to yJ − A for two distinct values of y, then they are cospectral for all y. Here we will focus on graphs cospectral with respect to yJ − A for exactly one value of y. We call such graphs -cospectral. It follows that is a rational number, and we prove existence of a pair of -cospectral graphs for every rational . In addition, we generate by computer all -cospectral pairs on at most nine vertices. Recently, Chesnokov and the second author constructed pairs of -cospectral graphs for all rational , where one graph is regular and the other one is not. This phenomenon is only possible for the mentioned values of , and by computer we find all such pairs of -cospectral graphs on at most eleven vertices. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
17. Imprimitivity index of the adjacency matrix of digraphs.
- Author
-
Akbari, Saieed, Ghodrati, Amir Hossein, and Hosseinzadeh, Mohammad Ali
- Subjects
- *
DIRECTED graphs , *GRAPH theory , *GEOMETRIC vertices , *BIPARTITE graphs , *MATRICES (Mathematics) - Abstract
Let G be a graph. An edge orientation of G is called smooth if the in-degree and the out-degree of every vertex differ by at most one. In this paper, we show that if G is a 2-edge-connected non-bipartite graph with δ ( G ) ≥ 3 , then G has a smooth primitive orientation. Among other results, using the spectral radius of digraphs, we show that if D 1 is a primitive regular orientation and D 2 is a non-regular orientation of a given graph, then for sufficiently large t , the number of closed walks of length t in D 1 is more than the number of closed walks of length t in D 2 . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
18. CLUSTERING BASED ON EIGENVECTORS OF THE ADJACENCY MATRIX.
- Author
-
LUCIŃSKA, MAŁGORZATA and WIERZCHÓN, SŁAWOMIR T.
- Subjects
K-means clustering ,EIGENVECTORS ,LAPLACIAN matrices ,GRAPH theory ,PERTURBATION theory - Abstract
The paper presents a novel spectral algorithm EVSA (eigenvector structure analysis), which uses eigenvalues and eigenvectors of the adjacency matrix in order to discover clusters. Based on matrix perturbation theory and properties of graph spectra we show that the adjacency matrix can be more suitable for partitioning than other Laplacian matrices. The main problem concerning the use of the adjacency matrix is the selection of the appropriate eigenvectors. We thus propose an approach based on analysis of the adjacency matrix spectrum and eigenvector pairwise correlations. Formulated rules and heuristics allow choosing the right eigenvectors representing clusters, i.e., automatically establishing the number of groups. The algorithm requires only one parameter-the number of nearest neighbors. Unlike many other spectral methods, our solution does not need an additional clustering algorithm for final partitioning. We evaluate the proposed approach using real-world datasets of different sizes. Its performance is competitive to other both standard and new solutions, which require the number of clusters to be given as an input parameter. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
19. MERGING THE 𝐴- AND 𝑄-SPECTRAL THEORIES
- Author
-
Nikiforov, V.
- Published
- 2017
20. 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
21. Maximal Biclique Subgraphs and Closed Pattern Pairs of the Adjacency Matrix: A One-to-One Correspondence and Mining Algorithms.
- Author
-
Li, Jinyan, Liu, Guimei, Li, Haiquan, and Wong, Limsoon
- Subjects
- *
BIPARTITE graphs , *GRAPH theory , *BIOINFORMATICS , *INFORMATION science , *DATA mining , *DATABASE searching , *ALGORITHMS , *ONLINE data processing , *INFORMATION resources management , *KNOWLEDGE management - Abstract
Maximal biclique (also known as complete bipartite) subgraphs can model many applications in Web mining, business, and bioinformatics. Enumerating maximal biclique subgraphs from a graph is a computationally challenging problem, as the size of the output can become exponentially large with respect to the vertex number when the graph grows. In this paper, we efficiently enumerate them through the use of closed patterns of the adjacency matrix of the graph. For an undirected graph G without self-loops, we prove that 1) the number of closed patterns in the adjacency matrix of G is even, 2) the number of the closed patterns is precisely double the number of maximal biclique subgraphs of G, and 3) for every maximal biclique subgraph, there always exists a unique pair of closed patterns that matches the two vertex sets of the subgraph. Therefore, the problem of enumerating maximal bicliques can be solved by using efficient algorithms for mining closed patterns, which are algorithms extensively studied in the data mining field. However, this direct use of existing algorithms causes a duplicated enumeration. To achieve high efficiency, we propose an O(mn) time delay algorithm for a nonduplicated enumeration, in particular, for enumerating those maximal bicliques with a large size, where m and n are the number of edges and vertices of the graph, respectively. We evaluate the high efficiency of our algorithm by comparing it to state- of-the-art algorithms on three categories of graphs: randomly generated graphs, benchmarks, and a real-life protein interaction network. In this paper, we also prove that if self-loops are allowed in a graph, then the number of closed patterns in the adjacency matrix is not necessarily even, but the maximal bicliques are exactly the same as those of the graph after removing all the self-loops. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF
22. Equivalence of lattice operators and graph matrices.
- Author
-
Yumoto, Jun and Misumi, Tatsuhiro
- Subjects
LATTICE field theory ,GRAPH theory ,BETTI numbers ,LAPLACIAN matrices ,DIRAC operators ,SPECTRAL theory ,LATTICE theory - Abstract
We explore the relationship between lattice field theory and graph theory, placing special emphasis on the interplay between Dirac and scalar lattice operators and matrices within the realm of spectral graph theory. Beyond delving into fundamental concepts of spectral graph theory, such as adjacency and Laplacian matrices, we introduce a novel matrix called an "antisymmetrized adjacency matrix", specifically tailored for cycle digraphs (T
1 lattice) and simple directed paths (B1 lattice). The nontrivial relationship between graph theory matrices and lattice operators shows that the graph Laplacian matrix mirrors the lattice scalar operator and the Wilson term in lattice fermions, while the antisymmetrized adjacency matrix, along with its extensions to higher dimensions, is equivalent to naive lattice Dirac operators. Building upon these connections, we provide rigorous proofs for two key assertions: (i) The count of zero-modes in a free lattice scalar operator coincides with the zeroth Betti number of the underlying graph (lattice). (ii) The maximum count of Dirac zero-modes in a free lattice fermion operator is equivalent to the cumulative sum of all Betti numbers when the D -dimensional graph results from a Cartesian product of cycle digraphs (T1 lattice) and simple directed paths (B1 lattice). [ABSTRACT FROM AUTHOR]- Published
- 2024
- Full Text
- View/download PDF
23. 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
24. Ring structure digraphs: Spectrum of adjacency matrix and application.
- Author
-
Agaev, R., Nikiforov, S., and Andryushina, N.
- Subjects
- *
DIRECTED graphs , *GRAPH theory , *LINEAR algebra , *TOPOLOGY , *POLYHEDRA - Abstract
Under elimination of two arcs, spectrum of digraph having ring structure and two Hamiltonian cycles is shown real, if and only if the number of vertices is even and “interval between arcs,” eliminated from the same cycle, is maximal. Possibility to apply the obtained results to evaluate failure-resistance of networks with ring topology is considered. [ABSTRACT FROM AUTHOR]
- Published
- 2010
- Full Text
- View/download PDF
25. Algebraic relationship between the structural network's Laplacian and functional network's adjacency matrix is preserved in temporal lobe epilepsy subjects.
- Author
-
Abdelnour, Farras, Dayan, Michael, Devinsky, Orrin, Thesen, Thomas, and Raj, Ashish
- Subjects
- *
TEMPORAL lobe epilepsy , *FUNCTIONAL connectivity - Abstract
The relationship between anatomic and resting state functional connectivity of large-scale brain networks is a major focus of current research. In previous work, we introduced a model based on eigen decomposition of the Laplacian which predicts the functional network from the structural network in healthy brains. In this work, we apply the eigen decomposition model to two types of epilepsy; temporal lobe epilepsy associated with mesial temporal sclerosis, and MRI-normal temporal lobe epilepsy. Our findings show that the eigen relationship between function and structure holds for patients with temporal lobe epilepsy as well as normal individuals. These results suggest that the brain under TLE conditions reconfigures and rewires the fine-scale connectivity (a process which the model parameters are putatively sensitive to), in order to achieve the necessary structure-function relationship. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
26. 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
27. 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
28. On the spectra and eigenspaces of the universal adjacency matrices of arbitrary lifts of graphs
- Author
-
Dalfó, C., Fiol, M. A., Pavlíková, S., Širáň, J., Universitat Politècnica de Catalunya. Departament de Matemàtiques, and Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
- Subjects
Algebras, Linear ,Lift ,Algebra and Number Theory ,Matemàtiques i estadística::Àlgebra::Àlgebra lineal i multilineal [Àrees temàtiques de la UPC] ,Grafs, Teoria de ,15 Linear and multilinear algebra ,matrix theory [Classificació AMS] ,15 Linear and multilinear algebra [Classificació AMS] ,Eigenspace ,Eigen ,Space ,Matemàtiques i estadística::Matemàtica discreta::Combinatòria [Àrees temàtiques de la UPC] ,Mathematics::Spectral Theory ,Graph ,Graph theory ,matrix theory ,Universal adjacency matrix ,Àlgebra lineal ,Symmetric square ,05 Combinatorics::05C Graph theory [Classificació AMS] - Abstract
The universal adjacency matrix U of a graph Γ, with adjacency matrix A, is a linear combination of A, the diagonal matrix D of vertex degrees, the identity matrix I, and the all-1 matrix J with real coefficients, that is, U=c1A+c2D+c3I+c4J, with ci∈R and c1≠0. Thus, in particular cases, U may be the adjacency matrix, the Laplacian, the signless Laplacian, and the Seidel matrix. In this paper, we develop a method for determining the universal spectra and bases of all the corresponding eigenspaces of arbitrary lifts of graphs (regular or not). As an example, the method is applied to give an efficient algorithm to determine the characteristic polynomial of the Laplacian matrix of the symmetric squares of odd cycles, together with closed formulas for some of their eigenvalues. The first author has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922. The research of the two first authors is partially supported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00. The research of the first author has also been supported by MICINN from the Spanish Government under project MTM2017-83271-R. The third and fourth authors acknowledge support from the APVV Research Grants 15-0220 and 17-0428, and the VEGA Research Grants 1/0142/17 and 1/0238/19.
- Published
- 2022
29. Asymptotic Spectral Analysis of Growing Regular Graphs
- Author
-
Hora, Akihito and Obata, Nobuaki
- Published
- 2008
- Full Text
- View/download PDF
30. Assembly Configuration Representation and Kinematic Modeling for Modular Reconfigurable Robots Based on Graph Theory.
- Author
-
Zhang, Tuopu, Du, Qinghao, Yang, Guilin, Wang, Chongchong, Chen, Chin-Yin, Zhang, Chi, Chen, Silu, and Fang, Zaojun
- Subjects
- *
GRAPH theory , *ROBOTS , *KINEMATICS - Abstract
A Modular Reconfigurable Robot (MRR) composed of standard joint and link modules has the advantages of rapid changeover of assembly configurations for a diversity of application requirements. To tackle the kinematics analysis issues for an MRR, it is essential to develop a generic method to mathematically represent all possible assembly configurations and automatically generate their kinematic models. In this paper, two types of robot modules, i.e., revolute joint modules and rigid link modules, are considered as the basic building blocks of an MRR. The topological structure of an MRR is represented by a graph, termed an Assembly Graph (AG), in which all robot modules, regardless of their types, are treated as vertices, while the connecting interfaces between any two robot modules are treated as edges. Based on graph theory, a modified adjacency matrix, termed an Assembly Adjacency Matrix (AAM), is proposed to represent the assembly configuration of an MRR, in which the three-dimensional assembly information is specified with connecting port vectors for the adjacent modules. A path matrix derived from the AAM of an MRR is employed to describe the connecting sequence of its constituting modules. The local frame representation of the Product-of-Exponentials (POE) formula is employed, which is configuration-independent. Therefore, for an MRR configuration represented with an AAM, its kinematic model will be automatically generated according to its path matrix. The proposed assembly configuration representation and kinematic modeling method are validated through a dual-branch MRR configuration. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
31. Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders
- Author
-
Reingold, Omer, Vadhan, Salil, and Wigderson, Avi
- Published
- 2002
- Full Text
- View/download PDF
32. Robustness analysis of cyber-physical power system based on reachable matrix.
- Author
-
Xu, Zhengwei, Ge, Yuan, Cao, Jin, Lin, Qiyou, and Yang, Shuquan
- Subjects
CYBER physical systems ,GRAPH theory ,MATRICES (Mathematics) ,SIMULATION methods & models - Abstract
The traditional modelling and simulation analysis methods based on graph theory are difficult to present the structural characteristics and dynamic laws of cyber-physical power systems (CPPS). In order to reduce the complexity of the attack graph, this paper proposes a CPPS robustness analysis method based on the reachable matrix. Based on the evolution of the augmented adjacency matrix of cyber-physical power system, this method uses the reachable matrix to obtain the maximum connectivity matrix of the system (the adjacency matrix corresponding to the largest connected subgraph of cyber-physical power system), and then, evaluates and analyses the robustness of cyber-physical power system. The IEEE118 node standard model is taken as an example to carry out the simulation experiment. The experimental results show that the reachable matrix has feasibility in the robustness analysis of cyber-physical power systems. Further through the contrast experiment found that compared with the robustness analysis method based on graph theory, the proposed method in this paper can reduce the modelling complexity of the mutual coupling network, reduce the complexity of the attack graph, and clearly and intuitively show the structural characteristics and dynamic laws of the network connection in the system. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
33. 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
34. Correlation Coefficient Measure of Intuitionistic Fuzzy Graphs with Application in Money Investing Schemes
- Author
-
Akula, Naveen Kumar and Shaik, Sharief Basha
- Subjects
Fuzzy Set Theory ,intuitionistic fuzzy laplacian matrix ,Graph Theory ,group decision-making problem ,Intuitionistic fuzzy preference relation ,03B52 ,Laplacian energy ,Fuzzy Graph Theory ,correlation coefficient ,03E72 ,intuitionistic fuzzy adjacency matrix ,intuitionistic fuzzy graph - Abstract
Intuitionistic fuzzy graphs are extensions of fuzzy graphs that preserve the dualism characteristics of fuzzy graphs and have a stronger capacity to describe ambiguity in actual decision-making issues than fuzzy graphs. In this research paper, the Laplacian energy and correlation coefficient of intuitionistic fuzzy graphs are computed for finding group decision-making problems that are supported by intuitionistic fuzzy preference relations. We propose a novel method for calculating establishments' comparative position loads by manipulating the undecided corroboration of IFPR and the correlation coefficient of one personality IFPR to the other items. As a result, we comprehend a large number of establishments in the detailed IFPR and devise a correlation coefficient process to investigate the significance of alternatives and the best of the alternatives. Finally, we present a collaborative decision-making technique in a money-investing scheme, and that idea may be devised in disparate beneficial investing schemes.
- Published
- 2023
35. 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
36. The Analysis of Assumptions in Model Bases Using Metagraphs
- Author
-
Basu, Amit and Blanning, Robert W.
- Published
- 1998
37. 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
38. 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
39. Some spectral inequalities for triangle-free regular graphs
- Author
-
Koledin, Tamara and Stanić, Zoran
- Published
- 2013
40. 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
41. 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
42. 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
43. 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
44. Diameters and Eigenvalues
- Author
-
Chung, F. R. K.
- Published
- 1989
- Full Text
- View/download PDF
45. 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
46. A NOTE ON THE FUSION OF TWO VERTICES IN A FUZZY GRAPH
- Author
-
Ramakrishnan, P. V. and Lakshmi, T.
- Published
- 2008
47. 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
48. Alpha Adjacency: A generalization of adjacency matrices
- Author
-
Enzo Wendler, Matt Hudelson, and Judi J. McDonald
- Subjects
Combinatorics ,Polynomial ,Matrix (mathematics) ,Algebra and Number Theory ,Skew ,Adjacency list ,Graph (abstract data type) ,Field (mathematics) ,Graph theory ,Adjacency matrix ,Mathematics - Abstract
B. Shader and W. So introduced the idea of the skew adjacency matrix. Their idea was to give an orientation to a simple undirected graph G from which a skew adjacency matrix S(G) is created. The -adjacency matrix extends this idea to an arbitrary field F. To study the underlying undirected graph, the average -characteristic polynomial can be created by averaging the characteristic polynomials over all the possible orientations. In particular, a Harary-Sachs theorem for the average-characteristic polynomial is derived and used to determine a few features of the graph from the average-characteristic polynomial.
- Published
- 2019
49. 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
50. Reliability assessment of distribution networks through graph theory, topology similarity and statistical analysis
- Author
-
Yue Xu, Tao Yu, and Bo Yang
- Subjects
Vertex (graph theory) ,Degree matrix ,Computer science ,020209 energy ,Energy Engineering and Power Technology ,Graph theory ,Topology (electrical circuits) ,02 engineering and technology ,Topology ,Similarity (network science) ,Control and Systems Engineering ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Adjacency matrix ,Electrical and Electronic Engineering ,Cluster analysis ,Reliability (statistics) - Abstract
This study aims to investigate the topology characteristic indices which have a close relationship with reliability of distribution networks via mathematical tools. First, a practical network is extracted into a topology and presented by weighted adjacency matrix associated with a failure degree matrix, which contains more significant information than that of original adjacency matrix. Second, singular value sequence and vertex/edge sharing are proposed as two similarity indices. Finally, similarity functions are applied on two cases to establish the relationship with reliability by curve fitting and clustering. optimisation strategy based on modified contingency-load-loss index is elaborated to improve the reliability and guide to distribution network planning.
- Published
- 2018
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.