74 results on '"Adjacency matrix"'
Search Results
2. Cospectral graphs : What properties are determined by the spectrum of a graph?
- 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
3. Energy of Graph
- Abstract
By given the adjacency matrix, laplacian matrix of a graph we can find the set of eigenvalues of graph in order to discussed about the energy of graph and laplacian energy of graph. (i.e. the sum of eigenvalues of adjacency matrix and laplacian matrix of a graph is called the energy of graph) and the laplacian energy of graph is greater or equal to zero for any graph and is greater than zero for every connected graph with more or two vertices (i.e. the last eigenvalues of laplacian matrix is zero), according to several theorems about the energy of graph and the laplacian energy of graph that are described in this work; I discussed about energy of graph, laplacian energy of graph and comparing them here.
- Published
- 2023
4. Energy of Graph
- Abstract
By given the adjacency matrix, laplacian matrix of a graph we can find the set of eigenvalues of graph in order to discussed about the energy of graph and laplacian energy of graph. (i.e. the sum of eigenvalues of adjacency matrix and laplacian matrix of a graph is called the energy of graph) and the laplacian energy of graph is greater or equal to zero for any graph and is greater than zero for every connected graph with more or two vertices (i.e. the last eigenvalues of laplacian matrix is zero), according to several theorems about the energy of graph and the laplacian energy of graph that are described in this work; I discussed about energy of graph, laplacian energy of graph and comparing them here.
- Published
- 2023
5. Energy of Graph
- Abstract
By given the adjacency matrix, laplacian matrix of a graph we can find the set of eigenvalues of graph in order to discussed about the energy of graph and laplacian energy of graph. (i.e. the sum of eigenvalues of adjacency matrix and laplacian matrix of a graph is called the energy of graph) and the laplacian energy of graph is greater or equal to zero for any graph and is greater than zero for every connected graph with more or two vertices (i.e. the last eigenvalues of laplacian matrix is zero), according to several theorems about the energy of graph and the laplacian energy of graph that are described in this work; I discussed about energy of graph, laplacian energy of graph and comparing them here.
- Published
- 2023
6. Fast search of the optimal contraction sequence in tensor networks
- Abstract
Tensor network and tensor computation are widely applied in scientific and engineering domains like quantum physics, electronic design automation, and machine learning. As one of the most fundamental operations for tensor networks, a tensor contraction eliminates the sharing orders among tensors and produces a compact sub-network. Different contraction sequence usually yields distinct storage and compute costs, and searching the optimal sequence is known as a hard problem. Prior work have designed heuristic and fast algorithms to solve this problem, however, several issues still remain unsolved. For example, the data format and data structure are not efficient, the constraints during modeling are impractical, the search of the optimal solution might fail, and the search cost is very high. In this paper, we first introduce a logk order representation and design an adjacency matrix-based data structure to efficiently accelerate the search of the optimal contraction sequence. Then, we propose an outer product pruning method with acceptable overhead to reduce the search space. Finally, we use a multithread optimization in our implementation to further improve the execution performance. We also present in-depth analysis of factors that influence the search time. This work provides a full-stack solution for optimal contraction sequence search from both high-level data structure and search algorithm to low-level execution parallelism, and it will benefit a broad range of tensor-related applications.
- Published
- 2021
7. Classic And Network Epidemiological Models
- Abstract
In this work is analyzed the environment and the dynamics of the states for a disease within a constant and closed population, represented by a system of ordinary differential equations, in which the individual, besides having the same opportunity to get in contact with any other, can recover or not, acquiring or not immunity through time. With these defined guidelines, the conditions when the disease spreads over time between such models are compared with those represented by a network. As the network can be represented by an adjacency matrix, the dynamics in the epidemiological states depends, besides the conditions in their parameters of the classic models, on largest eigenvalueof such matrix., En este trabajo se analiza el entorno y la dinámica de los estados para una enfermedad dentro de una población constante y cerrada, representado por un sistema de ecuaciones diferenciales ordinarias, en que el individuo, además de tener la misma oportunidad de entrar en contacto con cualquier otro, se pueda o no recuperar, adquiriendo o no inmunidad a través del tiempo. Con estos lineamientos definidos, se compara las condiciones cuando la enfermedad se propaga a lo largo del tiempo entre dichos modelos con los representados por una red. Como la red puede ser representado por una matriz de adyacencia, la dinámica en los estados epidemiológicos depende, además de las condiciones en sus parámetros de los modelos clásicos, del valor propio más grande de dicha matriz.
- Published
- 2021
8. Classic And Network Epidemiological Models
- Abstract
In this work is analyzed the environment and the dynamics of the states for a disease within a constant and closed population, represented by a system of ordinary differential equations, in which the individual, besides having the same opportunity to get in contact with any other, can recover or not, acquiring or not immunity through time. With these defined guidelines, the conditions when the disease spreads over time between such models are compared with those represented by a network. As the network can be represented by an adjacency matrix, the dynamics in the epidemiological states depends, besides the conditions in their parameters of the classic models, on largest eigenvalueof such matrix., En este trabajo se analiza el entorno y la dinámica de los estados para una enfermedad dentro de una población constante y cerrada, representado por un sistema de ecuaciones diferenciales ordinarias, en que el individuo, además de tener la misma oportunidad de entrar en contacto con cualquier otro, se pueda o no recuperar, adquiriendo o no inmunidad a través del tiempo. Con estos lineamientos definidos, se compara las condiciones cuando la enfermedad se propaga a lo largo del tiempo entre dichos modelos con los representados por una red. Como la red puede ser representado por una matriz de adyacencia, la dinámica en los estados epidemiológicos depende, además de las condiciones en sus parámetros de los modelos clásicos, del valor propio más grande de dicha matriz.
- Published
- 2021
9. On d-Fibonacci digraphs
- Abstract
The d-Fibonacci digraphs F(d, k), introduced here, have the number of vertices following some generalized Fibonacci-like sequences. They can be defined both as digraphs on alphabets and as iterated line digraphs. Here we study some of their nice properties. For instance, F(d, k) has diameter d + k - 2 and is semi-pancyclic; that is, it has a cycle of every length between 1 and l, with l ¿ {2k - 2, 2k - 1}. Moreover, it turns out that several other numbers of F(d, k) (of closed l-walks, classes of vertices, etc.) also follow the same linear recurrences as the numbers of vertices of the d-Fibonacci digraphs., This research has been 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 research of the first author has also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 734922., Peer Reviewed, Postprint (published version)
- Published
- 2021
10. Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem
- Abstract
Introducción: El problema de la ruta más corta o ruta de mínimo costo, ha sido uno de los temas más estudiados por áreas del conocimiento como la Investigación de Operaciones, la Ciencias de la Computación y la Decisión, las Telecomunicaciones, la Distribución en Planta, la Planeación de Proyectos, entre otras, buscando, por ejemplo; optimizar y reducir los costos que representan la distribución de mercancías, obtener la mínima cantidad de tiempo necesaria para finalizar un proyecto, o calcular la ruta más corta posible entre ordenadores conectados a una red. Objetivo: Estudiar el comportamiento de tres algoritmos voraces que permiten calcular la ruta de mínimo costo entre dos puntos (estado inicial y estado objetivo) en un grafo ponderado y con heurísticas. Metodología: Se implementó una aplicación en Java, y se ajustaron los algoritmos Greedy, A* y Dijkstra al problema en cuestión. Posteriormente se diseñaron dos casos de instancia, una negativa y otra positiva. Resultados: En los resultados de instancia negativa se modificó la heurística del nodo para permitir al algoritmo seleccionado escapar de óptimos locales y así, obtener un resultado completo, es decir llegar al estado objetivo, que, en algunas ocasiones, no necesariamente será el resultado más óptimo. Conclusiones: Mediante la comparación entre los tres algoritmos se pudo determinar que el algoritmo de Dijkstra siempre arroja resultados completos y óptimos. Por su parte, Greedy y A*, necesitan de heurísticas para llegar a un resultado completo, pero no óptimo., Introduction: The problem of the shortest route or minimum cost route, has been one of the topics most studied by areas of knowledge such as Operations Research, Computer Science and Decision, Telecommunications, Plant Distribution, Planning of Projects, among others, searching, for example; optimize and reduce the costs that represent the distribution of goods, obtain the minimum amount of time necessary to complete a project, or calculate the shortest possible route between computers connected to a network. Objective: We will study the behavior of three voracious algorithms that allow us to calculate the minimum cost route between two points (initial state and objective state) in a weighted graph and with heuristics. Method: Was implemented in Java, and the Greedy, A* and Dijkstra algorithms were adjusted to the problem in question. Subsequently, two instance cases were designed, one negative and one positive. Results: In the negative instance results the heuristic of the node was modified to allow the selected algorithm to escape from local optima and thus obtain a complete result, that is to say reach the objective state, which, in some cases, will not necessarily be the most optimal result. Conclusions: By comparing the three algorithms, it was determined that the Dijkstra algorithm always yields complete and optimal results. For its part, Greedy and A *, need heuristics to reach a complete result, but not optimal.
- Published
- 2020
11. Matrix Function for Solving Optimal Game Pass Strategy Summary
- Abstract
The breakthrough is to quantify the amount of water, food and money carried by people in the desert and to construct a discrete function with the number of days as a time variable, optimal Planning and design for the outflow of desert-walking resources and the introduction of resources and funds from the starting point, villages and mining areas, these resources and funds are fitted by the Adjacency Matrix and the coherent knowledge of probability to describe their dynamic changes with time (days). According to the restriction of the rules of the game, we try to find the optimal solution by computer software (Matlab) in order to reduce the computation of human brain.
- Published
- 2020
12. Matrix Function for Solving Optimal Game Pass Strategy Summary
- Abstract
The breakthrough is to quantify the amount of water, food and money carried by people in the desert and to construct a discrete function with the number of days as a time variable, optimal Planning and design for the outflow of desert-walking resources and the introduction of resources and funds from the starting point, villages and mining areas, these resources and funds are fitted by the Adjacency Matrix and the coherent knowledge of probability to describe their dynamic changes with time (days). According to the restriction of the rules of the game, we try to find the optimal solution by computer software (Matlab) in order to reduce the computation of human brain.
- Published
- 2020
13. Degree Distance and Gutman Index of Two Graph Products
- Abstract
The degree distance was introduced by Dobrynin, Kochetova and Gutman as a weighted version of the Wiener index. In this paper, we investigate the degree distance and Gutman index of complete, and strong product graphs by using the adjacency and distance matrices of a graph.
- Published
- 2020
14. Degree Distance and Gutman Index of Two Graph Products
- Abstract
The degree distance was introduced by Dobrynin, Kochetova and Gutman as a weighted version of the Wiener index. In this paper, we investigate the degree distance and Gutman index of complete, and strong product graphs by using the adjacency and distance matrices of a graph.
- Published
- 2020
15. Matrix Function for Solving Optimal Game Pass Strategy Summary
- Abstract
The breakthrough is to quantify the amount of water, food and money carried by people in the desert and to construct a discrete function with the number of days as a time variable, optimal Planning and design for the outflow of desert-walking resources and the introduction of resources and funds from the starting point, villages and mining areas, these resources and funds are fitted by the Adjacency Matrix and the coherent knowledge of probability to describe their dynamic changes with time (days). According to the restriction of the rules of the game, we try to find the optimal solution by computer software (Matlab) in order to reduce the computation of human brain.
- Published
- 2020
16. A general method to obtain the spectrum and local spectra of a graph from its regular partitions
- Abstract
It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also the local spectra, of a graph from the quotient matrices of some of its regular partitions, is proposed. Moreover, from such partitions, the C -local multiplicities of any class of vertices C is also determined, and some applications of these parameters in the characterization of completely regular codes and their inner distributions are described. As examples, it is shown how to find the eigenvalues and (local) multiplicities of walk-regular, distance-regular, and distance-biregular graphs., Received by the editors on February 20, 2020. Accepted for publication on May 27, 2020. Handling Editor: Sebastian M.Cioaba. Corresponding Author: Cristina Dalf ́o.†Departament de Matem`atica, Universitat de Lleida, Igualada (Barcelona), Catalonia (cristina.dalfo@udl.cat). Partiallysupported by AGAUR from the Catalan Government under project 2017SGR1087 and by MICINN from the Spanish Governmentunder projects PGC2018-095471-B-I00 and MTM2017-83271-R. Also received funding from the European Union’s Horizon 2020research and innovation programme under the Marie Sk lodowska-Curie grant agreement no. 734922.‡Departament de Matem`atiques, Barcelona Graduate School of Mathematics, Universitat Polit`ecnica de Catalunya,Barcelona, Catalonia, (miguel.angel.fiol@upc.edu). Partially supported by AGAUR from the Catalan Government under project2017SGR1087 and by MICINN from the Spanish Government under project PGC2018-095471-B-I00., Peer Reviewed, Postprint (author's final draft)
- Published
- 2020
17. (1, ≤ ℓ)-identifying codes in digraphs and graphs
- Abstract
The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the, El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre tod, Postprint (published version)
- Published
- 2020
18. Network-scale arterial traffic state prediction: Fusing multisensor traffic data
- Abstract
Road traffic congestion is an increasing societal problem. Road agencies and users seeks accurate and reliable travel speed information. This thesis developed a network-scale traffic state prediction based on Convolutional Neural Network (CNN). The method can predict the speed over the network accurately by preserving road connectivity and incorporating historical datasets. When dealing with an extensive network, the thesis also developed a clustering method to reduce the complexity of the prediction. By accurately predict the traffic state over a network, traffic operators can manage the network more effectively and travellers can make informed decision on their journeys.
- Published
- 2020
19. Degree Distance and Gutman Index of Two Graph Products
- Abstract
The degree distance was introduced by Dobrynin, Kochetova and Gutman as a weighted version of the Wiener index. In this paper, we investigate the degree distance and Gutman index of complete, and strong product graphs by using the adjacency and distance matrices of a graph.
- Published
- 2020
20. Degree Distance and Gutman Index of Two Graph Products
- Abstract
The degree distance was introduced by Dobrynin, Kochetova and Gutman as a weighted version of the Wiener index. In this paper, we investigate the degree distance and Gutman index of complete, and strong product graphs by using the adjacency and distance matrices of a graph.
- Published
- 2020
21. Bipartite Structured Gaussian Graphical Modeling via Adjacency Spectral Priors
- Abstract
Learning a graph with a bipartite structure IS essential for interpretability and identification of the relationships among data in numerous applications including document clustering, network medicine, etc. To learn a bipartite structure is equivalent to a max-cut problem, which is an NP-hard problem. Existing methods employ a two-stage procedure and are computationally demanding as they require solving semi-definite programming. In this paper, we introduce a bipartite graph learning framework lying at the integration of Gaussian graphical models (GGM) and spectral graph theory. The proposed algorithms are provably convergent and practically amenable for large-scale unsupervised graph learning tasks. Numerical experiments demonstrate the effectiveness of the proposed algorithm over existing state-of-the-art methods. An R package containing code for all the experimental results is available at https://cran.r-project.org/package=spectralGraphTopology.
- Published
- 2019
22. Graph theory and definitions
- Abstract
Graphs are a mathematical structure composed of a set of elements, and a set of connection between them. Due to their intuitive representation, graphs are widely employed in many different fields and, in particular, in systems biology and bioinformatics. In fact, they are used to model biological networks is several case studies, but also to represent data structures in different algorithmic procedures for solving bioinformatic problems. One of the key points of this widespread adoption is also related to the strong mathematical formulation behind them. In this article, we will introduce the basic concepts of graphs, starting from their definition and the description of simple notions. We will also describe specific types of graphs, like bipartite graphs and multigraphs, and we will explain two possible representations, namely adjacency lists and adjacency matrix. Finally, we will focus on bipartite graphs, by proposing an intuitive procedure to check if a graph is bipartite.
- Published
- 2019
23. A comparison of graph centrality measures based on random walks and their computation
- Abstract
When working with a network it is often of interest to locate the "most important" nodes in the network. A common way to do this is using some graph centrality measures. Since what constitutes an important node is different between different networks or even applications on the same network there is a large amount of different centrality measures proposed in the literature. Due to the large amount of different centrality measures proposed in different fields, there is also a large amount very similar or equivalent centrality measures in the sense that they give the same ranks. In this paper we will focus on centrality measures based on powers of the adjacency matrix or similar matrices and those based on random walk in order to show how some of these are related and can be calculated efficiently using the same or slightly altered algorithms.
- Published
- 2019
24. Bipartite Structured Gaussian Graphical Modeling via Adjacency Spectral Priors
- Abstract
Learning a graph with a bipartite structure IS essential for interpretability and identification of the relationships among data in numerous applications including document clustering, network medicine, etc. To learn a bipartite structure is equivalent to a max-cut problem, which is an NP-hard problem. Existing methods employ a two-stage procedure and are computationally demanding as they require solving semi-definite programming. In this paper, we introduce a bipartite graph learning framework lying at the integration of Gaussian graphical models (GGM) and spectral graph theory. The proposed algorithms are provably convergent and practically amenable for large-scale unsupervised graph learning tasks. Numerical experiments demonstrate the effectiveness of the proposed algorithm over existing state-of-the-art methods. An R package containing code for all the experimental results is available at https://cran.r-project.org/package=spectralGraphTopology.
- Published
- 2019
25. Characterizing identifying codes from the spectrum of a graph or digraph
- Abstract
A -identifying code in digraph D is a dominating subset C of vertices of D, such that all distinct subsets of vertices of D with cardinality at most l have distinct closed in-neighborhoods within C. As far as we know, it is the very first time that the spectral graph theory has been applied to the identifying codes. We give a new method to obtain an upper bound on l for digraphs. The results obtained here can also be applied to graphs., Peer Reviewed, Postprint (author's final draft)
- Published
- 2019
26. An algebraic approach to lifts of digraphs
- Abstract
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, We study the relationship between two key concepts in the theory of (di)graphs: the quotient digraph, and the lift Ga of a base (voltage) digraph. These techniques contract or expand a given digraph in order to study its characteristics, or obtain more involved structures. This study is carried out by introducing a quotient-like matrix, with complex polynomial entries, which fully represents Ga. In particular, such a matrix gives the quotient matrix of a regular partition of Ga, and when the involved group is Abelian, it completely determines the spectrum of Ga. As some examples of our techniques, we study some basic properties of the Alegre digraph. In addition we completely characterize the spectrum of a new family of digraphs, which contains the generalized Petersen graphs, and that of the Hoffman-Singleton graph, Peer Reviewed, Postprint (published version)
- Published
- 2019
27. The spectra of lifted digraphs
- Abstract
This is a post-peer-review, pre-copyedit version of an article published in Journal of algebraic combinatorics. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10801-018-0862-y, We present a method to derive the complete spectrum of the lift Ga of a base digraph G, with voltage assignment a on a (finite) group G. The method is based on assigning to G a quotient-like matrix whose entries are elements of the group algebra C[G], which fully represents Ga. This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalizes some previous results of Lov´asz and Babai concerning the spectra of Cayley digraphs, Peer Reviewed, Postprint (author's final draft)
- Published
- 2019
28. On spectra of weighted graphs of order ≤5
- Abstract
Producción Científica, The problem of characterizing the real spectra of weighted graphs is only solved for weighted graphs of order n ≤ 4. We overview these known results, that come from the context of nonnegative matrices, and give a new method to rule out many unresolved spectra of size 5., Ministerio de Economía, Industria y Competitividad ( grant MTM2015-365764-C3-1-P), Universidad de Valladolid (GIR TAMCO)
- Published
- 2018
29. On spectra of weighted graphs of order ≤5
- Abstract
Producción Científica, The problem of characterizing the real spectra of weighted graphs is only solved for weighted graphs of order n ≤ 4. We overview these known results, that come from the context of nonnegative matrices, and give a new method to rule out many unresolved spectra of size 5., Ministerio de Economía, Industria y Competitividad ( grant MTM2015-365764-C3-1-P), Universidad de Valladolid (GIR TAMCO)
- Published
- 2018
30. On spectra of weighted graphs of order ≤5
- Abstract
Producción Científica, The problem of characterizing the real spectra of weighted graphs is only solved for weighted graphs of order n ≤ 4. We overview these known results, that come from the context of nonnegative matrices, and give a new method to rule out many unresolved spectra of size 5., Ministerio de Economía, Industria y Competitividad ( grant MTM2015-365764-C3-1-P), Universidad de Valladolid (GIR TAMCO)
- Published
- 2018
31. Characterizing identifying codes through the spectrum of a graph or digraph
- Abstract
Postprint (author's final draft)
- Published
- 2017
32. The spectra of subKautz and cyclic Kautz digraphs
- Abstract
© 2017. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0, Kautz digraphs K(d,l) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related with these, the cyclic Kautz CK(d,l) and the subKautz sK(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 sK(d,2) and cyclic Kautz CK(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., Postprint (author's final draft)
- Published
- 2017
33. Eigenvectors of Random Matrices: A Survey
- Abstract
Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random.
- Published
- 2016
34. MODEL OF THE QUALITY MANAGEMENT SYSTEM OF A MACHINE TOOL COMPANY
- Abstract
Development of models and methods such that would improve the competitive position of enterprises by improving management processes is an important task of project management. Lack of project management within the information technology and continuous improvement of methods for the management of the environment, interaction, community, value and trust, based on the strategic objectives of enterprises and based on models that take into account the relationship of the system, resulting in significant material and resource costs. In the current work the improvement of the quality management system machine-tool company HC MIKRON® and proved that the introduction of new processes critical analysis requirements for products, support processes of the products to consumers and enterprises in the formation of a system of responsibility, division of responsibilities and reporting (according to ISO 9001: 2009) is an important scientific and reasonable step to improve the level of technological maturity and structural modernization of enterprise management. For the improved structure of the analysis model and test the properties of ergodicity, as a condition of efficiency, a new quality management system., Разработка моделей и методов, позволяющих повысить конкурентоспособность предприятий за счет усовершенствования процессов управления, является важной задачей проектного управления. В работе выполнено усовершенствование существующей системы менеджмента качества станкостроительного предприятия ХК МІКРОН® и доказано, что внедрение новых процессов (в соответствии с ДСТУ ISO 9001:2009) является важным и научно-подтвержденным мероприятием, направленным на повышение уровня технологической зрелости предприятия и его структурной модернизации., Розробка моделей та методів, які б дозволили підвищувати конкурентну спроможність підприємств за рахунок вдосконалення процесів управління є важливим завданням проектного менеджменту. У роботі виконано удосконалення існуючої системи менеджменту якості верстатобудівного підприємства ХК МІКРОН® та доведено, що введення нових процесів (відповідно до ISO 9001:2009) є важливим й науково-обґрунтованим кроком для підвищення рівня технологічної зрілості підприємства та структурної модернізації управління.
- Published
- 2016
35. Eigenvectors of Random Matrices: A Survey
- Abstract
Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random. Published by Elsevier Inc.
- Published
- 2016
36. Eigenvectors of Random Matrices: A Survey
- Abstract
Eigenvectors of large matrices (and graphs) play an essential role in combinatorics and theoretical computer science. The goal of this survey is to provide an up-to-date account on properties of eigenvectors when the matrix (or graph) is random. Published by Elsevier Inc.
- Published
- 2016
37. A note on the order of iterated line digraphs
- Abstract
Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices n_k of the k-iterated line digraph L_k(G), for k>= 0, where L_0(G) = G. We obtain this result by using the minimal polynomial of a quotient digraph pi(G) of G. We show some examples of this method applied to the so-called cyclic Kautz, the unicyclic, and the acyclic digraphs. In the first case, our method gives the enumeration of the ternary length-2 squarefree words of any length., Peer Reviewed, Postprint (author's final draft)
- Published
- 2016
38. Cospectral digraphs from locally line digraphs
- Abstract
A digraph Gamma = (V, E) is a line digraph when every pair of vertices u, v is an element of V have either equal or disjoint in -neighborhoods. When this condition only applies for vertices in a given subset (with at least two elements), we say that Gamma is a locally line digraph. In this paper we give a new method to obtain a digraph Gamma' cospectral with a given locally line digraph Gamma with diameter D, where the diameter D' of Gamma' is in the interval [D - 1, D + 1]. In particular, when the method is applied to De Bruijn or Kautz digraphs, we obtain cospectral digraphs with the same algebraic properties that characterize the formers. (C) 2016 Elsevier Inc. All rights reserved., Peer Reviewed, Postprint (author's final draft)
- Published
- 2016
39. Directed pseudo-graphs and Lie algebras over finite fields
- Abstract
The main goal of this paper is to show an application of Graph Theory to classifying Lie algebras over finite fields. It is rooted in the representation of each Lie algebra by a certain pseudo-graph. As partial results, it is deduced that there exist, up to isomorphism, four, six, fourteen and thirty-four 2-, 3-, 4-, and 5-dimensional algebras of the studied family, respectively, over the field Z/2Z. Over Z/3Z, eight and twenty-two 2-and 3-dimensional Lie algebras, respectively, are also found. Finally, some ideas for future research are presented.
- Published
- 2014
40. Directed pseudo-graphs and Lie algebras over finite fields
- Abstract
The main goal of this paper is to show an application of Graph Theory to classifying Lie algebras over finite fields. It is rooted in the representation of each Lie algebra by a certain pseudo-graph. As partial results, it is deduced that there exist, up to isomorphism, four, six, fourteen and thirty-four 2-, 3-, 4-, and 5-dimensional algebras of the studied family, respectively, over the field Z/2Z. Over Z/3Z, eight and twenty-two 2-and 3-dimensional Lie algebras, respectively, are also found. Finally, some ideas for future research are presented.
- Published
- 2014
41. Directed pseudo-graphs and Lie algebras over finite fields
- Abstract
The main goal of this paper is to show an application of Graph Theory to classifying Lie algebras over finite fields. It is rooted in the representation of each Lie algebra by a certain pseudo-graph. As partial results, it is deduced that there exist, up to isomorphism, four, six, fourteen and thirty-four 2-, 3-, 4-, and 5-dimensional algebras of the studied family, respectively, over the field Z/2Z. Over Z/3Z, eight and twenty-two 2-and 3-dimensional Lie algebras, respectively, are also found. Finally, some ideas for future research are presented.
- Published
- 2014
42. Directed pseudo-graphs and Lie algebras over finite fields
- Abstract
The main goal of this paper is to show an application of Graph Theory to classifying Lie algebras over finite fields. It is rooted in the representation of each Lie algebra by a certain pseudo-graph. As partial results, it is deduced that there exist, up to isomorphism, four, six, fourteen and thirty-four 2-, 3-, 4-, and 5-dimensional algebras of the studied family, respectively, over the field Z/2Z. Over Z/3Z, eight and twenty-two 2-and 3-dimensional Lie algebras, respectively, are also found. Finally, some ideas for future research are presented.
- Published
- 2014
43. Directed pseudo-graphs and Lie algebras over finite fields
- Abstract
The main goal of this paper is to show an application of Graph Theory to classifying Lie algebras over finite fields. It is rooted in the representation of each Lie algebra by a certain pseudo-graph. As partial results, it is deduced that there exist, up to isomorphism, four, six, fourteen and thirty-four 2-, 3-, 4-, and 5-dimensional algebras of the studied family, respectively, over the field Z/2Z. Over Z/3Z, eight and twenty-two 2-and 3-dimensional Lie algebras, respectively, are also found. Finally, some ideas for future research are presented.
- Published
- 2014
44. On graph differential equations and its associated matrix differential equations
- Abstract
Networks are one of the basic structures in many physical phenomena pertaining to engineering applications. As a network can be represented by a graph which is isomorphic to its adjacency matrix, the study of analysis of networks involving rate of change with respect to time reduces to the study of graph differential equations or equivalently matrix differential equations. In this paper, we develop the basic infrastructure to study the IVP of a graph differential equation and the corresponding matrix differential equation. Criteria are obtained to guarantee the existence of a solution and an iterative technique for convergence to the solution of a matrix differential equation is developed.
- Published
- 2013
45. On graph differential equations and its associated matrix differential equations
- Abstract
Networks are one of the basic structures in many physical phenomena pertaining to engineering applications. As a network can be represented by a graph which is isomorphic to its adjacency matrix, the study of analysis of networks involving rate of change with respect to time reduces to the study of graph differential equations or equivalently matrix differential equations. In this paper, we develop the basic infrastructure to study the IVP of a graph differential equation and the corresponding matrix differential equation. Criteria are obtained to guarantee the existence of a solution and an iterative technique for convergence to the solution of a matrix differential equation is developed.
- Published
- 2013
46. Neke klase spektralno ograničenih grafova
- Abstract
Spektralna teorija grafova je grana matematike koja je nastala pedesetih godina pro²log veka i od tada se neprestano razvija. Njen zna£aj ogleda se u brojnim primenama, naro£ito u hemiji, zici, ra£unarstvu i drugim naukama. Grane matematike, kao ²to su linearna algebra i, posebno, teorija matrica imaju vaºnu ulogu u spektralnoj teoriji grafova. Postoje razli£ite matri£ne reprezentacije grafa. Najvi ²e su izu£avane matrica susedstva grafa i Laplasova (P.S. Laplace) matrica, a zatim i Zajdelova (J.J. Seidel) i takozvana nenegativna Laplasova matrica. Spektralna teorija grafova u su²tini uspostavlja vezu izme u strukturalnih osobina grafa i algebarskih osobina njegove matrice, odnosno razmatra o kojim se strukturalnim osobinama (kao ²to su povezanost, bipartitnost, regularnost i druge) mogu dobiti informacije na osnovu nekih svojstava sopstvenih vrednosti njegove matrice. Veliki broj dosada²njih rezultata iz ovog ²irokog polja istraºivanja moºe se na¢i u slede¢im monograjama: [20], [21], [23] i [58]. Disertacija sadrºi originalne rezultate dobijene u nekoliko podoblasti spektralne teorije grafova. Ti rezultati izloºeni su u tri celine glave, od kojih je svaka podeljena na poglavlja, a neka od njih na potpoglavlja. Na po£etku svake glave, u posebnom poglavlju, formulisan je problem koji se u toj glavi razmatra, kao i postoje¢i rezultati koji se odnose na zadati problem, a neophodni su za dalja razmatranja. U ostalim poglavljima predstavljeni su originalni rezultati, koji se nalaze i u radovima [3], [4], [47], [48], [49], [50], [51] i [52]. U prvoj glavi razmatra se druga sopstvena vrednost regularnih grafova. Postoji dosta rezultata o grafovima £ija je druga po veli£ini sopstvena vrednost ograni£ena odozgo nekom (relativno malom) konstantom. Posebno, druga sopstvena vrednost ima zna£ajnu ulogu u odre ivanju strukture regularnih grafova. Poznata je karakterizacija regularnih grafova koji imaju samo jednu pozitivnu sopstvenu vrednost (videti [20]), a razmatrani su i regul, Spectral graph theory is a branch of mathematics that emerged more than sixty years ago, and since then has been continuously developing. Its importance is reected in many interesting and remarkable applications, esspecially in chemistry, physics, computer sciences and other. Other areas of mathematics, like linear algebra and matrix theory have an important role in spectral graph theory. There are many dierent matrix representations of a given graph. The ones that have been studied the most are the adjacency matrix and the Laplace matrix, but also the Seidel matrix and the so-called signless Laplace matrix. Basically, the spectral graph theory establishes the connection between some structrural properties of a graph and the algebraic properties of its matrix, and considers structural properties that can be described using the properties of the eigenvalues of its matrix. Systematized former results from this vast eld of algebraic graph theory can be found in the following monographs: [20], [21], [23] i [58]. This thesis contains original results obtained in several subelds of the spectral graph theory. Those results are presented within three chapters. Each chapter is divided into sections, and some sections into subsections. At the beginning of each chapter (in an appropriate sections), we formulate the problem considered within it, and present the existing results related to this problem, that are necessary for further considerations. All other sections contain only original results. Those results can also be found in the following papers: [3], [4], [47], [48], [49], [50], [51] and [52]. In the rst chapter we consider the second largest eigenvalue of a regular graph. There are many results concerning graphs whose second largest eigenvalue is upper bounded by some (relatively small) constant. The second largest eigenvalue plays an important role in determining the structure of regular graphs. There is a known characterization of regular graphs with only one positiv
- Published
- 2013
47. Автоматизація розв’язання екстремальних задач на графах у конструкторському проектуванні РЕА
- Abstract
Розглянуті можливості розв’язання задач конструкторського проектування РЕА, що зводяться до екстремальних задач на графах, за допомогою надбудови Solver MS Excel. Запропоновані моделі задач, які дають змогу знаходити екстремальні шляхи та мінімальні покриття (мінімальні остівні дерева) для графів довільної складності. У моделі введені обмеження зв’язності оптимальних маршрутів перевезень, які реалізовані як обмеження балансу потоків через транзитні пункти. Це дозволило звести розв’язвання моделі до розв’язання задачі лінійного програмування, яке підтримується стандартними процедурами MS Excel Solver.
- Published
- 2013
48. Automatization of solving the extremal problems on graphs in radioelectronic apparatus design
- Abstract
Possibilities of solving by MS Excel Add-in Solver the REA design problems modeled as the extremal graph problems are considered. Offered problem models enable to find extreme paths and minimum vertex covers (minimum spinning trees) for the graphs of any complexity. Constraints of graph connectivity for optimal routes are introduced in the model. These constraints are realized as constraints of flow balance in transit network points. That allowed to add the problem up to a linear programming problem, solving of which is correctly supported by MS Excel Solver common procedures., Рассмотрены возможности решения с помощью надстройки Solver MS Excel задач конструкторского проектирования РЕА, сводящиеся к экстремальным задачам на графах. Предложенны модели задач, дающие возможность находить экстремальные пути и минимальные покрытия (минимальные остовные деревья) для графов произвольной сложности. В модели введены ограничения связности оптимальных маршрутов перевозок, которые реализованы как ограничения балансов потоков через транзитные пункты. Это позволило свести решение модели к решению задачи линейного программирования, которое поддерживается стандартными процедурами MS Excel Solver., Розглянуті можливості розв’язання задач конструкторського проектування РЕА, що зводяться до екстремальних задач на графах, за допомогою надбудови Solver MS Excel. Запропоновані моделі задач, які дають змогу знаходити екстремальні шляхи та мінімальні покриття (мінімальні остівні дерева) для графів довільної складності. У моделі введені обмеження зв’язності оптимальних маршрутів перевезень, які реалізовані як обмеження балансу потоків через транзитні пункти. Це дозволило звести розв’язвання моделі до розв’язання задачі лінійного програмування, яке підтримується стандартними процедурами MS Excel Solver.
- Published
- 2013
49. Cluster detection in cytology images using the cellgraph method
- Abstract
Automated cervical cancer detection system is primarily based on delineating the cell nuclei and analyzing their textural and morphometric features for malignant characteristics. The presence of cell clusters in the slides have diagnostic value, since malignant cells have a greater tendency to stick together forming clusters than normal cells. However, cell clusters pose difficulty in delineating nucleus and extracting features reliably for malignancy detection in comparison to free lying cells. LBC slide preparation techniques remove biological artifacts and clustering to some extent but not completely. Hence cluster detection in automated cervical cancer screening becomes significant. In this work, a graph theoretical technique is adopted which can identify and compute quantitative metrics for this purpose. This method constructs a cell graph of the image in accordance with the Waxman model, using the positional coordinates of cells. The computed graph metrics from the cell graphs are used as the feature set for the classifier to deal with cell clusters. It is a preliminary exploration of using the topological analysis of the cellgraph to cytological images and the accuracy of classification using SVM showed that the results are well suited for cluster detection.
- Published
- 2012
- Full Text
- View/download PDF
50. Role of Adjacency Matrix & Adjacency List in Graph Theory
- 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
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.