Can I read Upper Bounds on the Signed Edge Domination Number of a Graph on EtoBox?

Upper Bounds on the Signed Edge Domination Number of a Graph by Fengming Dong; Jun Ge; Yan Yang is a Computer Science article available to read on EtoBox.

What is Upper Bounds on the Signed Edge Domination Number of a Graph about?

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 ⌉ .

Who reads Upper Bounds on the Signed Edge Domination Number of a Graph?

Author

Fengming Dong; Jun Ge; Yan Yang

Publisher

Elsevier BV

Published

2021

Language

EN

Field

Computer Science (Physical Sciences)