Vizing's conjecture is the most important open problem in domination theory, posed already in 1968. It asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In solving this problem and at the development of the theory on related problems, some of the members of our group actively participate. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper.
COBISS.SI-ID: 16083801
In this paper, we consider various problems concerning quasi-matchings and semi-matchings in bipartite graphs, which generalize the classical problem of determining a perfect matching in bipartite graphs. We prove a generalization of Hall's marriage theorem, and present an algorithm that solves the problem of determining a lexicographically minimum $g$-quasi-matching. We obtain that finding a lexicographically minimum quasi-matching is equivalent to minimizing any strictly convex function on the degrees of the A-side of a quasi-matching and use this fact to prove a more general statement. We also present an application in designing optimal CDMA-based wireless sensor networks.
COBISS.SI-ID: 16191577
In the paper the authors combine two so far separated areas of additive number theory. The first one builds on generalizations of Erdös-Ginzbur-Ziv theorem, while the second one on the fundamental Kneser’s theorem. Their main theorem turns out to imply several results that were so far unrelated. Although this paper presents a climax of certain field, the results imply possibility of further generalizations, going to the direction of the far-reaching Seymour-Schrijver hypothesis that combines the algebraic and the combinatorial side of additive number theory through the matroid theory.
COBISS.SI-ID: 15116377
One of the main areas of the project is the investigation of various convexities, related with the metric graph theory. In this article we consider g_3-convexity in a graph G that consists of those sets, whose Steiner interval with respect to any of its three vertices lies in them. Henning et al. (2009) proved that if every j-ball for all j)0 is g_3-convex in a graph G, then G has no induced house nor twin C_4, and every cycle in G of length at least six is well-bridged. In this paper we show that the converse of this theorem is true, thus characterizing the graphs in which all balls are g_3-convex.
COBISS.SI-ID: 16079193