Displaying similar documents to “Transversals of circuits in the lexicographic product of directed graphs”

The Smallest Non-Autograph

Benjamin S. Baumer, Yijin Wei, Gary S. Bloom (2016)

Discussiones Mathematicae Graph Theory

Similarity:

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