Currently displaying 1 – 20 of 23

Showing per page

Order by Relevance | Title | Year of publication

Graphs with large double domination numbers

Michael A. Henning — 2005

Discussiones Mathematicae Graph Theory

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ × 2 ( G ) . If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that γ × 2 ( G ) 3 n / 4 and we characterize those graphs achieving equality.

A characterization of roman trees

Michael A. Henning — 2002

Discussiones Mathematicae Graph Theory

A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is w ( f ) = v V f ( v ) . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number are called...

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...

On double domination in graphs

Jochen HarantMichael A. Henning — 2005

Discussiones Mathematicae Graph Theory

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ × 2 ( G ) . A function f(p) is defined, and it is shown that γ × 2 ( G ) = m i n f ( p ) , where the minimum is taken over the n-dimensional cube C = p = ( p , . . . , p ) | p i I R , 0 p i 1 , i = 1 , . . . , n . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then γ × 2 ( G ) ( ( l n ( 1 + d ) + l n δ + 1 ) / δ ) n .

Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

Michael A. HenningAlister J. Marcon — 2016

Discussiones Mathematicae Graph Theory

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating set of...

Bounds On The Disjunctive Total Domination Number Of A Tree

Michael A. HenningViroshan Naicker — 2016

Discussiones Mathematicae Graph Theory

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is a relaxation of arguably the most important domination parameter, namely the total domination number, γt(G). A set S of vertices in G is a disjunctive total dominating set of G if every vertex is adjacent to a vertex of S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number, [...] γtd(G) γ t d ( G ) , is the minimum cardinality of such a set. We observe that [...] γtd(G)≤γt(G)...

The diameter of paired-domination vertex critical graphs

Michael A. HenningChristina M. Mynhardt — 2008

Czechoslovak Mathematical Journal

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G , denoted by γ pr ( G ) , is the minimum cardinality of a paired-dominating set of G . The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one,...

A Characterization of Hypergraphs with Large Domination Number

Michael A. HenningChristian Löwenstein — 2016

Discussiones Mathematicae Graph Theory

Let H = (V, E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D ⊆ V such that for every vertex v ∈ V D there exists an edge e ∈ E for which v ∈ e and e ∩ D ≠ ∅. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all...

Domination Game: Extremal Families for the 3/5-Conjecture for Forests

Michael A. HenningChristian Löwenstein — 2017

Discussiones Mathematicae Graph Theory

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γg(G). Kinnersley, West and Zamani [SIAM J. Discrete Math. 27 (2013) 2090-2107]...

Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. HenningChristian LöwensteinDieter Rautenbach — 2010

Discussiones Mathematicae Graph Theory

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

Total domination subdivision numbers of graphs

Teresa W. HaynesMichael A. HenningLora S. Hopkins — 2004

Discussiones Mathematicae Graph Theory

A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number for some families...

Algorithmic aspects of total-subdomination in graphs

Laura M. HarrisJohannes H. HattinghMichael A. Henning — 2006

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph and let k ∈ Z⁺. A total k-subdominating function is a function f: V → {-1,1} such that for at least k vertices v of G, the sum of the function values of f in the open neighborhood of v is positive. The total k-subdomination number of G is the minimum value of f(V) over all total k-subdominating functions f of G where f(V) denotes the sum of the function values assigned to the vertices under f. In this paper, we present a cubic time algorithm to compute the total k-subdomination...

Domination Parameters of a Graph and its Complement

Wyatt J. DesormeauxTeresa W. HaynesMichael A. Henning — 2018

Discussiones Mathematicae Graph Theory

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

Page 1 Next

Download Results (CSV)