×

On the signed edge domination number of graphs. (English) Zbl 1186.05089

Summary: Let \(\gamma _s^\prime (G)\) be the signed edge domination number of \(G\). In 2006, Xu [B. Xu, “Two classes of edge domination in graphs”., Discrete Appl. Math. 154, No.10, 1541–1546 (2006; Zbl 1091.05055)] conjectured that: for any 2-connected graph \(G\) of order \(n(n\geq 2), \gamma _s^\prime (G)\geq 1\). In this article we show that this conjecture is not true. More precisely, we show that for any positive integer \(m\), there exists an \(m\)-connected graph \(G\) such that \(\gamma _s^\prime (G)\leq -\frac{m}{6}|V(G)|\). Also for every two natural numbers \(m\) and \(n\), we determine \(\gamma_s^\prime (K_{m,n})\), where \(K_{m,n}\) is the complete bipartite graph with part sizes \(m\) and \(n\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C22 Signed and weighted graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), North-Holland · Zbl 1134.05001
[2] Xu, B., Two classes of edge domination in graphs, Discrete Appl. Math., 154, 10, 1541-1546 (2006) · Zbl 1091.05055
[3] Xu, B., On edge domination numbers of graphs, Discrete Math., 294, 3, 311-316 (2005) · Zbl 1062.05116
[4] Xu, B., On signed edge domination numbers of graphs, Disc. Math., 239, 179-189 (2001) · Zbl 0979.05081
[5] Zelinka, B., On signed edge domination numbers of trees, Math. Bohem., 127, 1, 49-55 (2002) · Zbl 0995.05112
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.