Search

The cyclomatic number of a graph G (is denoted by ν) is the minimum number of edges of G whose removal makes G as acyclic. Denote by Gn,ν the collection of all n-vertex connected graphs with cyclomatic number ν. The elements of Gn,ν with maximum second Zagreb (M2) index (for ν ≤ 4 and ν = k(k-3) 2+1, where 4 ≤ k ≤ n-2) and with minimum M2 index (for ν ≤ 2) have already been reported in the literature. The main contribution of the present article is the characterization of graphs in the collection Gn,ν with minimum M2 index for ν ≥ 3 and n ≥ 2(ν - 1). The obtained extremal graphs, are molecular graphs and thereby, also minimize M2 index among all the connected molecular n-vertex graphs with cyclomatic number ν ≥ 3, where n ≥ 2(ν-1). For n ≥ 6, the graph having maximum M2 value in the collection Gn,5 has also been characterized and thereby a conjecture posed by Xu et al. [MATCH Commun. Math. Comput. Chem. 72 (2014) 641-654] is confirmed for ν = 5. [ABSTRACT FROM AUTHOR]

Abstract In a network or a graph, the total communicability (TC) has been defined as the sum of the entries in the exponential of the adjacency matrix of the network. This quantity offers a good measure of how easily information spreads across the network, and can be useful in the design of networks having certain desirable properties. In this paper, we obtain some bounds for total communicability of a graph G , T C (G) , in terms of spectral radius of the adjacency matrix, number of vertices, number of edges, minimum degree and the maximum degree of G. Moreover, we find some upper bounds for T C (G) when G is the Cartesian product, tensor product or the strong product of two graphs. In addition, Nordhaus–Gaddum-type results for the total communicability of a graph G are established. [ABSTRACT FROM AUTHOR]

The degree distance DD(G) of a connected graph G was invented by Dobrynin and Kochetova in 1994. Recently, one of the present authors introduced the concept of k-center Steiner degree distance defined as... where dG(S) is the Steiner k-distance of S and degG(v) is the degree of the vertex v in G. In this paper, we investigate the Steiner degree distance of complete and Cartesian product graphs. [ABSTRACT FROM AUTHOR]

Abstract Let G = (V , E) be a graph with vertex set V and edge set E. The v e -degree of a vertex v ∈ V equals the number of edges v e -dominated by v and the e v -degree of an edge e ∈ E equals the number of vertices e v -dominated by e. Recently, Chellali et al. studied the properties of v e -degree and e v -degree of graphs (Chellali et al., 2017). Also they focused on the regularity and irregularity of these types of degrees and proposed several open problems. In this paper, we solve one of them and obtain some results on the regularity and irregularity of v e - and e v -degrees in graphs. [ABSTRACT FROM AUTHOR]

Abstract The atom-bond connectivity (A B C) index of a graph G = (V , E) is defined as A B C (G) = ∑ u v ∈ E (G) d u + d v − 2 d u d v , where d u , d v are the degrees of the vertices u and v in G , respectively. In this paper, we prove that among all n -vertex graphs with given chromatic number χ ≥ 3 , the Turán graph T n , χ is the unique graph having the maximum A B C index, which completely confirms a conjecture posed in Zhang et al. (2016). [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]

Let d ( u, v ) be the distance between u and v of graph G , and let W f ( G ) be the sum of f ( d ( u, v )) over all unordered pairs { u, v } of vertices of G , where f ( x ) is a function of x . In some literatures, W f ( G ) is also called the Q -index of G . In this paper, some unified properties to Q -indices are given, and the majorization theorem is illustrated to be a good tool to deal with the ordering problem of Q -index among trees with n vertices. With the application of our new results, we determine the four largest and three smallest (resp. four smallest and three largest) Q -indices of trees with n vertices for strictly decreasing (resp. increasing) nonnegative function f ( x ), and we also identify the twelve largest (resp. eighteen smallest) Harary indices of trees of order n  ≥ 22 (resp. n  ≥ 38) and the ten smallest hyper-Wiener indices of trees of order n  ≥ 18, which improve the corresponding main results of Xu (2012) and Liu and Liu (2010), respectively. Furthermore, we obtain some new relations involving Wiener index, hyper-Wiener index and Harary index, which gives partial answers to some problems raised in Xu (2012). [ABSTRACT FROM AUTHOR]

