Search

Let , and be, respectively, the distance matrix, the distance Laplacian matrix and the distance signless Laplacian matrix of graph G, where denotes the diagonal matrix of the vertex transmissions in G. The eigenvalues of and will be denoted by and , respectively. In this paper, we study the properties of the distance Laplacian eigenvalues and the distance signless Laplacian eigenvalues of graph G. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph of order n with m edges. Denote by D ( G ) the diagonal matrix of its vertex degrees and by A ( G ) its adjacency matrix. Then the Laplacian matrix of graph G is L ( G ) = D ( G ) − A ( G ) . Among all eigenvalues of the Laplacian matrix L ( G ) of graph G , the most studied is the second smallest, called the algebraic connectivity a ( G ) of a graph. Let d ‾ ( G ) and δ ( G ) be the average degree and the minimum degree of graph G , respectively. In this paper we characterize all graphs for which ( i ) a ( G ) = 1 with δ ( G ) ≥ ⌈ n − 1 2 ⌉ , and ( i i ) a ( G ) = 2 with δ ( G ) ≥ n 2 . In [1] , Aouchiche mentioned a conjecture involving the algebraic connectivity a ( G ) and the average degree d ‾ ( G ) of graph G : a ( G ) − d ‾ ( G ) ≥ 4 − n − 4 n with equality holding if and only if G ‾ ≅ K 1 , n − 2 ∪ K 1 ( K 1 , n − 2 is a star of order n − 1 and G ‾ is the complement of graph G ). Here we prove this conjecture. [ABSTRACT FROM AUTHOR]

