Currently displaying 1 – 8 of 8

Showing per page

Order by Relevance | Title | Year of publication

Secure domination and secure total domination in graphs

William F. KlostermeyerChristina M. Mynhardt — 2008

Discussiones Mathematicae Graph Theory

A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that ( X - x ) u is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number γ s ( G ) ( γ s t ( G ) ) . We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then γ s t ( G ) γ s ( G ) . We also show that γ s t ( G ) is at most twice the clique covering number of...

Paired domination in prisms of graphs

Christina M. MynhardtMark Schurch — 2011

Discussiones Mathematicae Graph Theory

The paired domination number γ p r ( G ) of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: γ p r ( π G ) = 2 γ p r ( G ) for all πG; γ p r ( K G ) = 2 γ p r ( G ) ; γ p r ( K G ) = γ p r ( G ) .

Characterizing Cartesian fixers and multipliers

Stephen BeneckeChristina M. Mynhardt — 2012

Discussiones Mathematicae Graph Theory

Let G ☐ H denote the Cartesian product of the graphs G and H. In 2004, Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24(3) (2004), 389-402] characterized prism fixers, i.e., graphs G for which γ(G ☐ K₂) = γ(G), and noted that γ(G ☐ Kₙ) ≥ min{|V(G)|, γ(G)+n-2}. We call a graph G a consistent fixer if γ(G ☐ Kₙ) = γ(G)+n-2 for each n such that 2 ≤ n < |V(G)|- γ(G)+2, and characterize this class of graphs. Also in 2004, Burger,...

Counterexample to a conjecture on the structure of bipartite partitionable graphs

Richard G. GibsonChristina M. Mynhardt — 2007

Discussiones Mathematicae Graph Theory

A graph G is called a prism fixer if γ(G×K₂) = γ(G), where γ(G) denotes the domination number of G. A symmetric γ-set of G is a minimum dominating set D which admits a partition D = D₁∪ D₂ such that V ( G ) - N [ D i ] = D j , i,j = 1,2, i ≠ j. It is known that G is a prism fixer if and only if G has a symmetric γ-set. Hartnell and Rall [On dominating the Cartesian product of a graph and K₂, Discuss. Math. Graph Theory 24 (2004), 389-402] conjectured that if G is a connected, bipartite graph such that V(G) can be partitioned...

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

On the domination number of prisms of graphs

Alewyn P. BurgerChristina M. MynhardtWilliam D. Weakley — 2004

Discussiones Mathematicae Graph Theory

For a permutation π of the vertex set of a graph G, the graph π G is obtained from two disjoint copies G₁ and G₂ of G by joining each v in G₁ to π(v) in G₂. Hence if π = 1, then πG = K₂×G, the prism of G. Clearly, γ(G) ≤ γ(πG) ≤ 2 γ(G). We study graphs for which γ(K₂×G) = 2γ(G), those for which γ(πG) = 2γ(G) for at least one permutation π of V(G) and those for which γ(πG) = 2γ(G) for each permutation π of V(G).

Triangle Decompositions of Planar Graphs

Christina M. MynhardtChristopher M. van Bommel — 2016

Discussiones Mathematicae Graph Theory

A multigraph G is triangle decomposable if its edge set can be partitioned into subsets, each of which induces a triangle of G, and rationally triangle decomposable if its triangles can be assigned rational weights such that for each edge e of G, the sum of the weights of the triangles that contain e equals 1. We present a necessary and sufficient condition for a planar multigraph to be triangle decomposable. We also show that if a simple planar graph is rationally triangle decomposable, then it...

Page 1

Download Results (CSV)