Three conjectures on the signed cycle domination in graphs
Let G=(V,E) be a graph, a function g:E?{?1,1} is said to be a signed cycle dominating function (SCDF for short) of G if ? e?E(C) g(e)?1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as ? sc (G)=min{? e?E(G) g(e)?g is an SCDF of G}. Xu (Discrete Math. 309:10071012, 2009) first researched the signed cycle domination number of graphs and raised the following conjectures: (1) Let G be a maximal planar graphs of order n?3. Then ? sc (G)=n?2; (2) For any graph G with ?(G)=3, ? sc (G)?1; (3) For any 2-connected graph G, ? sc (G)?1. In this paper, we present some results about these conjectures.
signed cycle domination number domination number maximal planar graph planar graph