Skip to main content

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 mathstackexchangeMath.SE, but got no replies

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 mathstackexchange, but got no replies

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

Source Link
Hao S
  • 111
  • 2
  • 11

Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?

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 mathstackexchange, but got no replies