Three conjectures on the signed cycle domination in graphs

Three conjectures on the signed cycle domination in graphs

0.00 Avg rating0 Votes
Article ID: iaor20132803
Volume: 25
Issue: 4
Start Page Number: 639
End Page Number: 645
Publication Date: May 2013
Journal: Journal of Combinatorial Optimization
Authors: , , ,
Keywords: combinatorial optimization
Abstract:

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 ∑ eE(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{∑ eE(G) g(e)∣g is an SCDF of G}. Xu (Discrete Math. 309:1007–1012, 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.

Reviews

Required fields are marked *. Your email address will not be published.