Binary trees with the largest number of subtrees

This paper characterizes binary trees with n leaves, which have the greatest number of subtrees. These binary trees coincide with those which were shown by Fischermann et al. [Wiener index versus maximum degree in trees, Discrete Appl. Math. 122(1-3) (2002) 127-137] and Jelen and Triesch [Superdominance order and distance of trees with bounded maximum degree, Discrete Appl. Math. 125 (2-3) (2003) 225-233] to minimize the Wiener index.     

A Class of Trees and its Wiener Index

In this paper, we will consider the Wiener index for a class of trees that is connected to partitions of integers. Our main theorem is the fact that every integer is the Wiener index of a member of this class. As a consequence, this proves a conjecture of Lepović and Gutman. The paper also contains extremal and average results on the Wiener index of the studied class.This work was supported by Austrian Science Fund project no. S-8307-MAT.     

Laplacian coefficients of trees with given number of leaves or vertices of degree two

Let G be a simple undirected n-vertex graph with the characteristic polynomial of its Laplacian matrix . It is well known that for trees the Laplacian coefficient c_n-2 is equal to the Wiener index of G, while c_n-3 is equal to the modified hyper-Wiener index of graph. Using a result of Zhou and Gutman on the relation between the Laplacian coefficients and the matching numbers in subdivided bipartite graphs, we characterize the trees with k leaves (pendent vertices) which simultaneously minimize all Laplacian coefficients. In particular, this extremal balanced starlike tree S(n,k) minimizes the Wiener index, the modified hyper-Wiener index and recently introduced Laplacian-like energy. We prove that graph S(n,n-1-p) has minimal Laplacian coefficients among n-vertex trees with p vertices of degree two. In conclusion, we illustrate on examples of these spectrum-based invariants that the opposite problem of simultaneously maximizing all Laplacian coefficients has no solution, and pose a conjecture on extremal unicyclic graphs with k leaves.     

On bipartite graphs with minimal energy

The energy of a graph is the sum of the absolute values of the eigenvalues of the graph. In a paper [G. Caporossi, D. Cvetkovi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs. 2. Finding graphs with external energy, J. Chem. Inf. Comput. Sci. 39 (1999) 984-996] Caporossi et al. conjectured that among all connected graphs G with n≥6 vertices and n−1≤m≤2(n−2) edges, the graphs with minimum energy are the star S_n with m−n+1 additional edges all connected to the same vertices for m≤n+⌊(n−7)/2⌋, and the bipartite graph with two vertices on one side, one of which is connected to all vertices on the other side, otherwise. The conjecture is proved to be true for m=n−1,2(n−2) in the same paper by Caporossi et al. themselves, and for m=n by Hou in [Y. Hou, Unicyclic graphs with minimal energy, J. Math. Chem. 29 (2001) 163-168]. In this paper, we give a complete solution for the second part of the conjecture on bipartite graphs. Moreover, we determine the graph with the second-minimal energy in all connected bipartite graphs with n vertices and edges.     

Equiseparability on terminal Wiener index

The aim of this work is to explore the properties of the terminal Wiener index, which was recently proposed by Gutman et al. (2004) [3], and to show the fact that there exist pairs of trees and chemical trees which cannot be distinguished by using it. We give some general methods for constructing equiseparable pairs and compare the methods with the case for the Wiener index. More specifically, we show that the terminal Wiener index is degenerate to some extent.     

Extremal Graphs with Respect to Matching Energy for Random Six-membered Ring Spiro Chains

Acta Mathematicae Applicatae Sinica, English Series - Gutman and Wagner (in the matching energy of a graph, Disc. Appl. Math., 2012) defined the matching energy of a graph and pointed out that its...     

New results on the energy of integral circulant graphs

Circulant graphs are an important class of interconnection networks in parallel and distributed computing. Integral circulant graphs play an important role in modeling quantum spin networks supporting the perfect state transfer as well. The integral circulant graph ICG_n(D) has the vertex set Z_n = {0, 1, 2, … , n − 1} and vertices a and b are adjacent if gcd(a − b, n) ∈ D, where D ⊆ {d : d∣n, 1 ? d < n}. These graphs are highly symmetric, have integral spectra and some remarkable properties connecting chemical graph theory and number theory. The energy of a graph was first defined by Gutman, as the sum of the absolute values of the eigenvalues of the adjacency matrix. Recently, there was a vast research for the pairs and families of non-cospectral graphs having equal energies. Following Bapat and Pati [R.B. Bapat, S. Pati, Energy of a graph is never an odd integer, Bull. Kerala Math. Assoc. 1 (2004) 129-132], we characterize the energy of integral circulant graph modulo 4. Furthermore, we establish some general closed form expressions for the energy of integral circulant graphs and generalize some results from Ili? [A. Ili?, The energy of unitary Cayley graphs, Linear Algebra Appl. 431 (2009), 1881-1889]. We close the paper by proposing some open problems and characterizing extremal graphs with minimal energy among integral circulant graphs with n vertices, provided n is even.     

Ordering of trees with fixed matching number by the Laplacian coefficients

Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix L(G), . Aleksandar Ili? [A. Ili?, Trees with minimal Laplacian coefficients, Comput. Math. Appl. 59 (2010) 2776-2783] identified n-vertex trees with given matching number q which simultaneously minimize all Laplacian coefficients. In this paper, we give another proof of this result. Generalizing the approach in the above paper, we determine n-vertex trees with given matching number q which have the second minimal Laplacian coefficients. We also identify the n-vertex trees with a perfect matching having the largest and the second largest Laplacian coefficients, respectively. Extremal values on some indices, such as Wiener index, modified hyper-Wiener index, Laplacian-like energy, incidence energy, of n-vertex trees with matching number q are obtained in this paper.     

