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

 dc.contributor.author Narayan, Darren en_US dc.date.accessioned 2007-09-13T02:31:40Z en_US dc.date.available 2007-09-13T02:31:40Z en_US dc.date.issued 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 http://hdl.handle.net/1850/4756 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 en_US 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). dc.description.sponsorship The author is indebted to a referee for many valuable suggestions, including an improved en_US 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. 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 http://ritdml.rit.edu/handle/1850/4756 to RIT Scholar Works http://scholarworks.rit.edu/article/289, 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