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

Show simple item record Narayan, Darren en_US 2007-09-13T02:31:40Z en_US 2007-09-13T02:31:40Z en_US 2003 en_US
dc.identifier.citation Integers: Electronic Journal of Combinatorial Number Theory 3 (2003) A12 en_US
dc.identifier.issn 1553-1732 en_US
dc.identifier.uri en_US
dc.description.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). en_US
dc.description.sponsorship The author is indebted to a referee for many valuable suggestions, including an improved presentation of the proof of Theorem 3. This work was partially supported by a RIT College of Science Dean's Summer Research Fellowship Grant and a Reidler Foundation Grant. Thanks to Anthony Evans and Garth Isaak for useful discussions. Finally the author thanks Dustin Sheffield, now an undergraduate at Virginia Tech, for preliminary computer simulations. en_US
dc.language.iso en_US en_US
dc.publisher Integers en_US
dc.relation RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
dc.relation.ispartofseries vol. 3 en_US
dc.title An upper bound for the representation number of graphs with fixed order en_US
dc.type Article en_US
dc.subject.keyword Graph theory en_US
dc.subject.keyword Representation module en_US
dc.subject.keyword Representation number en_US

Files in this item

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

This item appears in the following Collection(s)

Show simple item record

Search RIT DML

Advanced Search