Consider a planar graph where every vertex is incident to at least 3 edges, and assign to each edge a weight equal to the sum of the degrees of its endpoints.

If not, what is the smallest n so that every such graph has an edge cover (a set of edges such that every vertex is incident to at least one edge in the set) with average weight at most n?

I am also interested in other questions/reference material pertaining to "light subgraphs", ( subgraphs of low degree)

For instance, is there a long path with low degree vertices on average? There seems to be some reasonable material on low degree triangles, but I could not find any info on light graphs with 4 or more vertices.

I have posted this question on Math.SE, but got no replies

  • 2
    $\begingroup$ Why $14$? Do you already have a counterexample with $13$, or a potential application for $14$? (It's easy to see that $n$ can't be brought below $10$, because the icosahedron is a planar graph where every edge has weight $5+5=10$.) $\endgroup$ – Noam D. Elkies Aug 15 '19 at 2:53
  • $\begingroup$ Aren't the wheel graphs (en.wikipedia.org/wiki/Wheel_graph) a counter example for any $n$? These also don't have an edge cover with a universal bound. In fact any sequence of planar graphs that have one vertex with degree going to infinity should provide a counter example. $\endgroup$ – quarague Aug 15 '19 at 7:15
  • $\begingroup$ @quarague I think the average weight for a cover of the wheel is $\sim 8$ for large wheels. A wheel with $n$ vertices on the rim can be covered by $\sim n/2+1$ edges, one of which has weight $n+3$, and the other have weight $6$. $\endgroup$ – M. Winter Aug 15 '19 at 7:34
  • 2
    $\begingroup$ @NoamD.Elkies Here an example of average weight $>13$ from OP's previous question. Like your example, it is based on a polyhedron, the triakis icosahedron, in which each edge has weight $\ge 13$. $\endgroup$ – M. Winter Aug 15 '19 at 8:17
  • $\begingroup$ @M.Winter Thanks, I overlooked the 'average', the wheel graphs are anexample where one edge has high weight but the average of an edge cover doesn't need to explode. $\endgroup$ – quarague Aug 15 '19 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.