On the Smallest Edge Defining Sets of Graphs

Abstract

For a given sequence of nonincreasing numbers, \(\mathbf{d} = (d_1, \ldots, 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’\) 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’)\) the smallest edge defining set of \(G\). This definition coincides with the similar one in design theory.