Premium
COLLECTING AUTOGRAṔHS: n ‐NODE GRAPHS THAT HAVE n ‐INTEGER SIGNATURES 1
Author(s) -
Bloom Gary S.,
Hell Pavol,
Taylor Herbert
Publication year - 1979
Publication title -
annals of the new york academy of sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.712
H-Index - 248
eISSN - 1749-6632
pISSN - 0077-8923
DOI - 10.1111/j.1749-6632.1979.tb32778.x
Subject(s) - autograph , combinatorics , graph , discrete mathematics , mathematics , multiset , computer science , art , art history
S ummary 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.