Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

The Smallest Non-Autograph

100%

Baumer B. S., Wei Y., Bloom G. S.

Discussiones Mathematicae Graph Theory

2016

tom 36

nr 3

577-602

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Baumer B. S.

1 Bloom G. S.

1 Wei Y.

1 2016

Wyniki wyszukiwania

The Smallest Non-Autograph