PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 577-602
Tytuł artykułu

The Smallest Non-Autograph

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
36
Numer
3
Strony
577-602
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-05-29
zaakceptowano
2015-09-25
online
2016-07-06
Twórcy
autor
  • Department of Mathematics and Statistics Smith College, ywei@smith.edu
  • 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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1881
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.