The Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n

Simple item page
dc.creatorAlpert, Matthew
dc.creatorFeder, Elie
dc.creatorHarborth, Heiko
dc.date2008-12-10
dc.date.accessioned2026-07-07T12:11:40Z
dc.date.available2026-07-07T12:11:40Z
dc.descriptionWe extend known results regarding the maximum rectilinear crossing number of the cycle graph (C_n) and the complete graph (K_n) to the class of general d-regular graphs R_{n,d}. We present the generalized star drawings of the d-regular graphs S_{n,d} of order n where n+d= 1 mod 2 and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of S_{n,d} for n = d = 0 mod 2 is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by Furry and Kleitman as partial results in the direction of this conjecture.
dc.description21 pages, 7 figures; submitted
dc.identifierhttps://arxiv.org/abs/0812.1917
dc.identifierhttp://arxiv.org/abs/0812.1917
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/210294
dc.subjectCombinatorics
dc.subject05C99
dc.titleThe Maximum of the Maximum Rectilinear Crossing Numbers of d-regular Graphs of Order n
dc.typetext

Files

Collections

arXiv