Currently displaying 1 – 9 of 9

Showing per page

Order by Relevance | Title | Year of publication

Total domination in categorical products of graphs

Douglas F. Rall — 2005

Discussiones Mathematicae Graph Theory

Several of the best known problems and conjectures in graph theory arise in studying the behavior of a graphical invariant on a graph product. Examples of this are Vizing's conjecture, Hedetniemi's conjecture and the calculation of the Shannon capacity of graphs, where the invariants are the domination number, the chromatic number and the independence number on the Cartesian, categorical and strong product, respectively. In this paper we begin an investigation of the total domination number on the...

On Graphs with Disjoint Dominating and 2-Dominating Sets

Michael A. HenningDouglas F. Rall — 2013

Discussiones Mathematicae Graph Theory

A DD2-pair of a graph G is a pair (D,D2) of disjoint sets of vertices of G such that D is a dominating set and D2 is a 2-dominating set of G. Although there are infinitely many graphs that do not contain a DD2-pair, we show that every graph with minimum degree at least two has a DD2-pair. We provide a constructive characterization of trees that have a DD2-pair and show that K3,3 is the only connected graph with minimum degree at least three for which D ∪ D2 necessarily contains all vertices of the...

Associative graph products and their independence, domination and coloring numbers

Richard J. NowakowskiDouglas F. Rall — 1996

Discussiones Mathematicae Graph Theory

Associative products are defined using a scheme of Imrich & Izbicki [18]. These include the Cartesian, categorical, strong and lexicographic products, as well as others. We examine which product ⊗ and parameter p pairs are multiplicative, that is, p(G⊗H) ≥ p(G)p(H) for all graphs G and H or p(G⊗H) ≤ p(G)p(H) for all graphs G and H. The parameters are related to independence, domination and irredundance. This includes Vizing's conjecture directly, and indirectly the Shannon capacity of a graph...

Vizing's conjecture and the one-half argument

Bert HartnellDouglas F. Rall — 1995

Discussiones Mathematicae Graph Theory

The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as well as the...

Improving some bounds for dominating Cartesian products

Bert L. HartnellDouglas F. Rall — 2003

Discussiones Mathematicae Graph Theory

The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds for dominating...

On dominating the Cartesian product of a graph and K₂

Bert L. HartnellDouglas F. Rall — 2004

Discussiones Mathematicae Graph Theory

In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and are investigated...

Connected domatic number in planar graphs

Bert L. HartnellDouglas F. Rall — 2001

Czechoslovak Mathematical Journal

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G . The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V ( G ) . We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.

Page 1

Download Results (CSV)