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.
@article{bwmeta1.element.doi-10_7151_dmgt_1881,
author = {Benjamin S. Baumer and Yijin Wei and Gary S. Bloom},
title = {The Smallest Non-Autograph},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {577-602},
zbl = {1339.05347},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1881}
}
Benjamin S. Baumer; Yijin Wei; Gary S. Bloom. The Smallest Non-Autograph. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 577-602. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1881/
[1] G. Bloom and S. Burr, On autographs which are complements of graphs of low degree, Carribean J. Math. 3 (1984) 17-28. | Zbl 0574.05040
[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[Crossref] | Zbl 0465.05027
[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[Crossref] | Zbl 0484.05059
[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. | Zbl 0524.05054
[6] S. Golomb, How to number a graph, Graph Theory Comput. (1972) 23-37. | Zbl 0293.05150
[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[Crossref] | Zbl 0493.68064
[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. | Zbl 1233.05179
[12] M. Sonntag, Difference labelling of cacti , Discuss. Math. Graph Theory 23 (2003) 55-65. doi:10.7151/dmgt.1185[Crossref]
[13] M. Sonntag, Difference labelling of digraphs, Discuss.Math. Graph Theory 24 (2004) 509-527. doi:10.7151/dmgt.1249[Crossref]
[14] K. Sugeng and J. Ryan, On several classes of monographs, Australas. J. Combin. 37 (2007) 277-284. | Zbl 1125.05092