A note on the signed edge domination number in graphs

作者：Fu Xueliang; Yang Yuansheng^*; Jiang Baoqi

来源：Discrete Applied Mathematics, 2008, 156(14): 2790-2792.

DOI：10.1016/j.dam.2007.10.024

• Signed edge domination function
• Signed edge domination number
• Closed edge-neighbourhood

Let G = (V(G), E(G)) be a graph. A function f : E(G) --> {+1, -1} is called the signed edge domination SEDF) of G if Sigma(e'is an element of N vertical bar e vertical bar) f (e') >= 1 for every e is an element of E (G). The signed edge domination number of G is defined as gamma(s)'(G) = min{Sigma(e is an element of E(G)) f(e)vertical bar f is a SEDFof G}. Xu [Baogen Xu, Two classes of edge domination in graphs, Discrete Applied Mathematics 154 (2006) 1541-1546] researched on the edge domination in graphs and proved that gamma(s)'(G) <= left perpendicular11/6n - 1right perpendicualr for any graph G of order n(n >= 4). In the article, he conjectured that: For any 2-connected graph G of order n(n >= 2), gamma(s)'(G) >= 1. In this note, we present Some counterexamples to the above conjecture and prove that there exists a family of k-connected graphs G(m,k) with gamma(s)'(G(m,k)) = k(m-1)(km+k+1)/2 (k >= 2, m > 1).

• 出版日期2008-7-28
• 单位大连理工大学; 内蒙古农业大学