Geodesic
The Smallest Non-Autograph
Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 577-602

Voir la notice de l'article provenant de la source Library of Science

Suppose that G is a simple, vertex-labeled graph and that S is a multiset. Then if there exists a one-to-one mapping between the elements of S and the vertices of G, such that edges in G exist if and only if the absolute difference of the corresponding vertex labels exist in S, then G is an autograph, and S is a signature for G. While it is known that many common families of graphs are autographs, and that infinitely many graphs are not autographs, a non-autograph has never been exhibited. In this paper, we identify the smallest non-autograph: a graph with 6 vertices and 11 edges. Furthermore, we demonstrate that the infinite family of graphs on n vertices consisting of the complement of two non-intersecting cycles contains only non-autographs for n ≥ 8.
Keywords: graph labeling, difference graphs, autographs, monographs 
@article{DMGT_2016_36_3_a5,
     author = {Baumer, Benjamin S. and Wei, Yijin and Bloom, Gary S.},
     title = {The {Smallest} {Non-Autograph}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {577--602},
     publisher = {mathdoc},
     volume = {36},
     number = {3},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a5/}
}
TY  - JOUR
AU  - Baumer, Benjamin S.
AU  - Wei, Yijin
AU  - Bloom, Gary S.
TI  - The Smallest Non-Autograph
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2016
SP  - 577
EP  - 602
VL  - 36
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a5/
LA  - en
ID  - DMGT_2016_36_3_a5
ER  - 
%0 Journal Article
%A Baumer, Benjamin S.
%A Wei, Yijin
%A Bloom, Gary S.
%T The Smallest Non-Autograph
%J Discussiones Mathematicae. Graph Theory
%D 2016
%P 577-602
%V 36
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a5/
%G en
%F DMGT_2016_36_3_a5
Baumer, Benjamin S.; Wei, Yijin; Bloom, Gary S. The Smallest Non-Autograph. Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 3, pp. 577-602. http://geodesic.mathdoc.fr/item/DMGT_2016_36_3_a5/