On graphs with graphic imbalance sequences

Abstract

The imbalance of the edge e=uv in a graph \(G\) is the value \(imb_{G}(e)=|d_{G}(u)-d_{G}(v)|\). We prove that the sequence \(M_{G}\) of all edge imbalances in \(G\) is graphic for several classes of graphs including trees, graphs in which all non-leaf vertices form a clique and the so-called complete extensions of paths, cycles and complete graphs. Also, we formulate two interesting conjectures related to graphicality of \(M_{G}\).