The Smallest Non-Autograph

• Autorzy: Benjamin S. Baumer , Yijin Wei , Gary S. Bloom
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

graph labeling; difference graphs; autographs; monographs

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 577-602

Daty

wydano

2016-08-01

otrzymano

2015-05-29

zaakceptowano

2015-09-25

online

2016-07-06

Twórcy

autor

Benjamin S. Baumer

• Program in Statistical & Data Sciences Smith College

autor

Yijin Wei

• Department of Mathematics and Statistics Smith College

autor

Gary S. Bloom

• Department of Computer Science City College

Bibliografia

• [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[Crossref]
• [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]
• [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[Crossref]
• [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[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.

Identyfikatory

DOI

10.7151/dmgt.1881