Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
About this item
Full title
Author / Creator
Publisher
Philadelphia: Society for Industrial and Applied Mathematics
Journal title
Language
English
Formats
Publication information
Publisher
Philadelphia: Society for Industrial and Applied Mathematics
Subjects
More information
Scope and Contents
Contents
Universal traversal sequences for cycles require length $\Omega (n^{1.29} )$, improving the previous bound of $\Omega (n\log n)$. For $d \geq 3$, universal traversal sequences for $d$-regular graphs require length $\Omega (d^{0.71} n^{2.29} )$. For constant $d$, the best previous bound was $\Omega (n^2 \log n)$.
Alternative Titles
Full title
Lower Bounds on Universal Traversal Sequences for Cycles and Other Low Degree Graphs
Authors, Artists and Contributors
Author / Creator
Identifiers
Primary Identifiers
Record Identifier
TN_cdi_proquest_journals_919698628
Permalink
https://devfeature-collection.sl.nsw.gov.au/record/TN_cdi_proquest_journals_919698628
Other Identifiers
ISSN
0097-5397
E-ISSN
1095-7111
DOI
10.1137/0221067
