Results 1 to 10 of about 59 (54)
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 +5 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
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
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 +1 more source
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 +1 more source
Maximum average degree of list-edge-critical graphs and Vizing's conjecture
Electronic Journal of Graph Theory and Applications, 2022 Vizing conjectured that χ′ℓ(G)≤Δ + 1 for all graphs. For a graph G and nonnegative integer k, we say G is a k-list-edge-critical graph if χ′ℓ(G)>k, but χ′ℓ(G − e)≤k for all e ∈ E(G).
Joshua Harrelson, Hannah Reavis
doaj +1 more source
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
Inequality Related to Vizing's Conjecture [PDF]
The Electronic Journal of Combinatorics, 2000 Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.
William Edwin Clark, Stephen Suen
openaire +2 more sources
An Improved Inequality Related to Vizing's Conjecture [PDF]
The Electronic Journal of Combinatorics, 2012 Vizing conjectured in 1963 that $\gamma(G \Box H) \geq \gamma(G)\gamma(H)$ for any graphs $G$ and $H$. A graph $G$ is said to satisfy Vizing's conjecture if the conjectured inequality holds for $G$ and any graph $H$. Vizing's conjecture has been proved for $\gamma(G) \le 3$, and it is known to hold for other classes of graphs.
Stephen Suen, Jennifer Tarr
openaire +2 more sources