Optimization Problems on Threshold Graphs

Mihai Talmaciu, Elena Nechita

Abstract


During the last three decades, different types of decompositions have been processed in the field of graph theory. Among these we mention: decompositions based on the additivity of some characteristics of the graph, decompositions where the adjacency law between the subsets of the partition is known, decompositions where the subgraph induced by every subset of the partition must have predeterminate properties, as well as combinations of such decompositions. In this paper we characterize threshold graphs using the weakly decomposition, determine: density and stability number, Wiener index and Wiener polynomial for threshold graphs.

Keywords


Threshold graph, weakly decomposition, Wiener index, Wiener polynomial

Full Text:

PDF


(C) 2010-2017 EduSoft