In this study, we enhance Markowitz portfolio selection with graph theory for the analysis of two portfolios composed of either EU or US assets. Using a threshold-based decomposition of their respective covariance matrices, we perturb the level of risk in each portfolio and build the corresponding sets of graphs.