Vertices Missed by Longest Paths or Circuits.
Abstract
Let G denote a graph with v(G) vertices, and let c(G) and p(G) denote the maximal numbers of vertices contained in any simple circuit or path in G. The author denotes by c(j,k) (p(j,k)) the greatest lower bounds of v(G) where G is a k-connected graph such that for every choice of j vertices of G there exists in G a simple circuit (path) with c(G) (p(G)) vertices that misses the j chosen vertices. Analogously defined numbers with G restricted to planar graphs are denoted by (c sub 0)(j,k) and (p sub 0)(j,k). Extending various known results it is established that (c sub 0)(1,3) < or = 124, (p sub 0)(1,3) < or = 484, c(2.3) < or = 90 and p(2.3) < or = 324. (Modified author abstract)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1973
- Accession Number
- AD0764091
Entities
People
- Branko Grunbaum
Organizations
- University of Washington