4
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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
    Commented Aug 15, 2019 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
    Commented Aug 15, 2019 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
    Commented Aug 15, 2019 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
    Commented Aug 15, 2019 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
    Commented Aug 15, 2019 at 14:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .