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.     

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{}}$.     

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.     

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.     

Zagreb,Harary and hyper-Wiener indices of graphs with a given matching number

In this paper, we present sharp bounds for the Zagreb indices, Harary index and hyper-Wiener index of graphs with a given matching number, and we also completely determine the extremal graphs.     

On the minimum degree,edge-connectivity and connectivity of power graphs of finite groups

In this paper, the minimum degree of power graphs of certain cyclic groups, abelian p-groups, dihedral groups and dicyclic groups are obtained. It is ascertained that the edge-connectivity and minimum degree of power graphs are equal, and consequently, the minimum disconnecting sets of power graphs of the aforementioned groups are determined. In order to investigate the equality of connectivity and minimum degree of power graphs, certain necessary conditions for finite groups and a necessary and su?cient condition for finite cyclic groups are obtained. Moreover, the equality is discussed for the power graphs of abelian p-groups, dihedral groups and dicyclic groups.     

On the discrepancy between two Zagreb indices

We examine the quantity

$S\left(G\right)=\sum _{uv\in E\left(G\right)}min(degu,degv)$

over sets of graphs with a fixed number of edges. The main result shows the maximum possible value of $S\left(G\right)$ is achieved by three different classes of constructions, depending on the distance between the number of edges and the nearest triangular number. Furthermore we determine the maximum possible value when the set of graphs is restricted to be bipartite, a forest, or to be planar given sufficiently many edges. The quantity $S\left(G\right)$ corresponds to the difference between two well studied indices, the irregularity of a graph and the sum of the squares of the degrees in a graph. These are known as the first and third Zagreb indices in the area of mathematical chemistry.     

Complete catalogue of graphs of maximum degree 3 and defect at most 4

We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M_3,D, that is, (3,D,−?)-graphs for ?≤4.We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−?)-graphs with D≥2 and ?≤4. Our results also give an improvement to the upper bound on the largest possible number N_3,D of vertices in a graph of maximum degree 3 and diameter D, so that N_3,D≤M_3,D−6 for D≥5.     

The starlike trees with maximum and minimum second order connectivity index

Let G be a simple graph and h≥0 be an integer. The higher order connectivity index R _h (G) of G is defined as $$R_h(G)=\sum_{v_{i_1}v_{i_2}\cdots v_{i_{h+1}}} \frac{1}{\sqrt {d_{i_1}d_{i_2}\cdots d_{i_{h+1}}}},$$ where d _i denotes the degree of the vertex v _i and $v_{i_{1}}v_{i_{2}}\cdots v_{i_{h+1}}$ runs over all paths of length h in G. A starlike tree is a tree with unique vertex of degree greater than two. Rada and Araujo proved that the starlike trees which have equal connectivity index of order h for all h≥0 are isomorphic. By T(n) we denote the set of the starlike trees on n vertices. In this paper, we characterize the extremal starlike trees with maximum and minimum second order connectivity index in T(n).