Vizing's conjecture
http://dbpedia.org/resource/Vizing's_conjecture an entity of type: WikicatConjectures
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing, and states that, if γ(G) denotes the minimum number of vertices in a dominating set for the graph G, then conjectured a similar bound for the domination number of the tensor product of graphs; however, a counterexample was found by . Since Vizing proposed his conjecture, many mathematicians have worked on it, with partial results described below. For a more detailed overview of these results, see .
rdf:langString
Гипотеза Визинга — предположение о связи доминирующего множества и прямого произведения графов, не подтверждённое по состоянию на 2017 год, при этом гипотеза доказана для ряда частных случаев. Впервые была высказана Вадимом Визингом. Утверждение гипотезы гласит, что для — минимального числа вершин в доминирующем множестве графа , выполнено: . В 1995 году предположены аналогичные границы для доминирующего числа тензорного произведения графов, однако позже найден контрпример.
rdf:langString
rdf:langString
Vizing's conjecture
rdf:langString
Гипотеза Визинга
xsd:integer
8175877
xsd:integer
1117794799
rdf:langString
Vadim G. Vizing
rdf:langString
Vadim G.
rdf:langString
Vizing
rdf:langString
Vizing Conjecture
rdf:langString
VizingConjecture
xsd:integer
1968
rdf:langString
In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing, and states that, if γ(G) denotes the minimum number of vertices in a dominating set for the graph G, then conjectured a similar bound for the domination number of the tensor product of graphs; however, a counterexample was found by . Since Vizing proposed his conjecture, many mathematicians have worked on it, with partial results described below. For a more detailed overview of these results, see .
rdf:langString
Гипотеза Визинга — предположение о связи доминирующего множества и прямого произведения графов, не подтверждённое по состоянию на 2017 год, при этом гипотеза доказана для ряда частных случаев. Впервые была высказана Вадимом Визингом. Утверждение гипотезы гласит, что для — минимального числа вершин в доминирующем множестве графа , выполнено: . В 1995 году предположены аналогичные границы для доминирующего числа тензорного произведения графов, однако позже найден контрпример.
xsd:nonNegativeInteger
8812
