The number of independent subsets and the energy of caterpillars under degree restriction

Abstract

The energy En(G) of a graph G is defined as the sum of the absolute values of its eigenvalues. The Hosoya index Z(G) of a graph G is the number of independent edge subsets of G, including the empty set. And, the Merrifield-Simmons index σ(G) of a graph G is the number of independent vertex subsets of G, including the empty set. The studies of these three graph invariants are motivated by their application in chemistry, combined with pure mathematical interests. In particular, they can be used to predict boiling points of saturated hydrocarbons and estimate the total π-electron energy. For ℓ ≥ 1, let a1, a2, . . . , aℓ be non-negative integers, such that a1 and aℓ are positive. The tree obtained from the path graph of vertices v1, v2, . . . , vℓ, by attaching ai new leaves to vi, for 1 ≤ i ≤ ℓ, is called a (a1, a2, . . . , aℓ)-caterpillar and denoted by C(a1 + 1, a2 + 2, . . . , aℓ−1 + 2, aℓ +1). In this thesis, we characterize extremal caterpillars relative to the energy, the Hosoya index and the Merrifield-Simmons index. We first study caterpillars with the same degree sequence, then compare caterpillars of the same size, same order, and different degree sequence. For any given degree sequence D, we characterize the caterpillar X(D) that maximizes Z and En. In X(D), as we move along the internal path towards the center, the degrees are in a nondecreasing order. Characterization of the caterpillar S(D) that has the minimum Z and En and maximum σ is also provided. In S(D), large and small degrees alternate.