On the Smallest Edge Defining Sets of Graphs

Abstract

For a given sequence of nonincreasing numbers, $\mathbf{d}=(d_1,\dots ,d_n)$, a necessary and sufficient condition is presented to characterize $d$ when its realization is a unique labelled simple graph. If $G$ is a graph, we consider the subgraph $G^{\prime }$ of $G$ with maximum edges which is uniquely determined with respect to its degree sequence. We call the set of $E(G)\setminus E(G^{\prime })$ the smallest edge defining set of $G$. This definition coincides with the similar one in design theory.