Search

In this paper, we introduce the subset-strong product of graphs and give a method for calculating the adjacency spectrum of this product. In addition, exact expressions for the first and second Zagreb indices of the subset-strong products of two graphs are reported. Examples are provided to illustrate the applications of this product in some growing graphs and complex networks. [ABSTRACT FROM AUTHOR]

We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the g -Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs. [ABSTRACT FROM AUTHOR]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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 CC 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]

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]

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]

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]

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]

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]

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]

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.

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

A signed graph G σ consists of an underlying graph G and a sign function σ , which assigns each edge uv of G a sign σ ( u v ) , either positive or negative. The adjacency matrix of G σ is defined as A ( G σ ) = ( a u , v σ ) with a u , v σ = σ ( u v ) a u , v , where a u , v = 1 if u , v ∈ V ( G ) are adjacent, and a u , v = 0 otherwise. The positive inertia index of G σ , written as p ( G σ ) , is defined to be the number of positive eigenvalues of A ( G σ ) . Recently, Yu et al. (2016) [12] characterized the signed graphs G σ with pendant vertices such that p ( G σ ) = 2 . In this paper, we extend the above work to a more general case, characterizing the signed graphs G σ with cut points whose positive inertia index is 2. [ABSTRACT FROM AUTHOR]

In this paper we consider a graph G, a partition P = [V1, V2, ..., Vk} of V (G) and the generalized complements GkP and Gk(i)P with respect to the partition P. We derive conditions to be satisfied by P so that G commutes with its generalized complements. Apart from the general characterization, we also obtain conditions on P = [V1, V2, ...,Vk} so that G commutes with its generalized complements for certain classes of graphs namely complete graphs, cycles and generalized wheels. In the process we obtain a commuting decomposition of regular complete k-partite graph ... in terms of a Hamiltonian cycle and its k-complement. We also get a commuting decomposition of a complete k-partite graph ... in terms of a generalized wheel and its k-complement, where n1, n2, ..., nk satisfy some conditions. [ABSTRACT FROM AUTHOR]

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph. [ABSTRACT FROM AUTHOR]

Given a graph G with n vertices and m edges, the term energy of graph E(G) was introduced by Gutman in chemistry, due to its relevance to the total π ― electron energy of carbon compounds. In 1971 McClelland obtained both lower and upper bounds for π 8213; electron energy. An improved upper bound was obtained by Koolen-Moulton in 2001. The lower and upper bounds for E(G) obtained in this paper are better than McClelland and Koolen-Moulton bounds. Also we obtained an upper bound for graph energy in terms of n as E(G) ≤ n/2[ 1 + √ n-2/2]. [ABSTRACT FROM AUTHOR]

Let G [ F, V k , H v ] be the graph with k pockets, where F is a simple graph of order n  ≥ 1, V k = { v 1 , … , v k } is a subset of the vertex set of F and H v is a simple graph of order m  ≥ 2, v is a specified vertex of H v . Also let G [ F, E k , H uv ] be the graph with k edge-pockets, where F is a simple graph of order n  ≥ 2, E k = { e 1 , … , e k } is a subset of the edge set of F and H uv is a simple graph of order m  ≥ 3, uv is a specified edge of H uv such that H u v − u is isomorphic to H u v − v . In this paper, we obtain some results describing the signless Laplacian spectra of G [ F, V k , H v ] and G [ F, E k , H uv ] in terms of the signless Laplacian spectra of F, H v and F, H uv , respectively. In addition, we also give some results describing the adjacency spectrum of G [ F, V k , H v ] in terms of the adjacency spectra of F, H v . Finally, as many applications of these results, we construct infinitely many pairs of signless Laplacian (resp. adjacency) cospectral graphs. [ABSTRACT FROM AUTHOR]