Comparing the Zagreb indices for graphs with small difference between the maximum and minimum degrees

The first Zagreb index M₁(G) and the second Zagreb index M₂(G) of a (molecular) graph G are defined as M₁(G)=∑_u∈V(G)(d(u))² and M₂(G)=∑_uv∈E(G)d(u)d(v), where d(u) denotes the degree of a vertex u in G. The AutoGraphiX system [M. Aouchiche, J.M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, L. Hiesse, J. Lacheré, A. Monhait, Variable neighborhood search for extremal graphs. 14. The AutoGraphiX 2 system, in: L. Liberti, N. Maculan (Eds.), Global Optimization: From Theory to Implementation, Springer, 2005; G. Caporossi, P. Hansen, Variable neighborhood search for extremal graphs: 1 The AutoGraphiX system, Discrete Math. 212 (2000) 29-44; G. Caporossi, P. Hansen, Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures, Discrete Math. 276 (2004) 81-94] conjectured that M₁/n≤M₂/m (where n=|V(G)| and m=|E(G)|) for simple connected graphs. Hansen and Vuki?evi? [P. Hansen, D. Vuki?evi?, Comparing the Zagreb indices, Croat. Chem. Acta 80 (2007) 165-168] proved that it is true for chemical graphs and it does not hold for all graphs. Vuki?evi? and Graovac [D. Vuki?evi?, A. Graovac, Comparing Zagreb M₁ and M₂ indices for acyclic molecules, MATCH Commun. Math. Comput. Chem. 57 (2007) 587-590] proved that it is also true for trees. In this paper, we show that M₁/n≤M₂/m holds for graphs with Δ(G)−δ(G)≤2 and characterize the extremal graphs, the proof of which implies the result in [P. Hansen, D. Vuki?evi?, Comparing the Zagreb indices, Croat. Chem. Acta 80 (2007) 165-168]. We also obtain the result that M₁/n≤M₂/m holds for graphs with Δ(G)−δ(G)≤3 and δ(G)≠2.     

Zagreb indices of graphs

The first Zagreb index M₁(G) is equal to the sum of squares of the degrees of the vertices, and the second Zagreb index M₂(G) is equal to the sum of the products of the degrees of pairs of adjacent vertices of the underlying molecular graph G. In this paper, we obtain lower and upper bounds on the first Zagreb index M₁(G) of G in terms of the number of vertices (n), number of edges (m), maximum vertex degree (Δ), and minimum vertex degree (δ). Using this result, we find lower and upper bounds on M₂(G). Also, we present lower and upper bounds on M₂(G) +M₂(G) in terms of n, m, Δ, and δ, where G denotes the complement of G. Moreover, we determine the bounds on first Zagreb coindex M₁(G) and second Zagreb coindex M₂(G). Finally, we give a relation between the first Zagreb index and the second Zagreb index of graph G.     

On the Zagreb indices of the line graphs of the subdivision graphs

The aim of this paper is to investigate the Zagreb indices of the line graphs of the tadpole graphs, wheel graphs and ladder graphs using the subdivision concepts.     

On graphs with equal edge connectivity and minimum degree

The note contains some conditions on a graph implying that the edge connectivity is equal to the minimum degree. One of these conditions is that if d₁?d₂???d_n is the degree sequence then ∑^l_l?1(d₁+d_n?1)>In?1 for $\text{1 ? l? min {}\text{n}\text{2?1}\text{, d}{}_{\mathrm{n}}\text{}}$.     

On the maximal eccentric connectivity indices of graphs

For a connected simple graph G, the eccentricity ec(v) of a vertex v in G is the distance from v to a vertex farthest from v, and d(v) denotes the degree of a vertex v. The eccentric connectivity index of G, denoted by ξc(G), is defined as v∈V(G)d(v)ec(v). In this paper, we will determine the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(n ≤ m ≤ n + 4), and propose a conjecture on the graphs with maximal eccentric connectivity index among the connected graphs with n vertices and m edges(m ≥ n + 5).     

All hypoenergetic graphs with maximum degree at most 3

The energy E(G) of a graph G is defined as the sum of the absolute values of its eigenvalues. A connected graph G of order n is said to be hypoenergetic if E(G)<n. All connected hypoenergetic graphs with maximum degree Δ3 have been characterized. In addition to the four (earlier known) hypoenergetic trees, we now show that complete bipartite graph K_2,3 is the only hypoenergetic cycle-containing hypoenergetic graph. By this, the validity of a conjecture by Majstorović et al. has been confirmed.     

Realizability of p-point graphs with prescribed minimum degree,maximum degree,and line connectivity

It is well known that certain graph-theoretic extremal questions play a central role in the study of communication network vulnerability. Herein we consider a generalization of some of the classical results in this area. We define a (p, Δ, δ, λ) graph as a graph having p points, maximum degree Δ, minimum degree Δ, and line connectivity λ. An arbitrary quadruple of integers (a, b, c, d) is called (p, Δ, δ, λ) realizable if there is a (p, Δ, δ, λ) graph with p = a, Δ = b, Δ = c, and λ = d. Necessary and sufficient conditions for a quadruple to be (p, Δ, δ, λ) realizable are derived.     

Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k

A graph G is (k,0)‐colorable if its vertices can be partitioned into subsets V₁ and V₂ such that in G[V₁] every vertex has degree at most k, while G[V₂] is edgeless. For every integer k?0, we prove that every graph with the maximum average degree smaller than (3k+4)/(k+2) is (k,0)‐colorable. In particular, it follows that every planar graph with girth at least 7 is (8, 0)‐colorable. On the other hand, we construct planar graphs with girth 6 that are not (k,0)‐colorable for arbitrarily large k. © 2009 Wiley Periodicals, Inc. J Graph Theory 65:83–93, 2010     

Maximal and maximum independent sets in graphs with at most r cycles

Let m(G) denote the number of maximal independent sets of vertices in a graph G and let c(n,r) be the maximum value of m(G) over all connected graphs with n vertices and at most r cycles. A theorem of Griggs, Grinstead, and Guichard gives a formula for c(n,r) when r is large relative to n, while a theorem of Goh, Koh, Sagan, and Vatter does the same when r is small relative to n. We complete the determination of c(n,r) for all n and r and characterize the extremal graphs. Problems for maximum independent sets are also completely resolved. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 283–314, 2006     

Maximum Zagreb index, minimum hyper-Wiener index and graph connectivity

In this work we show that among all n-vertex graphs with edge or vertex connectivity k, the graph G=K_k(K₁+K_n−k−1), the join of K_k, the complete graph on k vertices, with the disjoint union of K₁ and K_n−k−1, is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique n-vertex graph with edge or vertex connectivity k whose hyper-Wiener index is minimum.     

On (Kq,k) vertex stable graphs with minimum size

A graph $G$ is a $(K_q,k)$ vertex stable graph if it contains a $K_q$ after deleting any subset of $k$ vertices. We give a characterization of $(K_q,k)$ vertex stable graphs with minimum size for $q=3,4,5$.     

Partition of graphs with condition on the connectivity and minimum degree

C. Thomassen and M. Szegedy proved the existence of a functionf(s, t) such that the points of anyf(s, t)-connected graph have a decomposition into two non-empty sets such that the subgraphs induced by them ares-connected andt-connected, respectively. We prove, thatf(s, t) ≦ 4s+4t − 13 and examine a similar problem for the minimum degree.