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/

[1] G. Bloom and S. Burr, On autographs which are complements of graphs of low degree, Carribean J. Math. 3 (1984) 17-28.

[2] G.S. Bloom, A chronology of the Ringel-Kotzig conjecture and the continuing quest to call all trees graceful, Annals of the New York Academy of Sciences 328 (1979) 32-51. doi:10.1111/j.1749-6632.1979.tb17766.x

[3] G.S. Bloom, P. Hell and H. Taylor, Collecting autographs: n-node graphs that have n-integer signatures, Annals of the New York Academy of Sciences 319 (1979) 93-102. doi:10.1111/j.1749-6632.1979.tb32778.x

[4] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman, New York, 1979).

[5] S. Gervacio, Which wheels are proper autographs, Southeast Asian Bull. Math. 7 (1983) 41-50.

[6] S. Golomb, How to number a graph, Graph Theory Comput. (1972) 23-37.

[7] F. Harary, Sum graphs and difference graphs, Congr. Numer. 72 (1990) 101-108.

[8] S. Hedge and Vasudeva, On mod difference labeling of digraphs, AKCE Int. J. Graphs Comb. 6 (2009) 79-84.

[9] E.M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. System Sci. 25 (1982) 42-65. doi:10.1016/0022-0000(82)90009-5

[10] A. Rosa, On certain valuations of the vertices of a graph, in: Theory of Graphs, Internat. Symposium, Rome, P. Rosenstiehl (Ed(s)), (New York, Gordon and Breach, 1966) 349-355.

[11] M. Seoud and E. Helmi, On difference graphs, J. Combin. Math. Combin. Comput. 76 (2011) 189.

[12] M. Sonntag, Difference labelling of cacti, Discuss. Math. Graph Theory 23 (2003) 55-65. doi:10.7151/dmgt.1185

[13] M. Sonntag, Difference labelling of digraphs, Discuss.Math. Graph Theory 24 (2004) 509-527. doi:10.7151/dmgt.1249

[14] K. Sugeng and J. Ryan, On several classes of monographs, Australas. J. Combin. 37 (2007) 277-284.