An upper bound for the representation number of graphs with fixed order

Show full item record

Title: An upper bound for the representation number of graphs with fixed order
Author: Narayan, Darren
Abstract: A graph has a representation modulo n if there exists an injective map f: {V(G)} -> {0, 1, ... , n @ 1} such that vertices u and v are adjacent if and only if |f(u)@f(v)| is relatively prime to n. The representation number is the smallest n such that G has a representation modulo n. We seek the maximum value for the representation number over graphs of a fixed order. Erdos and Evans provided an upper bound in their proof that every finite graph can be represented modulo some positive integer. In this note we improve this bound and show that the new bound is best possible (Refer to PDF file for exact formulas).
Record URI: http://hdl.handle.net/1850/4756
Date: 2003

Files in this item

Files Size Format View
DNarayanArticle2003.pdf 336.2Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse