Currently displaying 1 – 13 of 13

Showing per page

Order by Relevance | Title | Year of publication

Global alliances and independence in trees

Mustapha ChellaliTeresa W. Haynes — 2007

Discussiones Mathematicae Graph Theory

A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such...

Domination and independence subdivision numbers of graphs

Teresa W. HaynesSandra M. HedetniemiStephen T. Hedetniemi — 2000

Discussiones Mathematicae Graph Theory

The domination subdivision number s d γ ( G ) of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of adjacent vertices...

Bounds on the global offensive k-alliance number in graphs

Mustapha ChellaliTeresa W. HaynesBert RanderathLutz Volkmann — 2009

Discussiones Mathematicae Graph Theory

Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number γ k ( G ) is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on γ k ( G ) in terms of order, maximum degree, independence number, chromatic number and minimum degree.

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

k-independence stable graphs upon edge removal

Mustapha ChellaliTeresa W. HaynesLutz Volkmann — 2010

Discussiones Mathematicae Graph Theory

Let k be a positive integer and G = (V(G),E(G)) a graph. A subset S of V(G) is a k-independent set of G if the subgraph induced by the vertices of S has maximum degree at most k-1. The maximum cardinality of a k-independent set of G is the k-independence number βₖ(G). A graph G is called β¯ₖ-stable if βₖ(G-e) = βₖ(G) for every edge e of E(G). First we give a necessary and sufficient condition for β¯ₖ-stable graphs. Then we establish four equivalent conditions for β¯ₖ-stable trees.

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.

A Note on Non-Dominating Set Partitions in Graphs

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

Discussiones Mathematicae Graph Theory

A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is...

Downhill Domination in Graphs

Teresa W. HaynesStephen T. HedetniemiJessie D. JamiesonWilliam B. Jamieson — 2014

Discussiones Mathematicae Graph Theory

A path π = (v1, v2, . . . , vk+1) in a graph G = (V,E) is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1), where deg(vi) denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is...

Total domination edge critical graphs with maximum diameter

Lucas C. van der MerweCristine M. MynhardtTeresa W. Haynes — 2001

Discussiones Mathematicae Graph Theory

Denote the total domination number of a graph G by γₜ(G). A graph G is said to be total domination edge critical, or simply γₜ-critical, if γₜ(G+e) < γₜ(G) for each edge e ∈ E(G̅). For 3ₜ-critical graphs G, that is, γₜ-critical graphs with γₜ(G) = 3, the diameter of G is either 2 or 3. We characterise the 3ₜ-critical graphs G with diam G = 3.

Domination Subdivision Numbers

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number s d γ ( G ) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that 1 s d γ ( G ) 3 for any graph G. We give a counterexample to this conjecture. On the other hand, we show...

Page 1

Download Results (CSV)