
doi: 10.7151/dmgt.1129
handle: 20.500.12556/DKUM-65351
Summary: A dominating set \(D\) for a graph \(G\) is a subset of \(V(G)\) such that any vertex in \(V(G)-D\) has a neighbor in \(D\), and a domination number \(\gamma(G)\) is the size of a minimum dominating set for \(G\). For the Cartesian product \(G\square H\) Vizing's conjecture [cf. \textit{V. G. Vizing}, Vychisl. Sistemy, Novosibirsk 9, 30-43 (1963; Zbl 0194.25203)] states that \(\gamma(G\square H)\geq(G)\gamma(H)\) for every pair of graphs \(G\), \(H\). In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when \(\gamma(G)= \gamma(H)= 3\).
dominantno število, mathematics, graph theory, domination number, graph, info:eu-repo/classification/udc/519.17, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), teorija grafov, matematika, Cartesian product, kartezični produkt, graf
dominantno število, mathematics, graph theory, domination number, graph, info:eu-repo/classification/udc/519.17, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), teorija grafov, matematika, Cartesian product, kartezični produkt, graf
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 7 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
