On the minimal sum of edges in a signed edge-dominated graph

Abstract: Let

G

be a simple graph with

n

vertices and

p m 1

-weights on edges. Suppose that for every edge

e

the sum of edges adjacent to

e

(including

e

itself) is positive. Then the sum of weights over edges of

G

is at least

- f r a c n^{2} 25

. Also we provide an example of a weighted graph with described properties and the sum of weights

- (1 + o (1)) f r a c n^{2} 8 (1 + s q r t 2)^{2}

. The previous best known bounds were

- f r a c n^{2} 16

and

- (1 + o (1)) f r a c n^{2} 54

respectively. We show that the constant

- 1 / 54

is optimal under some additional conditions.

Full work available at URL: https://arxiv.org/abs/2012.09956

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (2)

This page was built for publication: On the minimal sum of edges in a signed edge-dominated graph