347 results on '"Adjacency matrix"'
Search Results
2. BOUNDS FOR THE α-ADJACENCY ENERGY OF A GRAPH.
- Author
-
SHABAN, REZWAN UL, IMRAN, MUHAMMAD, and GANIE, HILAL A.
- Subjects
GRAPH theory ,EIGENVALUES ,CONVEX functions ,RAYLEIGH quotient ,GRAPH connectivity - Abstract
For the adjacency matrix A(G) and diagonal matrix of the vertex degrees D(G) of a simple graph G, the A(G) matrix is the convex combinations of D(G) and A(G), and is defined as A(G) = D(G)+(1)A(G), for 0 n be the eigenvalues of A(G) (which we call -adjacency eigenvalues of the graph G). The generalized adjacency energy also called -adjacency energy of the graph G is defined as EA (G) = is the average vertex degree, m is the size and n is the order of G. The -adjacency energy of a graph G merges the theory of energy (adjacency energy) and the signless Laplacian energy, as EA0 (G) = E (G) and 2E A 12 (G) = QE(G), where E (G) is the energy and QE(G) is the signless Laplacian energy of G. In this paper, we obtain some new upper and lower bounds for the generalized adjacency energy of a graph, in terms of different graph parameters like the vertex covering number, the Zagreb index, the number of edges, the number of vertices, etc. We characterize the extremal graphs attained these bounds. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
3. Topological relation expression and verification of symmetrical parallel mechanism based on the evolution of chemical molecule.
- Author
-
He, Litao, Fang, Hairong, and Zhang, Dan
- Published
- 2023
- Full Text
- View/download PDF
4. Some Properties of Double Domination in Vague Graphs with an Application.
- Author
-
Rao, Yongsheng, Cai, Ruiqi, Talebi, Ali Asghar, and Mojahedfar, Masomeh
- Subjects
- *
GRAPH theory , *DOMINATING set , *FUZZY graphs , *ENERGY consumption , *SYMMETRY - Abstract
This paper is devoted to the study of the double domination in vague graphs, and it is a contribution to the Special Issue "Advances in graph theory and Symmetry/Asymmetry" of Symmetry. Symmetry is one of the most important criteria that illustrate the structure and properties of fuzzy graphs. It has many applications in dominating sets and helps find a suitable place for construction. Vague graphs (VGs), which are a family of fuzzy graphs (FGs), are a well-organized and useful tool for capturing and resolving a range of real-world scenarios involving ambiguous data. In the graph theory, a dominating set (DS) for a graph G * = (X , E) is a subset D of the vertices X so that every vertex which is not in D is adjacent to at least one member of D. The subject of energy in graph theory is one of the most attractive topics serving a very important role in biological and chemical sciences. Hence, in this work, we express the notion of energy on a dominating vague graph (DVG) and also use the concept of energy in modeling problems related to DVGs. Moreover, we introduce a new notion of a double dominating vague graph (DDVG) and provide some examples to explain various concepts introduced. Finally, we present an application of energy on DVGs. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
5. 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
6. Spectrum of prism graph and relation with network related quantities.
- Author
-
Raza, Ali, Munir, Mobeen, Abbas, Tasawar, Eldin, Sayed M., and Khan, Ilyas
- Subjects
GRAPH theory ,STABILITY theory ,POLYHEDRA ,SPANNING trees ,RADIUS (Geometry) - Abstract
Spectra of network related graphs have numerous applications in computer sciences, electrical networks and complex networks to explore structural characterization like stability and strength of these different real-world networks. In present article, our consideration is to compute spectrum based results of generalized prism graph which is well-known planar and polyhedral graph family belongs to the generalized Petersen graphs. Then obtained results are applied to compute some network related quantities like global mean-first passage time, average path length, number of spanning trees, graph energies and spectral radius. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
7. BOUNDS FOR THE EIGENVALUES OF GALLAI GRAPHS OF SOME GRAPHS.
- Author
-
PALATHINGAL, JEEPAMOL J.
- Subjects
EIGENVALUES ,GRAPH theory ,MATHEMATICAL bounds ,GEOMETRIC vertices ,SET theory - Abstract
The line graph L(G), of a graph G has the edges of G as its vertices and two distinct edges of G are adjacent in L(G), if they are adjacent in G. The Gallai graph (G) of a graph G, has the edges of G as its vertices and two distinct vertices are adjacent in (G) if they are adjacent edges in G, but do not lie on a triangle. The anti-Gallai graph κ(G) of a graph G has the edges of G as its vertices and two distinct edges of G are adjacent in κ(G), if they lie on a common triangle in G. In this paper we find bounds for the eigenvalues of Gallai graph of some class of graphs by using the adjacency spectrum of line graph and anti-Gallai graph. [ABSTRACT FROM AUTHOR]
- Published
- 2023
8. Improving the BB84 quantum key distribution protocol as based on graph theory.
- Author
-
Khalaf, R. Z., Abdul-Kareem, A. S., and Mahdi, S. S.
- Subjects
- *
QUANTUM cryptography - Abstract
Key distribution is considered to be among the most significant stages in any cryptographic system, and quantum key distribution is a secure method used to exchange keys between entities involved in communication. In this study, we propose to improve the BB84-quantum key distribution protocol using graph-based coding, where agreement between the two parties is agreed on the graph used in quantum-bases encoding at both ends. This paper presents a simulation of the proposed protocol using python language. The experimental results, which have been very promising, show that the proposed protocol is more effective and secure than the standard BB84 protocol. [ABSTRACT FROM AUTHOR]
- Published
- 2022
9. 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
10. Aα matrix of commuting graphs of non-abelian groups.
- Author
-
Rather, Bilal A., Ali, Fawad, Ullah, Nasim, Mohammad, Al-Sharef, Din, Anwarud, and Sehra
- Subjects
EIGENVALUES ,EIGENANALYSIS ,EXPONENTIAL stability ,LAPLACIAN matrices ,GRAPH theory - Abstract
For a finite group G and a subset X≠ 0 of G, the commuting graph, indicated by G = C(G, X), is the simple connected graph with vertex set X and two distinct vertices x and y are edge connected in G if and only if they commute in X. The Aα matrix of G is specified as A
α (G) = αD(G) + (1-α)A(G), α ∈ [0, 1], where D(G) is the diagonal matrix of vertex degrees while A(G) is the adjacency matrix of G. In this article, we investigate the Aα matrix for commuting graphs of finite groups and we also find the Aα eigenvalues of the dihedral, the semidihedral and the dicyclic groups. We determine the upper bounds for the largest Aα eigenvalue for these graphs. Consequently, we get the adjacency eigenvalues, the Laplacian eigenvalues, and the signless Laplacian eigenvalues of these graphs for particular values of α. Further, we show that these graphs are Laplacian integral. [ABSTRACT FROM AUTHOR]- Published
- 2022
- Full Text
- View/download PDF
11. Application of Fiedler Value for Mitigation of Loss of Connectivity in Wireless Mesh Networks.
- Author
-
Pandey, Soma and Kadambi, Govind R.
- Subjects
WIRELESS mesh networks ,WIRELESS communications ,EIGENVALUES ,LAPLACIAN matrices ,GRAPH theory - Abstract
This paper proposes a new scheme for very fast detection of a sensor going offline or loss of connectivity of sensor in Wireless Mesh Networks (WMN) in order to avoid any packet loss. A sensor is declared offline by a gateway if it does not receive any packet from the sensor for a specific time interval termed as keep-alive time. In mesh networks, this keep-alive window is kept for a very long duration; sometimes it is as high as 2.5 to 3 hours. The time duration is kept high so that gateway does not declare a sensor that is in deep sleep to conserve battery, as offline. However, keeping a large keep-alive time window leads to the very likely possibility of missing the timely detection of a critical event like a smoke sensor or gas leak sensor going offline. In the proposed method, the gateway maintains its table of neighbourhood matrix in order to facilitate fast and efficient tracking as well as tracing of the nodes for the detection of the loss of connectivity of a sensor. A Laplacian matrix formulation proposed by Fiedler is invoked for tracking and tracing lost nodes of WMN. Through the Fiedler value, this paper substantiates the efficacy of monitoring a large WMN not only for its algebraic connectivity but also to compute the number of disconnected partitions in it. This is achieved through the number of null values of eigenvalues of the Laplacian matrix of the graph of WMN. Through simulation studies, this paper demonstrates achieving an 88 % success rate in the detection of disconnection with an average latency of 39.806 ms. On the contrary, a conventional process for the time duration after which a sensor can be declared offline might be an hour or even more depending upon the pre-set duration of the keep-alive time window. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
12. A Matrix Model to Analyze Cascading Failure in Critical Infrastructures
- Author
-
Gueye, Assane, Mbaye, Babacar, Fall, Doudou, Diop, Alassane, Kashihara, Shigeru, Akan, Ozgur, Editorial Board Member, Bellavista, Paolo, Editorial Board Member, Cao, Jiannong, Editorial Board Member, Coulson, Geoffrey, Editorial Board Member, Dressler, Falko, Editorial Board Member, Ferrari, Domenico, Editorial Board Member, Gerla, Mario, Editorial Board Member, Kobayashi, Hisashi, Editorial Board Member, Palazzo, Sergio, Editorial Board Member, Sahni, Sartaj, Editorial Board Member, Shen, Xuemin (Sherman), Editorial Board Member, Stan, Mircea, Editorial Board Member, Jia, Xiaohua, Editorial Board Member, Zomaya, Albert Y., Editorial Board Member, Thorn, Jessica P. R., editor, Gueye, Assane, editor, and Hejnowicz, Adam P., editor
- Published
- 2020
- Full Text
- View/download PDF
13. An Encryption Technique Using A Complete Graph With A Self-Invertible Matrix.
- Author
-
Mohan, P., Rajendran, K., and Rajesh, A.
- Subjects
- *
GRAPH theory , *COMPUTATIONAL complexity , *MATRICES (Mathematics) , *INTERNET - Abstract
Nowadays, the process of message encryption is the most important thing to secure our messages and communication between people. Message encryption methods are rapidly increasing currently due to the growth and evolution of the internet and network communications. Sharing information, personal messages, images, or data from one person to another over unsecured channels opens the door for attack, or hacking. To reduce this terminology and to provide better security, cryptographic or encryption techniques play an essential role. We have many kinds of symmetric enciphering techniques like the Caesar Cipher, Atbash Cipher, Hill Cipher, etc., In this paper, we are going to give the enciphering technique with the help of a complete graph, an adjacency matrix, and a generated self-invertible key matrix to encrypt and decrypt the given messages to produce a complicated ciphertext. Since we are using the self-invertible matrix as a key matrix, the inverse of this key matrix is always existing, and while we are decrypting the ciphertext, we do not need to compute the inverse of the key matrix. It helps us to reduce the computational complexity involved in the process of finding the inverse of a key matrix. [ABSTRACT FROM AUTHOR]
- Published
- 2022
14. Parametric Graph Theory and Matrix Approach Model for Assessing the Surface Water Quality.
- Author
-
Baluch, M. A.
- Subjects
WATER quality ,GRAPH theory ,MATRICES (Mathematics) ,WATER supply ,WATER use - Abstract
In this paper a systematic parametric approach for assessing the water quality for given water resource by using the concepts of graph theory and matrix algebra is presented. A new, novel, generic and more sensitive water quality index (WQI) named as "Baluch" index is proposed that can assess and ranks the water quality for a given water resource. The water quality parameters listed in FAO-29 guidelines (belong to resource under investigation) and their relative importances are utilized to create a water quality assessment graph (WQG) and adjacency matrix. As a case study, the water quality of eighteen stations of upper basin of Indus River, Pakistan is assessed. Eight physicochemical quality parameters including pH, TDS, Total hardness, Ca Hardness, Mg hardness, SO4-2, Cl-1, and EC are used for constructing WQA. This WQA is then used to figure out "Baluch" index for each monitoring station, and it is found that "Baluch" index for Darband station has lowest value i.e. 0.85 and "Baluch" index highlight the situation that all other stations have relatively higher values of pH, which is concern able problem. Furthermore, this new index indicate the lowest quality water belongs to Jijal stations due relatively higher values of pH (i.e. 8.25) and Cl-ion, above average values of TDS, Hardness, SO42-ion concentrations. [ABSTRACT FROM AUTHOR]
- Published
- 2022
15. Lower Bounds of the Resolvent Estrada Indices for Line Graphs and Complementary Graphs.
- Author
-
Shuxiang Jia, Bo Deng, Chengfu Ye, and Weilin Liang
- Subjects
- *
SCHWARZ inequality , *REGULAR graphs , *GRAPH theory , *MACHINE translating , *INFORMATION processing , *LINEAR orderings - Published
- 2022
- Full Text
- View/download PDF
16. 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
17. Spectra of quaternion unit gain graphs.
- Author
-
Belardo, Francesco, Brunetti, Maurizio, Coble, Nolan J., Reff, Nathan, and Skogman, Howard
- Subjects
- *
QUATERNIONS , *GRAPH theory , *SPECTRAL theory , *LAPLACIAN matrices , *EIGENVALUES - Abstract
A quaternion unit gain graph is a graph where each orientation of an edge is given a quaternion unit, which is the inverse of the quaternion unit assigned to the opposite orientation. In this paper we define the adjacency, Laplacian and incidence matrices for a quaternion unit gain graph and study their properties. These properties generalize several fundamental results from spectral graph theory of ordinary graphs, signed graphs and complex unit gain graphs. Bounds for both the left and right eigenvalues of the adjacency and Laplacian matrix are developed, and the right eigenvalues for the cycle and path graphs are explicitly calculated. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
18. 异形截面立体编织的锭子轨道设计方法.
- Author
-
孙志宏, 方 涛, 王振喜, 邵国为, 徐 昌, and 王 兵
- Subjects
GRAPH theory - Abstract
Copyright of Journal of Donghua University (Natural Science Edition) is the property of Journal of Donghua University (Natural Science) Editorial Office and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 2022
- Full Text
- View/download PDF
19. Optimizing weighted gene co-expression network analysis with a multi-threaded calculation of the topological overlap matrix.
- Author
-
Shuai, Min, He, Dongmei, and Chen, Xin
- Subjects
- *
GENE regulatory networks , *BIG data , *MATRICES (Mathematics) , *SOURCE code - Abstract
Biomolecular networks are often assumed to be scale-free hierarchical networks. The weighted gene co-expression network analysis (WGCNA) treats gene co-expression networks as undirected scale-free hierarchical weighted networks. The WGCNA R software package uses an Adjacency Matrix to store a network, next calculates the topological overlap matrix (TOM), and then identifies the modules (sub-networks), where each module is assumed to be associated with a certain biological function. The most time-consuming step of WGCNA is to calculate TOM from the Adjacency Matrix in a single thread. In this paper, the single-threaded algorithm of the TOM has been changed into a multi-threaded algorithm (the parameters are the default values of WGCNA). In the multi-threaded algorithm, Rcpp was used to make R call a C++ function, and then C++ used OpenMP to start multiple threads to calculate TOM from the Adjacency Matrix. On shared-memory MultiProcessor systems, the calculation time decreases as the number of CPU cores increases. The algorithm of this paper can promote the application of WGCNA on large data sets, and help other research fields to identify sub-networks in undirected scale-free hierarchical weighted networks. The source codes and usage are available at https://github.com/do-somethings-haha/multi-threaded_calculate_unsigned_TOM_from_unsigned_or_signed_Adjacency_Matrix_of_WGCNA. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
20. 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
21. 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
22. A Greedy Technique Based Improved Approach to Solve Graph Colouring Problem.
- Author
-
Shukla, Ajay Narayan, Bharti, Vishal, and Garg, M. L.
- Subjects
GRAPH coloring ,GRAPH theory ,IMAGE processing ,IMAGING systems ,MATRICES (Mathematics) - Abstract
Graph colouring problem is a well-known NP-class optimization problem, studied due to a lot of applications in various real-world problems. Some of these applications are: register allocation, image processing and communication networks. There are various techniques suggested by the researchers to solve the problem which is either exact or approximate in nature. In this paper, a new greedy technique, based on degrees of vertices in the graph is presented to solve the graph colouring problem in an improved manner. The technique involves the use of adjacency matrix along with another matrix generated for the set of possible colours for each vertex in the graph. The generated colour matrix is used to assign the colours among the vertices in the graph based on decreasing degrees of the vertices. Several DIMACS colouring instances solved using the suggested approach in the article and compared with some contemporary techniques for the performance and proves compatible and having better execution time with compared technique. The obtained colouing results are mostly optimal colour values corresponding to the examined colouring instances of the graph. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
23. Alignment-Free Analyses of Nucleic Acid Sequences Using Graphical Representation (with Special Reference to Pandemic Bird Flu and Swine Flu)
- Author
-
Nandy, Ashesh, De, Antara, Roy, Proyasha, Dutta, Munna, Roy, Moumita, Sen, Dwaipayan, Basak, Subhash C., and Singh, Shailza, editor
- Published
- 2018
- Full Text
- View/download PDF
24. 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
25. Differentiation of alkyl radicals: A route through chemical graph theory.
- Author
-
Chatterjee, Subhojyoti, Liu, Fengyi, and Wang, Feng
- Subjects
- *
MOLECULAR graphs , *ALKYL radicals , *GRAPH theory , *RADICAL anions , *MOLECULAR connectivity index , *OCTANOIC acid , *CHEMICAL structure - Abstract
Alkyl radicals play important roles such as intermediary metabolism, cell damage/injury and death leading to potential mutations. The present investigation using chemical graph theory studied two sets of carboxyl radicals, that is, deprotonated (DPro, radical) and protonated (Pro, radical anion) forms of 5‐ethyl heptanoic acid and 5‐ethenyl hept‐6‐enoic acid (Set I) radicals and 6‐ethyl octanoic acid and 6‐ethenyl oct‐7‐enoic acid (Set II) radicals. The study reveals that the largest eigenvalue (LEV) spectra of the adjacency matrix have a unique value, where the spectra increase from DPro to Pro and from single to double bonded alkyl radical structures, thus forming a scoring function for molecular topological indices. This topological index is presented as a measure for molecular connectivity/branching, where the index is used to predict the refractivity of a series of carboxyl radicals. The statistical correlation coefficient obtained for quantitative structure–property relationship between chemical structure (alkyl radical) and its physical property (refractivity) through heat maps are excellent and ranges within 0.97–0.99. It is further discovered that the vector component of the LEV gives an insight to its structural details, where it captures the node with the highest degree along with the important weighted node, that holds the complete structure (i.e., the radical site), in case of the Pro radical structures. Node centrality, which captures the structural makeup, divides DPro radical T‐shaped structures into two subunits for the signal transduction of important biological process like oral toxicity. Size of the largest clusters is also studied, illustrating the parameter to be less sensitive for differentiating the CC double bonds in the Pro radicals. To our knowledge, this is the first study where pattern recognition has been exemplified through the lower‐diagonal‐upper decomposition matrix of the chemical graph that forms a fingerprint signature to differentiate the alkyl radicals. The present study innovatively digitalizes the chemical structures of alkyl radicals that enables the discovery of structure–property relationship reflected by their molecular branching through machine learning. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
26. The magnetic discrete Laplacian inferred from the Gauß–Bonnet operator and application.
- Author
-
Athmouni, Nassim, Baloudi, Hatem, Damak, Mondher, and Ennaceur, Marwa
- Subjects
- *
WEIGHTED graphs , *GRAPH theory , *SPECTRAL theory - Abstract
We consider the notion of χ -completeness of a locally finite graph and we extend this notion to the weighted magnetic graph. Moreover, we establish a link between the magnetic adjacency matrix on line graph and the magnetic discrete Laplacian on 1-forms. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
27. Spectral clustering of combinatorial fullerene isomers based on their facet graph structure.
- Author
-
Bille, Artur, Buchstaber, Victor, and Spodarev, Evgeny
- Subjects
- *
FULLERENES , *ISOMERS , *NOBEL Prize in Chemistry , *SPECTRAL theory , *STABILITY criterion , *GRAPH theory - Abstract
After Curl, Kroto and Smalley were awarded 1996 the Nobel Prize in chemistry, fullerenes have been subject of much research. One part of that research is the prediction of a fullerene's stability using topological descriptors. It was mainly done by considering the distribution of the twelve pentagonal facets on its surface, calculations mostly were performed on all isomers of C40, C60 and C80. This paper suggests a novel method for the classification of combinatorial fullerene isomers using spectral graph theory. The classification presupposes an invariant scheme for the facets based on the Schlegel diagram. The main idea is to find clusters of isomers by analyzing their graph structure of hexagonal facets only. We also show that our classification scheme can serve as a formal stability criterion, which became evident from a comparison of our results with recent quantum chemical calculations (Sure et al. in Phys Chem Chem Phys 19:14296–14305, 2017). We apply our method to classify all isomers of C60 and give an example of two different cospectral isomers of C44. Calculations are done with our own Python scripts available at (Bille et al. in Fullerene database and classification software, https://www.uni-ulm.de/mawi/mawi-stochastik/forschung/fullerene-database/, 2020). The only input for our algorithm is the vector of positions of pentagons in the facet spiral. These vectors and Schlegel diagrams are generated with the software package Fullerene (Schwerdtfeger et al. in J Comput Chem 34:1508–1526, 2013). [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
28. A topological approach of multiple correspondence analysis.
- Author
-
Abdesselam, Rafik
- Subjects
- *
CORRESPONDENCE analysis (Statistics) , *PROXIMITY matrices , *GRAPH theory , *RANK correlation (Statistics) , *MULTIDIMENSIONAL scaling - Abstract
Topological multiple correspondence analysis (TMCA) studies a group of categorical variables defined on the same set of individuals. It is a topological method of data analysis that consists of exploring, analyzing, and representing the associations between several qualitative variables in the context of multiple correspondence analysis (MCA). It compares and classifies proximity measures to select the best one according to the data under consideration, then analyzes, interprets, and visualizes with graphic representations, the possible associations between several categorical variables relating to the known problem of MCA. Based on the notion of neighborhood graphs, some of these proximity measures are more-or-less equivalent. A topological equivalence index between two measures is defined and statistically tested according to the degree of description of the associations between the modalities of these qualitative variables. We compare proximity measures and propose a topological criterion for choosing the best association measure, adapted to the data considered, from among some of the most widely used proximity measures for categorical data. The principle of the proposed approach is illustrated using a real dataset with conventional proximity measures for binary variables from the literature. The first step is to find the proximity measure that can best be adapted to the data; the second step is to use this measure to perform the TMCA. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
29. 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
30. A Poisson multi-Bernoulli mixture filter for tracking multiple resolvable group targets.
- Author
-
Zhou, Yusong, Zhao, Jin, Wu, Sunyong, and Liu, Chang
- Subjects
- *
FILTERS & filtration , *GRAPH theory , *MIXTURES , *FUNCTIONALS , *DYNAMIC models - Abstract
This paper presents a novel Poisson multi-Bernoulli mixture (PMBM) filter for tracking multiple resolvable group targets (MRGT) based on graph theory. Firstly, the number of groups and the relationships between members within the group are modelled by the adjacency matrix. Then, considering that a single dynamic evolution model is insufficient to guarantee stable tracking performance for group targets, the virtual leader-follower model (VLFM) is introduced to predict the evolution trend of unknown and potentially detected targets, respectively. Furthermore, we prove the conjugation of the proposed algorithm with the probability generating functionals (PGF) and give a detailed implementation of the Gaussian mixture (GM). Based on the coexistence scenario of splitting, merging and non-linear motion of the group targets, the simulation results show the effectiveness of the proposed algorithm in comparison with the existing methods. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
31. Palindromic Characteristic of Committed Graphs and Some Model Theoretic Properties.
- Author
-
Çevik, Ahmet
- Subjects
- *
GRAPH theory , *FORMAL languages , *PALINDROMES , *MODEL theory - Abstract
We bring into attention the interplay between model theory of committed graphs (1-regular graphs) and their palindromic characteristic in the domain of formal languages. We prove some model theoretic properties of committed graphs and then give a characterization of them in the formal language domain using palindromes. We show in the first part of the paper that the theory of committed graphs and the theory of infinite committed graphs differ in terms of completeness. We give the observation that theories of finite and infinite committed graphs are both decidable. The former is finitely axiomatizable, whereas the latter is not. We note that every committed graph is isomorphic to the structure of integers. In the second part, as our main focus of the paper and using some of the results in the first section, we give a characterization of committed graphs based on the notion of finite and infinite palindrome strings. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
32. The Discrete Laplacian Acting on 2-Forms and Application.
- Author
-
Baloudi, Hatem, Belgacem, Sayda, and Jeribi, Aref
- Subjects
- *
LAPLACIAN matrices , *GRAPH theory , *SPECTRAL theory , *ACTING - Abstract
In the current paper, we study the discrete Laplacian acting on 2-forms which was introduced and investigated by Chebbi (Potential Anal 49(2):331–358, 2018). We establish a new criterion of essential self-adjointness using the Nelson lemma. Moreover, we give an upper bound on the infimum of the essential spectrum. Furthermore, we establish a link between the adjacency matrix and the discrete Laplacian on 2-forms. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
33. A Unified Framework for Structured Graph Learning via Spectral Constraints.
- Author
-
Kumar, Sandeep, Jiaxi Ying, de M. Cardoso, Jose Vinícius, and Palomar, Daniel P.
- Subjects
- *
COMBINATORIAL optimization , *GRAPH theory , *REGULAR graphs , *SPECTRAL theory , *LAPLACIAN matrices , *NP-hard problems , *CONSTRAINT programming - Abstract
Graph learning from data is a canonical problem that has received substantial attention in the literature. Learning a structured graph is essential for interpretability and identification of the relationships among data. In general, learning a graph with a specific structure is an NP-hard combinatorial problem and thus designing a general tractable algorithm is challenging. Some useful structured graphs include connected, sparse, multi-component, bipartite, and regular graphs. In this paper, we introduce a unified framework for structured graph learning that combines Gaussian graphical model and spectral graph theory. We propose to convert combinatorial structural constraints into spectral constraints on graph matrices and develop an optimization framework based on block majorization-minimization to solve structured graph learning problem. The proposed algorithms are provably convergent and practically amenable for a number of graph based applications such as data clustering. Extensive numerical experiments with both synthetic and real data sets illustrate the effectiveness of the proposed algorithms. An open source R package containing the code for all the experiments is available at https://CRAN.R-project.org/package=spectralGraphTopology. [ABSTRACT FROM AUTHOR]
- Published
- 2020
34. 具有n-4个悬挂点的三圈图补图的最小特征值.
- Author
-
剧宏娟 and 雷英杰
- Subjects
GRAPH theory ,MAXIMA & minima ,MATRICES (Mathematics) - Abstract
Copyright of Journal of Hebei University of Science & Technology is the property of Hebei University of Science & Technology, Journal of Hebei University of Science & Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 2019
- Full Text
- View/download PDF
35. Graceful Labeling for Some Supercaterpillar Graphs Using Adjacency Matrix.
- Author
-
Pakpahan, R. N. and Sugeng, K. A.
- Subjects
- *
GRAPH theory , *GRAPH labelings , *MATHEMATICS problems & exercises , *INJECTIVE functions - 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. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
36. 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
37. The Energy of Conjugacy Class Graphs of Some Metabelian Groups.
- Author
-
Ahmad Fadzil, Amira Fadina, Sarmin, Nor Haniza, and Birkia, Rabiha Mahmoud
- Subjects
- *
FREE metabelian groups , *GRAPH theory , *ABELIAN groups , *FREE groups , *GRAPHIC methods - Abstract
The energy of a graph of a group G is the sum of all absolute values of the eigenvalues of the adjacency matrix. An adjacency matrix is a square matrix where the rows and columns consist of 0 or 1-entry depending on the adjacency of the vertices of the graph. A conjugacy class graph is a graph whose vertex set is the non-central conjugacy classes of the group. Two vertices are connected if their orders are not coprime. Meanwhile, a group G is said to be metabelian if there exists a normal subgroup H in G such that both H and the factor group G/H are abelian. In this research, the energy of the conjugacy class graphs for all nonabelian metabelian groups of order 24 are determined. The computations are assisted by Groups, Algorithm and Programming (GAP) and Maple2016 software. The results show that the energy of graphs of the groups in the study must be an even integer in the case that the energy is rational. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
38. On signed graphs with just two distinct Laplacian eigenvalues.
- Author
-
Hou, Yaoping, Tang, Zikai, and Wang, Dijian
- Subjects
- *
GRAPH theory , *LAPLACIAN matrices , *EIGENVALUES , *PATHS & cycles in graph theory , *GRAPH connectivity - Abstract
Abstract We investigate signed graph whose Laplacian matrix has just two distinct eigenvalues. All simple connected signed graphs with maximum degree at most 4 and just two distinct Laplacian eigenvalues are characterized in this paper. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
39. Uniquely pressable graphs: Characterization, enumeration, and recognition.
- Author
-
Cooper, Joshua and Whitlatch, Hays
- Subjects
- *
GRAPHIC methods , *GRAPH theory , *ALGORITHMS , *MATHEMATICAL models , *NUMERICAL analysis - Abstract
Abstract Motivated by the study of genomes evolving by reversals, we consider pseudograph transformations known as "pressing sequences". In particular, we address the question of when a graph has precisely one pressing sequence resulting in the empty graph, thus answering an question from Cooper and Davis (2015) [13]. We characterize such "uniquely pressable" graphs, count the number of them on a given number of vertices, and provide a polynomial-time recognition algorithm. We conclude with several open questions. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
40. On graphs with prescribed star complements.
- Author
-
Yuan, Xiying, Zhao, Qingqing, Liu, Lele, and Chen, Hongyan
- Subjects
- *
GRAPH theory , *MULTIPLICITY (Mathematics) , *LOCALIZATION (Mathematics) , *FRACTIONAL calculus , *TREE graphs - Abstract
Abstract Let μ be an eigenvalue of a simple graph G with multiplicity k ≥ 1. A star complement for μ in G is an induced subgraph of G of order n − k with no eigenvalue μ. In this paper, we study the maximal graphs with the star S m as a star complement for −2. The maximal graphs with S 3 , S 4 , S 13 and S 21 as a star complement for −2 are described. We also describe the regular graphs with K 2 , s (s ≥ 2) as a star complement for an eigenvalue μ. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
41. The spectra of a new join of graphs.
- Author
-
Paul, Somnath
- Subjects
- *
GRAPH theory , *GRAPHIC methods , *MATHEMATICAL models , *MATHEMATICAL analysis , *REPRESENTATIONS of graphs - Abstract
Let G 1 , G 2 and H be three graphs on disjoint sets of vertices and G 1 has m 1 edges. Let S (G 1 , H) be the graph obtained from G 1 and H in the following way: (1) Delete all the edges of G 1 and consider m 1 disjoint copies of H. (2) Join each vertex of the i th copy of H to the end vertices of the i th edge of G 1 . Let G 1 (∨ H) G 2 be the graph obtained from S (G 1 , H) by joining each vertex of G 1 with each vertex of G 2. In this paper, we determine the adjacency (respectively, Laplacian, signless Laplacian) spectrum of G 1 (∨ H) G 2 in terms of those of G 1 , G 2 and H. As an application, we construct infinite pairs of cospectral graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
42. Energy of a vertex.
- Author
-
Arizmendi, Octavio, Fernandez Hidalgo, Jorge, and Juarez-Romero, Oliver
- Subjects
- *
MATHEMATICAL equivalence , *CONTINUITY , *GRAPH theory , *GEOMETRIC vertices , *SPECTRAL geometry , *FINITE groups - Abstract
In this paper we develop the concept of energy of a vertex introduced in Arizmendi and Juarez-Romero (2018). We derive basic inequalities, continuity properties, give examples and extend the definition to locally finite graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
43. Spectral characterizations of anti-regular graphs.
- Author
-
Aguilar, Cesar O., Lee, Joon-yeob, Piato, Eric, and Schweitzer, Barbara J.
- Subjects
- *
REGULAR graphs , *CHEBYSHEV polynomials , *EIGENVALUES , *GRAPH theory , *MATRICES (Mathematics) , *ASYMPTOTIC distribution - Abstract
We study the eigenvalues of the unique connected anti-regular graph A n . Using Chebyshev polynomials of the second kind, we obtain a trigonometric equation whose roots are the eigenvalues and perform elementary analysis to obtain an almost complete characterization of the eigenvalues. In particular, we show that the interval Ω = [ − 1 − 2 2 , − 1 + 2 2 ] contains only the trivial eigenvalues λ = − 1 or λ = 0 , and any closed interval strictly larger than Ω will contain eigenvalues of A n for all n sufficiently large. We also obtain bounds for the maximum and minimum eigenvalues, and for all other eigenvalues we obtain interval bounds that improve as n increases. Moreover, our approach reveals a more complete picture of the bipartite character of the eigenvalues of A n , namely, as n increases the eigenvalues are (approximately) symmetric about the number − 1 2 . We also obtain an asymptotic distribution of the eigenvalues as n → ∞ . Finally, the relationship between the eigenvalues of A n and the eigenvalues of a general threshold graph is discussed. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
44. Numerical Range of Simple Graphs and Some Bounds for their Eigenvalues.
- Author
-
Tajarrod, M. and Sistani, T.
- Subjects
- *
CHARTS, diagrams, etc. , *MATRICES (Mathematics) , *APPROXIMATION algorithms , *EIGENVALUE equations , *SUBGRAPHS - Abstract
The numerical range of a simple graph G, named F(G), is the numerical range of its adjacency matrix A(G). The main purpose of this paper is to approximate F(G). Then, using this approximation, bounds for the largest and the smallest eigenvalues of G are proposed. In fact, lower bounds for the largest eigenvalues of G are presented in terms of disjoint induced subgraphs of G and the numerical range of the square of A(G). [ABSTRACT FROM AUTHOR]
- Published
- 2018
45. Various Domination Energies in Graphs.
- Author
-
Kolamban, Shajidmon and Kumar, M. Kamal
- Subjects
- *
MATHEMATICAL analysis , *GRAPH theory , *LAPLACIAN matrices , *GEOMETRIC vertices , *GRAPHIC methods - Abstract
Representing a subset of vertices in a graph by means of a matrix was introduced by E. Sampath Kumar. Let G(V, E) be a graph and S ⊆ V be a set of vertices. We can represent the set S by means of a matrix as follows, in the adjacency matrix A(G) of G replace the aii element by 1 if and only if, vi ∊ S. In this paper we study the set S being dominating set and corresponding domination energy of some class of graphs. [ABSTRACT FROM AUTHOR]
- Published
- 2018
46. 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
47. On the α-index of graphs with pendent paths.
- Author
-
Nikiforov, Vladimir and Rojo, Oscar
- Subjects
- *
GRAPH theory , *LINEAR algebra , *LAPLACIAN operator , *MATRICES (Mathematics) , *LAPLACIAN matrices - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For every real α ∈ [ 0 , 1 ] , write A α ( G ) for the matrix A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . This paper presents some extremal results about the spectral radius ρ α ( G ) of A α ( G ) that generalize previous results about ρ 0 ( G ) and ρ 1 / 2 ( G ) . In particular, write B p , q , r be the graph obtained from a complete graph K p by deleting an edge and attaching paths P q and P r to its ends. It is shown that if α ∈ [ 0 , 1 ) and G is a graph of order n and diameter at least k , then ρ α ( G ) ≤ ρ α ( B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ ) , with equality holding if and only if G = B n − k + 2 , ⌊ k / 2 ⌋ , ⌈ k / 2 ⌉ . This result generalizes results of Hansen and Stevanović [5] , and Liu and Lu [7] . [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
48. On the Aα-spectral radius of a graph.
- Author
-
Xue, Jie, Lin, Huiqiu, Liu, Shuting, and Shu, Jinlong
- Subjects
- *
GRAPH theory , *GRAPHIC methods , *MATRICES (Mathematics) , *COMPLEX matrices , *LINEAR algebra - Abstract
Let G be a graph with adjacency matrix A ( G ) and let D ( G ) be the diagonal matrix of the degrees of G . For any real α ∈ [ 0 , 1 ] , Nikiforov [3] defined the matrix A α ( G ) as A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) . The largest eigenvalue of A α ( G ) is called the A α -spectral radius of G . In this paper, we give three edge graft transformations on A α -spectral radius. As applications, we determine the unique graph with maximum A α -spectral radius among all connected graphs with diameter d , and determine the unique graph with minimum A α -spectral radius among all connected graphs with given clique number. In addition, some bounds on the A α -spectral radius are obtained. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
49. Frame graph.
- Author
-
Abdollahi, Farshid and Najafi, Hashem
- Subjects
- *
GRAPH theory , *HILBERT space , *GEOMETRIC vertices , *LAPLACIAN matrices , *MATHEMATICAL sequences - Abstract
Let
be a finite-dimensional Hilbert space and be a finite frame for . For , we associate a simple graph denoted by and called frame graph, with all elements of as vertices, and two distinct vertices are adjacent when the inner product of them is nonzero. The associated graph is called a tight frame graph if the mentioned frame is tight. In this paper, we study some basic properties of and investigate the relation between the frame-theoretic properties of and the graph-theoretic properties of . For example, it is shown that trees on more than two vertices and cycles on more than five vertices are not tight frame graphs while complete graphs, complete graphs minus a single edge and the join of each graph with itself are tight frame graphs. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF
50. On the Aα-characteristic polynomial of a graph.
- Author
-
Liu, Xiaogang and Liu, Shunyi
- Subjects
- *
POLYNOMIALS , *GRAPH theory , *GEOMETRIC vertices , *COEFFICIENTS (Statistics) - Abstract
Let G be a graph with n vertices, and let A ( G ) and D ( G ) denote respectively the adjacency matrix and the degree matrix of G . Define A α ( G ) = α D ( G ) + ( 1 − α ) A ( G ) for any real α ∈ [ 0 , 1 ] . The A α -characteristic polynomial of G is defined to be det ( x I n − A α ( G ) ) = ∑ j c α j ( G ) x n − j , where det ( ⁎ ) denotes the determinant of ⁎, and I n is the identity matrix of size n . The A α -spectrum of G consists of all roots of the A α -characteristic polynomial of G . A graph G is said to be determined by its A α -spectrum if all graphs having the same A α -spectrum as G are isomorphic to G . In this paper, we first formulate the first four coefficients c α 0 ( G ) , c α 1 ( G ) , c α 2 ( G ) and c α 3 ( G ) of the A α -characteristic polynomial of G . And then, we observe that A α -spectra are much efficient for us to distinguish graphs, by enumerating the A α -characteristic polynomials for all graphs on at most 10 vertices. To verify this observation, we characterize some graphs determined by their A α -spectra. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.