The diameter of almost Eulerian digraphs.
Hamiltonicity of -traceable graphs.
The Degree-Diameter Problem for Outerplanar Graphs
For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that [...] nΔ,D=ΔD2+O (ΔD2−1) is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.
Page 1