Results 1 to 10 of about 215 (116)
A note on a Vizing's generalized conjecture [PDF]
Opuscula Mathematica, 2007 In this note we give a generalized version of Vizing's conjecture concerning the distance domination number for the cartesian product of two graphs.
Mostafa Blidia, Mustapha Chellali
doaj +3 more sources
Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 In this paper, we study a variant of graph domination known as $(t, r)$ broadcast domination, first defined in Blessing, Insko, Johnson, and Mauretour in 2015.
Tom Shlomi
doaj +3 more sources
KŐNIG’S LINE COLORING AND VIZING’S THEOREMS FOR GRAPHINGS [PDF]
Forum of Mathematics, Sigma, 2016 The classical theorem of Vizing states that every graph of maximum degree $d$ admits an edge coloring with at most
ENDRE CSÓKA +2 more
doaj +3 more sources
A New Framework to Approach Vizing’s Conjecture
Discussiones Mathematicae Graph Theory, 2021 We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing’s conjecture. The new framework unifies two different approaches to the conjecture.
Brešar Boštjan +4 more
doaj +4 more sources
On a Vizing-type Integer Domination Conjecture
Theory and Applications of Graphs, 2020 Given a simple graph G, a dominating set in G is a set of vertices S such that every vertex not in S has a neighbor in S. Denote the domination number, which is the size of any minimum dominating set of G, by γ(G). For any integer k ≥ 1, a function f : V
Elliot Krop, Randy Davila
doaj +5 more sources
A Class of Graphs Approaching Vizing's Conjecture
Theory and Applications of Graphs, 2016 For any graph G=(V,E), a subset S of V dominates G if all vertices are contained in the closed neighborhood of S, that is N[S]=V. The minimum cardinality over all such S is called the domination number, written γ(G). In 1963, V.G. Vizing conjectured that
Aziz Contractor, Elliot Krop
doaj +5 more sources
Sum-of-Squares Certificates for Vizing's Conjecture via Determining Gr\"obner Bases [PDF]
Journal of Symbolic Computation, 2023 The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs $G$ and $H$ is at least the product of the domination numbers of $G$ and $H$.
Gaar, Elisabeth, Siebenhofer, Melanie
core +5 more sources
An improvement in the two-packing bound related to Vizing's conjecture
Theory and Applications of Graphs, 2020 Vizing's conjecture states that the domination number of the Cartesian product of graphs is at least the product of the domination numbers of the two factor graphs.
Kimber Wolff
doaj +4 more sources
Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squares [PDF]
Journal of Symbolic Computation, 2020 Vizing's conjecture (open since 1968) relates the product of the domination numbers of two graphs to the domination number of their Cartesian product graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz existence question.
Gaar, Elisabeth +3 more
core +5 more sources
Journal of Mathematics, 2022 In this study, from a tree with a quasi-spanning face, the algorithm will route Hamiltonian cycles. Goodey pioneered the idea of holding facing 4 to 6 sides of a graph concurrently.
T. Anuradha +5 more
doaj +1 more source