Mathematical aspects of some graph invariants

Abstract

A graph invariant is a numerical quantity that remains unchanged under graph isomorphism. Topological indices are graph invariants that represent certain topological features of a graph. For example, connectivity, planarity, girth and diameter are topological features of a graph. Similarly, degrees and distances in a graph are examples of some basic topological features. Some topological indices of a graph can be determined solely in terms of vertex degrees or in terms of distances between the vertices. The former is called a degree-based index and the later is a distance-based index. Another type of topological invariants is the spectrum-based indices that are obtained from the eigenvalues of a graph. Finding an extremal graph with respect to a topological index is the problem of determining a graph maximizing or minimizing the value of that parameter among all graphs of fixed order. Topological descriptors are used in QSAR/QSPR studies to correlate physico-chemical properties of molecules. Our primary focus in this thesis is the study of extremal graphs with respect to some distance-based topological invariants. The graphs on which we emphasize in this part include connected n-vertex graphs with n−1 edges (i.e. trees), connected n-vertex graphs containing n edges (i.e. unicyclic graphs) and connected n-vertex graphs with n + 1 edges (i.e. bicyclic graphs), where bicyclic graphs may contain two or three cycles. We also study the corresponding extremal conjugated graphs with respect to these indices. We further our investigation to compute closed analytical formulas for some recently defined distance-based indices of join and corona product of any finite number of graphs. Moreover, we compute distance-based indices of some 3-fence graphs and their line graphs. We also compute these indices of the finite square grid and its line graph. The mathematical concept of estimation can be defined as a process of approximating a desired result with a statistical technique or software tool. The second aim of this thesis is to estimate two spectrum-based indices for the molecular graphs of some nanotubes. More results of such kind are obtained for all nanocones with one arbitrary cycle as the core.