The k-th power of a graph G, denoted by [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n with m edges and diameter d . The Wiener index W ( G ) and the multiplicative Wiener index π ( G ) of the graph G are equal, respectively, to the sum and product of the distances between all pairs of vertices of G . We obtain a lower bound for the difference π ( G ) − W ( G ) of bipartite graphs. From it, we prove that π ( G ) > W ( G ) holds for all connected bipartite graphs, except P 2 , P 3 , and C 4 . We also establish sufficient conditions for the validity of π ( G ) > W ( G ) in the general case. Finally, a relation between W ( G ) , π ( G ) , n , m , and d is obtained. [ABSTRACT FROM AUTHOR]

The Wiener polarity index W p ( G ) of a graph G is the number of unordered pairs of vertices { u ,  v } in G such that the distance between u and v is equal to 3. Very recently, Zhang and Hu studied the Wiener polarity index in [Y. Zhang, Y. Hu, 2016] [38]. In this short paper, we establish an upper bound on the Wiener polarity index in terms of Hosoya index and characterize the corresponding extremal graphs. Moreover, we obtain Nordhaus–Gaddum-type results for W p ( G ). Our lower bound on W p ( G ) + W p ( G ¯ ) is always better than the previous lower bound given by Zhang and Hu. [ABSTRACT FROM AUTHOR]

The Graovac–Ghorbani index ( ABC GG ), was introduced by Graovac and Ghorbani, (2010). In this paper we present some upper and lower bounds on the ABC GG index and characterize the extremal graphs. [ABSTRACT FROM AUTHOR]

The distance signless Laplacian spectral radius of a connected graph G is the largest eigenvalue of the distance signless Laplacian matrix of G , defined as D Q ( G ) = T r ( G ) + D ( G ) , where D ( G ) is the distance matrix of G and T r ( G ) is the diagonal matrix of vertex transmissions of G . In this paper we determine upper and lower bounds on the minimal and maximal entries of the principal eigenvector of D Q ( G ) and characterize the extremal graphs. In addition, we obtain a lower bound on the distance signless Laplacian spectral radius of G based on its order and independence number, and characterize the extremal graph. [ABSTRACT FROM AUTHOR]

Let S z ( G ) and ξ c ( G ) be the Szeged index and the eccentric connectivity index of a graph G , respectively. In this paper we obtain a lower bound on S z ( T ) − ξ c ( T ) by double counting on some matrix and characterize the extremal graphs. From this result we compare the Szeged index and the eccentricity connectivity index of trees. For bipartite graphs we also compare the Szeged index and the eccentricity connectivity index. Moreover, we show that S z ( G ) − ξ c ( G ) ≥ − 4 for bipartite graphs and this result is not true in the general case. Finally, we classify the bipartite graphs G in which S z ( G ) − ξ c ( G ) ∈ { − 4 , − 3 , − 2 , − 1 , 0 , 1 , 2 } . [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with vertex set V = { v 1 , v 2 , … , v n } . Also let μ 1 ( G ) ≥ μ 2 ( G ) ≥ ⋯ ≥ μ n − 1 ( G ) ≥ μ n ( G ) = 0 and q 1 ( G ) ≥ q 2 ( G ) ≥ ⋯ ≥ q n ( G ) ≥ 0 be the Laplacian eigenvalues and signless Laplacian eigenvalues of G , respectively. In this paper we obtain μ i ( G ) ≤ i − 1 + min U i ⁡ max ⁡ { | N H ( v k ) ∪ N H ( v j ) | : v k v j ∈ E ( H ) } , where N H ( v k ) is the set of neighbors of vertex v k in V ( H ) = V ( G ) \ U i , U i is any ( i − 1 ) -subset of V ( G ) (here, we agree that i ∈ { 1 , … , n − 1 } and μ i ( G ) ≤ i − 1 if E ( H ) = ∅ ). For any graph G , this bound does not exceed the order of G . Moreover, we prove that max ⁡ { μ i ( G ) , q i ( G ) } ≤ max i ≤ k ≤ n ⁡ { d G ( v k ) + ∑ v j ∈ N G ( v k ) ∩ N d G ( v j ) d G ( v k ) } ≤ 2 d G ( v i ) , where d G ( v i ) is the i -th largest degree of G and N = { v i , v i + 1 , … , v n } . [ABSTRACT FROM AUTHOR]

Abstract: Molecular descriptors play an important role in mathematical chemistry, especially in the QSPR and QSAR modeling. Among them, a special place is reserved for the so called topological indices. Nowadays, there exists a legion of topological indices that found applications in various areas of chemistry Todeschini and Consonni (2000, 2009). Recently, we carried out comparison between several topological indices for various classes of graphs and trees (Das et al., 2012; Das and Trinajsti, 2010, 2011, 2012; Horoldagva and Das, 2012; Hua and Das, 2013). In this report, we compare the Wiener index and the Zagreb indices and the eccentric connectivity index for trees. [Copyright &y& Elsevier]

Abstract: The remoteness of a connected graph is the maximum, over all vertices, of the average distance from a vertex to all others, while the proximity of a connected graph is the minimum, over all vertices, of the average distance from a vertex to all others. In this paper, we first deal with some conjectures on remoteness and proximity, among which two conjectures were proved, while the other two conjectures were disproved by counter examples. Then we obtain some new upper bounds for remoteness and proximity in terms of some graph invariants. Moreover, we use remoteness to give a new sufficient condition for a connected bipartite graph to be Hamiltonian. [Copyright &y& Elsevier]

Abstract: In Das et al. (2013) [8], a new graph on monogenic semigroups (with zero) having elements has been recently defined. The vertices are the non-zero elements and, for , any two distinct vertices and are adjacent if in . As a continuing study, in Akgunes et al. (2014) [3], it has been investigated some well known indices (first Zagreb index, second Zagreb index, Randić index, geometric–arithmetic index, atom-bond connectivity index, Wiener index, Harary index, first and second Zagreb eccentricity indices, eccentric connectivity index, the degree distance) over . In the light of above references, our main aim in this paper is to extend these studies over to the tensor product. In detail, we will investigate the diameter, radius, girth, maximum and minimum degree, chromatic number, clique number and domination number for the tensor product of any two (not necessarily different) graphs and . [Copyright &y& Elsevier]

Abstract: Let be a simple connected graph with vertex set and edge set . The first Zagreb index and the second Zagreb index are defined as follows: and where is the degree of vertex in . The eccentric connectivity index of a graph , denoted by , is defined as where is the eccentricity of in . Recently, Das and Trinajstić (2011) [11] compared the eccentric connectivity index and Zagreb indices for chemical trees and molecular graphs. However, the comparison between the eccentric connectivity index and Zagreb indices, in the case of general trees and general graphs, is very hard and remains unsolved till now. In this paper, we compare the eccentric connectivity index and Zagreb indices for some graph families. We first give some sufficient conditions for a graph satisfying , . Then we introduce two classes of composite graphs, each of which has larger eccentric connectivity index than the first Zagreb index, if the original graph has larger eccentric connectivity index than the first Zagreb index. As a consequence, we can construct infinite classes of graphs having larger eccentric connectivity index than the first Zagreb index. [Copyright &y& Elsevier]

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. In this paper, we determined the extremal (maximal and minimal) unicyclic and bicyclic graphs with respect to Harary index. [ABSTRACT FROM AUTHOR]

Abstract: Let be a simple graph with vertex set and edge set . The Laplacian matrix of G is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity of a graph [18]. In this paper we give a lower bound on the algebraic connectivity of graphs. Moreover, we mention two conjectures, obtained by the system AutoGraphiX, about the algebraic connectivity , diameter and the minimum degree of graphs (see, [2], available online at http://www.gerad.ca/∼agx/):with equality if and only if G is isomorphic to a graph with and , and (ii) is minimum for a graph composed of 2 cliques on vertices with a common vertex if n is odd, and linked by an edge if n is even. Here we prove conjecture in (i) using the lower bound on the algebraic connectivity of graphs and conjecture in (ii), respectively. [Copyright &y& Elsevier]

Abstract: The power of a graph , denoted by , is the graph with the same vertex set as , such that two vertices are adjacent in if and only if their distance is at most in . In this paper, we give bounds on the first two largest Laplacian eigenvalues of the second power of a general graph, and on the second power of a tree. We also give a Nordhaus–Gaddum-type inequality for the Laplacian spectral radius of . [Copyright &y& Elsevier]

Abstract: Let be a simple graph of order with triangle(s). Also let be the eigenvalues of the adjacency matrix of graph . X. Yong [X. Yong, On the distribution of eigenvalues of a simple undirected graph, Linear Algebra Appl. 295 (1999) 73–80] conjectured that (i) is complete if and only if and also (ii) is complete if and only if . Here we disprove this conjecture by a counter example. Wang et al. [J.F. Wang, F. Belardo, Q.X. Huang, B. Borovićanin, On the two largest Q-eigenvalues of graphs, Discrete Math. 310 (2010) 2858–2866] conjectured that friendship graph is determined by its adjacency spectrum. Here we prove this conjecture. The eccentricity of a vertex is the maximum distance from it to another vertex and the average eccentricity of a graph is the mean value of eccentricities of all vertices of . Moreover, we mention three conjectures, obtained by the system AutoGraphiX, about the average eccentricity , girth and the spectral radius of graphs (see Aouchiche (2006) [1], available online at http://www.gerad.ca/~agx/). We give a proof of one conjecture and disprove two conjectures by counter examples. [Copyright &y& Elsevier]

Abstract: Let be a simple, connected and undirected graph with vertex set and edge set . Also let be the distance matrix of a graph (Janežič et al., 2007) . Here we obtain Nordhaus–Gaddum-type result for the spectral radius of distance matrix of a graph. A sharp upper bound on the maximal entry in the principal eigenvector of an adjacency matrix and signless Laplacian matrix of a simple, connected and undirected graph are investigated in Das (2009)  and Papendieck and Recht (2000) . Generally, an upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries and without zero diagonal entries are investigated in Zhao and Hong (2002)  and Das (2009) , respectively. In this paper, we obtain an upper bound on minimal entry in the principal eigenvector for the distance matrix of a graph and characterize extremal graphs. Moreover, we present the lower and upper bounds on maximal entry in the principal eigenvector for the distance matrix of a graph and characterize extremal graphs. [Copyright &y& Elsevier]

Abstract: The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. For a connected graph and two nonadjacent vertices and in of , recall that is the supergraph formed from by adding an edge between vertices and . Denote the Harary index of and by and , respectively. We obtain lower and upper bounds on , and characterize the equality cases in those bounds. Finally, in this paper, we present some lower and upper bounds on the Harary index of graphs with different parameters, such as clique number and chromatic number, and characterize the extremal graphs at which the lower or upper bounds on the Harary index are attained. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The adjacency matrix of a graph is denoted by and defined as the matrix , where for and 0 otherwise. The largest eigenvalue () of is called the spectral radius or the index of . The Laplacian matrix of is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity () of a graph [12]. In [1,2], Aouchiche et al. have given a series of conjectures on index () and algebraic connectivity () of (see also [3]). Here we prove two conjectures and disprove one by a counter example. [Copyright &y& Elsevier]

For a connected graph G , the eccentric connectivity index (ECI) and connective eccentricity index (CEI) of G are, respectively, defined as ξ c ( G ) = ∑ v i ∈ V ( G ) deg G ( v i ) ε G ( v i ) , ξ c e ( G ) = ∑ v i ∈ V ( G ) deg G ( v i ) ε G ( v i ) where deg G ( v i ) is the degree of v i in G and ε G ( v i ) denotes the eccentricity of vertex v i in G . In this paper we study on the difference of ECI and CEI of graphs G , denoted by ξ D ( G ) = ξ c ( G ) − ξ c e ( G ) . We determine the upper and lower bounds on ξ D ( T ) and the corresponding extremal trees among all trees of order n . Moreover, the extremal trees with respect to ξ D are completely characterized among all trees with given diameter d . And we also characterize some extremal general graphs with respect to ξ D . Finally we propose that some comparative relations between CEI and ECI are proposed on general graphs with given number of pendant vertices. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n ≥ 3 . The remoteness ρ = ρ ( G ) is the maximum, over all vertices, of the average distance from a vertex to all others. The radius r = r ( G ) is the minimum, over all vertices, of the eccentricity of a vertex. Aouchiche and Hansen (2011) conjectured that ρ − r ≥ 3 − n 4 if n is odd and ρ − r ≥ 2 n − n 2 4 ( n − 1 ) if n is even. In this paper, we confirm this conjecture. In addition, we completely characterize extremal graphs attaining the lower bound. [ABSTRACT FROM AUTHOR]