COLLECTING AUTOGRAṔHS: n‐NODE GRAPHS THAT HAVE n‐INTEGER SIGNATURES1
Gary S. Bloom, Pavol Hell, Herbert Taylor · Annals of the New York Academy of Sciences · 1979
Summary A new compact representation for many graphs is defined in a “numbered graph” context. Each integer of an n‐element multiset (the signature of the graph) is assigned to a node of an n‐node graph. An edge between a pair of nodes exists if and only if the absolute difference of their two node numbers is an element of the signature. A graph defined by such a signature is called an autograph. In this progress report families of autographs, including trees, are presented, and nonautographs are discussed. “Proper” signatures comprised only of positive integers are examined to determine which autographs may be drawn from them. Progress toward the objective of determining a characterization of proper autographs is discussed.