Search

A topic of current interest in the study of topological indices is to find relations between some index and one or several relevant parameters and/or other indices. In this paper we study two general topological indices A&alpha, and B&alpha, defined for each graph H=(V(H),E(H)) by A&alpha, (H)=&sum, ij&isin, E(H)f(di,dj)&alpha, i&isin, V(H)h(di)&alpha, where di denotes the degree of the vertex i and &alpha, is any real number. Many important topological indices can be obtained from A&alpha, by choosing appropriate symmetric functions and values of &alpha, This new framework provides new tools that allow to obtain in a unified way inequalities involving many different topological indices. In particular, we obtain new optimal bounds on the variable Zagreb indices, the variable sum-connectivity index, the variable geometric-arithmetic index and the variable inverse sum indeg index. Thus, our approach provides both new tools for the study of topological indices and new bounds for a large class of topological indices. We obtain several optimal bounds of A&alpha, (respectively, B&alpha, ) involving A&beta, (respectively, B&beta, ). Moreover, we provide several bounds of the variable geometric-arithmetic index in terms of the variable inverse sum indeg index, and two bounds of the variable inverse sum indeg index in terms of the variable second Zagreb and the variable sum-connectivity indices.

The maximum weighted independent set (MWIS) problem is important since it occurs in various applications, such as facility location, selection of non-overlapping time slots, labeling of digital maps, etc. However, in real-life situations, input parameters within those models are often loosely defined or subject to change. For such reasons, this paper studies robust variants of the MWIS problem. The study is restricted to cases where the involved graph is a tree. Uncertainty of vertex weights is represented by intervals. First, it is observed that the max–min variant of the problem can be solved in linear time. Next, as the most important original contribution, it is proved that the min–max regret variant is NP-hard. Finally, two mutually related approximation algorithms for the min–max regret variant are proposed. The first of them is already known, but adjusted to the considered situation, while the second one is completely new. Both algorithms are analyzed and evaluated experimentally.