- Tytuł:
- The Smallest Non-Autograph
- Autorzy:
-
Baumer, Benjamin S.
Wei, Yijin
Bloom, Gary S. - Powiązania:
- https://bibliotekanauki.pl/articles/31340873.pdf
- Data publikacji:
- 2016-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
graph labeling
difference graphs
autographs
monographs - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2016, 36, 3; 577-602
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł