The Smallest Non-Autograph

Benjamin S. Baumer; Yijin Wei; Gary S. Bloom

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 577-602
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Benjamin S. Baumer, Yijin Wei, and Gary S. Bloom. "The Smallest Non-Autograph." Discussiones Mathematicae Graph Theory 36.3 (2016): 577-602. <http://eudml.org/doc/285690>.

@article{BenjaminS2016,
abstract = {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.},
author = {Benjamin S. Baumer, Yijin Wei, Gary S. Bloom},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph labeling; difference graphs; autographs; monographs},
language = {eng},
number = {3},
pages = {577-602},
title = {The Smallest Non-Autograph},
url = {http://eudml.org/doc/285690},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Benjamin S. Baumer
AU - Yijin Wei
AU - Gary S. Bloom
TI - The Smallest Non-Autograph
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 577
EP - 602
AB - 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.
LA - eng
KW - graph labeling; difference graphs; autographs; monographs
UR - http://eudml.org/doc/285690
ER -

References

top
  1. [1] G. Bloom and S. Burr, On autographs which are complements of graphs of low degree, Carribean J. Math. 3 (1984) 17-28. Zbl0574.05040
  2. [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] Zbl0465.05027
  3. [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] Zbl0484.05059
  4. [4] M.R. Garey and D.S. Johnson, Computers and Intractability (W.H. Freeman, New York, 1979). 
  5. [5] S. Gervacio, Which wheels are proper autographs, Southeast Asian Bull. Math. 7 (1983) 41-50. Zbl0524.05054
  6. [6] S. Golomb, How to number a graph, Graph Theory Comput. (1972) 23-37. Zbl0293.05150
  7. [7] F. Harary, Sum graphs and difference graphs, Congr. Numer. 72 (1990) 101-108. 
  8. [8] S. Hedge and Vasudeva, On mod difference labeling of digraphs, AKCE Int. J. Graphs Comb. 6 (2009) 79-84. 
  9. [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] Zbl0493.68064
  10. [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. [11] M. Seoud and E. Helmi, On difference graphs, J. Combin. Math. Combin. Comput. 76 (2011) 189. Zbl1233.05179
  12. [12] M. Sonntag, Difference labelling of cacti , Discuss. Math. Graph Theory 23 (2003) 55-65. doi:10.7151/dmgt.1185[Crossref] 
  13. [13] M. Sonntag, Difference labelling of digraphs, Discuss.Math. Graph Theory 24 (2004) 509-527. doi:10.7151/dmgt.1249[Crossref] 
  14. [14] K. Sugeng and J. Ryan, On several classes of monographs, Australas. J. Combin. 37 (2007) 277-284. Zbl1125.05092

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.