Let G=(V,E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the Laplacian matrix and the signless Laplacian matrix of G are L(G)=D(G)-A(G) and Q(G)=D(G)+A(G), respectively. Also denote by λ1(G), a(G), q1(G) and δ(G) the largest eigenvalue of A(G), the second smallest eigenvalue of L(G), the largest eigenvalue of Q(G) and the minimum degree of G, respectively. In this paper, we give partial proofs to the following two conjectures: (i)Aouchiche (Comparaison Automatisée d’Invariants en Théorie des Graphes, 2006) if G is a connected graph, then a(G)/δ(G) is minimum for graph composed of 2 triangles linked with a path. (ii)Aouchiche et al. (Linear Algebra Appl 432:2293-2322, 2010) and Cvetković et al. (Publ Inst Math Beogr 81(95):11-27, 2007) if G is a connected graph with n≥4 vertices, then q1(G)-2λ1(G)≤n-2n-1 with equality holding if and only if G≅K1,n-1. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V and edge set E. Let di be the degree of the vertex vi of G. The inverse degree, Randić index, and harmonic index of G are defined as ID =Σvi∈V 1/di, R =Σvivj∈E 1/√di dj, and H = Σvivj∈E 2/(di + dj), respectively. We obtain relations between ID and R as well as between ID and H. Moreover, we prove that in the case of trees, ID > R and ID > H. [ABSTRACT FROM AUTHOR]

Let G = ( V , E ) be a simple graph of order n . The normalized Laplacian eigenvalues of graph G are denoted by ρ 1 ( G ) ≥ ρ 2 ( G ) ≥ ⋯ ≥ ρ n − 1 ( G ) ≥ ρ n ( G ) = 0 . Also let G and G ′ be two nonisomorphic graphs on n vertices. Define the distance between the normalized Laplacian spectra of G and G ′ as σ N ( G , G ′ ) = ∑ i = 1 n | ρ i ( G ) − ρ i ( G ′ ) | p , p ≥ 1 . Define the cospectrality of G by c s N ( G ) = min ⁡ { σ N ( G , G ′ ) : G ′ not isomorphic to G } . Let c s n N = max ⁡ { c s N ( G ) : G a graph on n vertices } . In this paper, we give an upper bound on c s N ( G ) in terms of the graph parameters. Moreover, we obtain an exact value of c s n N . An upper bound on the distance between the normalized Laplacian spectra of two graphs has been presented in terms of Randić energy. As an application, we determine the class of graphs, which are lying closer to the complete bipartite graph than to the complete graph regarding the distance of normalized Laplacian spectra. [ABSTRACT FROM AUTHOR]

Letdenote the class ofc-cyclic graphs withnvertices, girthandpendant vertices. In this paper, we determine the unique extremal graph with largest signless Laplacian spectral radius and Laplacian spectral radius in the class of connectedc-cyclic graphs withvertices, girthgand at mostpendant vertices, respectively, and the unique extremal graph with largest signless Laplacian spectral radius ofwhenand, and we also identify the unique extremal graph with largest Laplacian spectral radius inin the caseand eitherandgis even orandgis odd. Our results extends the corresponding results of [Sci. Sin. Math. 2010;40:1017–1024, Electron. J. Combin. 2011; 18:p.183, Comput. Math. Appl. 2010;59:376–381, Electron. J. Linear Algebra. 2011;22:378–388 and J. Math. Res. Appl. 2014;34:379–391]. [ABSTRACT FROM AUTHOR]

A kite graph Ki n ,  ω is a graph obtained from a clique K ω and a path P n − ω by adding an edge between a vertex from the clique and an endpoint from the path. In this note, we prove that K i n , n − 1 is determined by its signless Laplacian spectrum when n ≠ 5 and n ≥ 4, and K i n , n − 1 is also determined by its distance spectrum when n ≥ 4. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n . For i = 1 , 2 , … , n , let d i be the degree of the vertex v i of G . The extended adjacency matrix A ex of G is defined so that its ( i, j )-entry is equal to 1 2 ( d i d j + d j d i ) if the vertices v i and v j are adjacent, and 0 otherwise,Yang et al. (1994). The spectral radius η 1 and the energy E e x of the A ex -matrix are examined. Lower and upper bounds on η 1 and E e x are obtained, and the respective extremal graphs characterized. [ABSTRACT FROM AUTHOR]

We study the Laplacian and the signless Laplacian energy of connected unicyclic graphs, obtaining a tight upper bound for this class of graphs. We also find the connected unicyclic graph on n vertices having largest (signless) Laplacian energy for 3 ≤ n ≤ 13 . For n ≥ 11 , we conjecture that the graph consisting of a triangle together with n − 3 balanced distributed pendent vertices is the candidate having the maximum (signless) Laplacian energy among connected unicyclic graphs on n vertices. We prove this conjecture for many classes of graphs, depending on σ , the number of (signless) Laplacian eigenvalues bigger than or equal to 2. [ABSTRACT FROM AUTHOR]

The classical first and second Zagreb indices of a graph G are defined as M 1 ( G ) = ∑ v ∈ V d G ( v ) 2 and M 2 ( G ) = ∑ u v ∈ E ( G ) d G ( u ) d G ( v ) , where d G ( v ) is the degree of the vertex v of graph G . Recently, Furtula et al. (2014) studied the difference between the Zagreb indices and mentioned a problem to characterize the graphs for which M 1 ( G ) > M 2 ( G ) or M 1 ( G ) < M 2 ( G ) or M 1 ( G ) = M 2 ( G ) . In this paper we completely solve this problem. [ABSTRACT FROM AUTHOR]

The Kirchhoff indexof a graphGis the sum of resistance distances between all unordered pairs of vertices, which was introduced by Klein and Randić. In this paper, we characterize all extremal graphs with respect to Kirchhoff index among all graphs obtained by deletingpedges from a complete graphwithand obtain a sharp upper bound on the Kirchhoff index of these graphs. In addition, all the graphs with the first to ninth maximal Kirchhoff indices are completely determined among all connected graphs of order. [ABSTRACT FROM PUBLISHER]

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

Let G = ( V , E ) be a connected graph with vertex set V ( G ) = { v 1 , v 2 , … , v n } and edge set E ( G ) . The transmission Tr ( v i ) of vertex v i is defined to be the sum of distances from v i to all other vertices. Let Tr ( G ) be the n × n diagonal matrix with its ( i , i ) -entry equal to Tr G ( v i ) . The distance signless Laplacian is defined as D Q ( G ) = Tr ( G ) + D ( G ) , where D ( G ) is the distance matrix of G . Let ∂ 1 ( G ) ≥ ∂ 2 ( G ) ≥ ⋯ ≥ ∂ n ( G ) denote the eigenvalues of distance signless Laplacian matrix of G . In this paper, we first characterize all graphs with ∂ n ( G ) = n − 2 . Secondly, we characterize all graphs with ∂ 2 ( G ) ∈ [ n − 2 , n ] when n ≥ 11 . Furthermore, we give the lower bound on ∂ 2 ( G ) with independence number α and the extremal graph is also characterized. [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 inverse degree of graph G is defined as I D ( G ) = ∑ v ∈ V ( G ) 1 d G ( v ) where d G ( v ) is the degree of vertex v in G . In this paper we have determined some upper and lower bounds on the inverse degree I D ( G ) for a connected graph G in terms of other graph parameters, such as chromatic number, clique number, connectivity, number of cut edges, matching number. Also the corresponding extremal graphs have been completely characterized. [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 connective eccentricity index (CEI) of a graph G is defined as ξ ce ( G ) = ∑ v i ∈ V ( G ) d ( v i ) ε ( v i ) where ε ( v i ) and d ( v i ) are the eccentricity and the degree of vertex v i , respectively, in G . In this paper we obtain some lower and upper bounds on the connective eccentricity index for all trees of order n and with matching number β and characterize the corresponding extremal trees. And the maximal graphs of order n and with matching number β and n edges have been determined which maximize the connective eccentricity index. Also the extremal graphs with maximal connective eccentricity index are completely characterized among all connected graphs of order n and with matching number β . Moreover we establish some relations between connective eccentricity index and eccentric connectivity index, as another eccentricity-based invariant, of graphs. [ABSTRACT FROM AUTHOR]

The article offers information on the molecular graph G with vertex set V (G) and edge set E(G). It mentions that the Zagreb index of G is related to the degree of vertex in G. It offers information on the multiplicative Zagreb coindex and second multiplicative Zagreb coindex.. It offers information on the Narumi-Katayama index of a graph G, denoted by NK(G).

For G being a graph with n vertices and m edges, and with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n − 1 ≥ μ n = 0 , the Laplacian energy is defined as L E = ∑ i = 1 n | μ i − 2 m / n | . Let σ be the largest positive integer such that μ σ ≥ 2 m / n . We characterize the graphs satisfying σ = n − 1 . Using this, we obtain lower bounds for LE in terms of n, m , and the first Zagreb index. In addition, we present some upper bounds for LE in terms of graph invariants such as n, m , maximum degree, vertex cover number, and spanning tree packing number. [ABSTRACT FROM AUTHOR]

For any real number α , let s α ( G ) denote the sum of the α th power of the non-zero Laplacian eigenvalues of a graph G . In this paper, we first obtain sharp bounds on the largest and the second smallest Laplacian eigenvalues of a graph, and a new spectral characterization of a graph from its Laplacian eigenvalues. Using these results, we then establish sharp bounds for s α ( G ) in terms of the number of vertices, number of edges, maximum vertex degree and minimum vertex degree of the graph G , from which a Nordhaus–Gaddum type result for s α is also deduced. Moreover, we characterize the graphs maximizing s α for α > 1 among all the connected graphs with given matching number. [ABSTRACT FROM AUTHOR]

Resistance distance was introduced by Klein and Randić as a generalisation of the classical distance. The Kirchhoff index Kf(G) of a graph G is the sum of resistance distances between all unordered pairs of vertices. In this article we characterise the extremal graphs with the maximal Kirchhoff index among all non-trivial quasi-tree graphs of order n. Moreover, we obtain a lower bound on the Kirchhoff index for all non-trivial quasi-tree graphs of order n. [ABSTRACT FROM AUTHOR]

Abstract The reciprocal degree distance (RDD), defined for a connected graph G as vertex-degree- weighted sum of the reciprocal distances, that is, R D D (G) = ∑ u ≠ v d G (u) + d G (v) d G (u , v) , where d G (u) is the degree of the vertex u in the graph G and d G (u , v) denotes the distance between two vertices u and v in the graph G. The reciprocal degree distance is a weight version of the Harary index, just as the degree distance is a weight version of the Wiener index. Finding sufficient conditions for graphs possessing certain properties is an important and meaningful problem. In this paper, we give sufficient conditions for a graph to be k -connected or β -deficient in terms of the reciprocal degree distance. [ABSTRACT FROM AUTHOR]

We investigate the graph with minimal Zeroth-order general Randić index in terms of its order n , pendent number N 1 and cyclomatic number γ ≥ 0. Extremal graphs were completely characterized for cases of γ = 0 , 1 , 2 , which can be directly extended for graphs with cyclomatic number γ ≥ 3. [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]

Abstract For a connected graph G , the general sum-connectivity index χ α (G) , general Platt index P l α (G) and second Zagreb index M 2 (G) are defined as χ α (G) = ∑ u v ∈ E (G) (d (u) + d (v)) α , P l α (G) = ∑ u v ∈ E (G) (d (u) + d (v) − 2) α and M 2 (G) = ∑ u v ∈ E (G) d (u) d (v) , where d (u) is the degree of vertex u. A k -polygonal cactus is a connected graph in which every edge lies on exactly one cycle of length k. In this paper, we shall determine the minimum value and maximum value for χ α (G) , P l α (G) and M 2 (G) , respectively, among the class of k -polygonal cacti with n cycles for k ≥ 3 , n ≥ 3 and α > 1. Furthermore, when α > 1 , we determine the unique extremal maximum k -polygonal cactus with n cycles for k ≥ 3 and n ≥ 3 , and we also identify the unique extremal minimum k -polygonal cactus with n cycles for 3 ≤ k ≤ 5 and n ≥ 3. [ABSTRACT FROM AUTHOR]

Let a ( k ) = ( a 1 , a 2 , … , a k ) be a sequence of positive integers. A butterfly-like graph W p ( s ) ; a ( k ) is a graph consisting of s ( ≥ 1 ) cycle of lengths p + 1 , and k ( ≥ 1 ) paths P a 1 + 1 , P a 2 + 1 , …, P a k + 1 intersecting in a single vertex. The girth of a graph G is the length of a shortest cycle in G . Two graphs are said to be A - cospectral if they have the same adjacency spectrum. For a graph G , if there does not exist another non-isomorphic graph H such that G and H share the same Laplacian (respectively, signless Laplacian) spectrum, then we say that G is L − D S (respectively, Q − D S ). In this paper, we firstly prove that no two non-isomorphic butterfly-like graphs with the same girth are A -cospectral, and then present a new upper and lower bounds for the i -th largest eigenvalue of L ( G ) and Q ( G ) , respectively. By applying these new results, we give a positive answer to an open problem in Wen et al. (2015) [17] by proving that all the butterfly-like graphs W 2 ( s ) ; a ( k ) are both Q − D S and L − D S . [ABSTRACT FROM AUTHOR]