Upper bounds on the signed edge domination number of a graph.

A signed edge domination function (or SEDF) of a simple graph G = (V , E) is a function f : E → { 1 , − 1 } such that ∑ e ′ ∈ N [ e ] f (e ′) ≥ 1 holds for each edge e ∈ E , where N [ e ] is the set of edges in G that share at least one endpoint with e. Let γ s ′ (G) denote the minimum value of f (G) among all SEDFs f , where f (G) = ∑ e ∈ E f (e). In 2005, Xu conjectured that γ s ′ (G) ≤ n − 1 , where n is the order of G. This conjecture has been proved for the two cases v o d d (G) = 0 and v e v e n (G) = 0 , where v o d d (G) (resp. v e v e n (G)) is the number of odd (resp. even) vertices in G. This article proves Xu's conjecture for v e v e n (G) ∈ { 1 , 2 }. We also show that for any simple graph G of order n , γ s ′ (G) ≤ n + v o d d (G) ∕ 2 and γ s ′ (G) ≤ n − 2 + v e v e n (G) when v e v e n (G) > 0 , and thus γ s ′ (G) ≤ (4 n − 2) ∕ 3. Our result improves the best current upper bound of γ s ′ (G) ≤ ⌈ 3 n ∕ 2 ⌉. [ABSTRACT FROM AUTHOR]