On the minimal sum of edges in a signed edge-dominated graph

DOI10.37236/10500MaRDI QIDQ2170791zbMATH OpenOpenAlexFDO

Authors Pavel Prozorov, Danila Cherkashin

Publication date 6 September 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2012.09956

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

signed edge domination functionsigned graphon

Mathematics Subject Classification ID

Vertex degrees (05C07) Signed and weighted graphs (05C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $G$ be a simple graph with $n$ vertices and $pm1$-weights on edges. Suppose that for every edge $e$ the sum of edges adjacent to $e$ (including $e$ itself) is positive. Then the sum of weights over edges of $G$ is at least $-frac{n}^{2}25$. Also we provide an example of a weighted graph with described properties and the sum of weights $-(1+o(1))frac{n}^{2}8(1+sqrt2{)}^2$. The previous best known bounds were $-frac{n}^{2}16$ and $-(1+o(1))frac{n}^{2}54$ respectively. We show that the constant $-1/54$ is optimal under some additional conditions.

Review text

Summary: Let \(G\) be a simple graph with \(n\) vertices and \(\pm 1\)-weights on edges. Suppose that for every edge \(e\) the sum of edges adjacent to \(e\) (including \(e\) itself) is positive. Then the sum of weights over edges of \(G\) is at least \(-\frac{n^2}{25} \). Also we provide an example of a weighted graph with described properties and the sum of weights \(-(1+o(1))\frac{n^2}{8(1 + \sqrt{2})^2}\). The previous best known bounds were \(-\frac{n^2}{16}\) and \(-(1+o(1))\frac{n^2}{54}\) respectively. We show that the constant \(-1/54\) is optimal under some additional conditions.

Recommendations

• On signed edge domination numbers of graphs
• Signed total edge domination number in graphs
• Some results on weighted graphs without induced cycles of nonpositive weights
• Some bounds for the signed edge domination number of a graph
• Upper bounds on the signed edge domination number of a graph

Cites work

• Graphs with maximal number of adjacent pairs of edges
• Large networks and graph limits
• On edge domination numbers of graphs
• On signed edge domination numbers of graphs
• On the signed edge domination number of graphs
• The sum of the squares of degrees: sharp asymptotics

Cited in

(3)

• Minimal signed dominating functions of graphs
• scientific article; zbMATH DE number 1472163 (Why is no real title available?)
• On the minimal sum of edge weights in a signed edge-dominated graph. II

This page was built for publication: On the minimal sum of edges in a signed edge-dominated graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170791)