Tricyclic graphs with maximum Merrifield-Simmons index

It is well known that the graph invariant, ‘the Merrifield-Simmons index’ is important one in structural chemistry. The connected acyclic graphs with maximal and minimal Merrifield-Simmons indices are determined by Prodinger and Tichy [H. Prodinger, R.F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart. 20 (1982) 16-21]. The sharp upper and lower bounds for the Merrifield-Simmons indices of unicyclic graphs are characterized by Pedersen and Vestergaard [A.S. Pedersen, P.D. Vestergaard, The number of independent sets in unicyclic graphs, Discrete Appl. Math. 152 (2005) 246-256]. The sharp upper bound for the Merrifield-Simmons index of bicyclic graphs is obtained by Deng, Chen and Zhang [H. Deng, S. Chen, J. Zhang, The Merrifield-Simmons index in (n,n+1)-graphs, J. Math. Chem. 43 (1) (2008) 75-91]. The sharp lower bound for the Merrifield-Simmons index of bicyclic graphs is determined by Jing and Li [W. Jing, S. Li, The number of independent sets in bicyclic graphs, Ars Combin, 2008 (in press)]. In this paper, we will consider the tricyclic graph, i.e., a connected graph with cyclomatic number 3. The tricyclic graph with n vertices having maximum Merrifield-Simmons index is determined.     

On the eccentric distance sum of graphs

The eccentric distance sum is a novel topological index that offers a vast potential for structure activity/property relationships. For a graph G, it is defined as ξd(G)=_∑v∈Vε(v)D(v), where ε(v) is the eccentricity of the vertex v and D(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. Motivated by [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 934-944], in this paper we characterize the extremal trees and graphs with maximal eccentric distance sum. Various lower and upper bounds for the eccentric distance sum in terms of other graph invariants including the Wiener index, the degree distance, eccentric connectivity index, independence number, connectivity, matching number, chromatic number and clique number are established. In addition, we present explicit formulae for the values of eccentric distance sum for the Cartesian product, applied to some graphs of chemical interest (like nanotubes and nanotori).     

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.     

Solution to a conjecture on the maximal energy of bipartite bicyclic graphs

The energy of a simple graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of its adjacency matrix. Let C_n denote the cycle of order n and the graph obtained from joining two cycles C₆ by a path P_n-12 with its two leaves. Let B_n denote the class of all bipartite bicyclic graphs but not the graph R_a,b, which is obtained from joining two cycles C_a and C_b (a,b≥10 and ) by an edge. In [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41(2001) 1002-1005], Gutman and Vidovi? conjectured that the bicyclic graph with maximal energy is , for n=14 and n≥16. In [X. Li, J. Zhang, On bicyclic graphs with maximal energy, Linear Algebra Appl. 427(2007) 87-98], Li and Zhang showed that the conjecture is true for graphs in the class B_n. However, they could not determine which of the two graphs R_a,b and has the maximal value of energy. In [B. Furtula, S. Radenkovi?, I. Gutman, Bicyclic molecular graphs with the greatest energy, J. Serb. Chem. Soc. 73(4)(2008) 431-433], numerical computations up to a+b=50 were reported, supporting the conjecture. So, it is still necessary to have a mathematical proof to this conjecture. This paper is to show that the energy of is larger than that of R_a,b, which proves the conjecture for bipartite bicyclic graphs. For non-bipartite bicyclic graphs, the conjecture is still open.     

The smallest values of algebraic connectivity for unicyclic graphs

The algebraic connectivity of G is the second smallest eigenvalue of its Laplacian matrix. Let U_n be the set of all unicyclic graphs of order n. In this paper, we will provide the ordering of unicyclic graphs in U_n up to the last seven graphs according to their algebraic connectivities when n≥13. This extends the results of Liu and Liu [Y. Liu, Y. Liu, The ordering of unicyclic graphs with the smallest algebraic connectivity, Discrete Math. 309 (2009) 4315-4325] and Guo [J.-M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711].     

On t-branch split cuts for mixed-integer programs

In this paper we study the t-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). They presented a family of mixed-integer programs with n integer variables and a single continuous variable and conjectured that the convex hull of integer solutions for any n has unbounded rank with respect to (n?1)-branch split cuts. It was shown earlier by Cook et al. (Math Program 47:155–174, 1990) that this conjecture is true when n = 2, and Li and Richard proved the conjecture when n = 3. In this paper we show that this conjecture is also true for all n > 3.     

Comparing Zagreb indices for connected graphs

It was conjectured that for each simple graph G=(V,E) with n=|V(G)| vertices and m=|E(G)| edges, it holds M₂(G)/m≥M₁(G)/n, where M₁ and M₂ are the first and second Zagreb indices. Hansen and Vuki?evi? proved that it is true for all chemical graphs and does not hold in general. Also the conjecture was proved for all trees, unicyclic graphs, and all bicyclic graphs except one class. In this paper, we show that for every positive integer k, there exists a connected graph such that m−n=k and the conjecture does not hold. Moreover, by introducing some transformations, we show that M₂/(m−1)>M₁/n for all bicyclic graphs and it does not hold for general graphs. Using these transformations we give new and shorter proofs of some known results.