Spelling suggestions: "subject:"domination number"" "subject:"comination number""
1 |
On the domination numbers of prisms of cyclesLin, Ming-Hung 16 January 2008 (has links)
Let $gamma(G)$ be the domination number of a graph $G$. For any
permutation $pi$ of the vertex set of a graph $G$, the prism of $G$
with respect to $pi$ is the graph $pi G$ obtained from two copies
$G_{1}$ and $G_{2}$ of $G$ by joining $uin V(G_{1})$ and $vin
V(G_{2})$ iff $v=pi(u)$. We prove that
$$gamma(pi C_{n})geq cases{frac{ n}{ 2}, &if $n = 4k ,$ cr
leftlceilfrac{n+1}{2}
ight
ceil, &if $n
eq 4k$,} mbox{and }
gamma(pi C_{n}) leq leftlceil frac{2n-1}{3}
ight
ceil
mbox{for all }pi.$$ We also find a permutation $pi_{t}$ such that
$gamma(pi_{t} C_{n})=k$, where $k$ between the lower bound and the
upper bound of $gamma(pi C_{n})$ in above. Finally, we prove that
if $pi_{b}C_{n}$ is a bipartite graph, then
$$gamma(pi_{b}C_{n})geq cases{frac{n}{2}, &if $n = 4k ,$cr
leftlceilfrac{n+1}{2}
ight
ceil, &if $n = 4k+2$,} mbox{and }
gamma(pi_{b}C_{n})leq leftlfloor frac{5n+2}{8}
ight
floor.$$
|
2 |
Strong Equality of Domination Parameters in TreesHaynes, Teresa W., Henning, Michael A., Slater, Peter J. 06 January 2003 (has links)
We study the concept of strong equality of domination parameters. Let P1 and P2 be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P2 also has property P1. Let ψ1(G) and ψ2(G), respectively, denote the minimum cardinalities of sets with properties P1 and P2, respectively. Then ψ1(G) ≤ ψ2(G). If ψ1(G)=ψ2(G) and every ψ1(G)-set is also a ψ2(G)-set, then we say ψ1(G) strongly equals ψ2(G), written ψ1(G) = ψ2(G). We provide a constructive characterization of the trees T such that γ(T) = i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T) = γt(T), where γt(T) denotes the total domination number of T, is also presented.
|
3 |
Trees With Equal Domination and Tree-Free Domination NumbersHaynes, Teresa W., Henning, Michael A. 01 June 2002 (has links)
The tree-free domination number y(G; -Fk), k ≥ 2, of a graph G is the minimum cardinality of a dominating set S in G such that the subgraph (S) induced by S contains no tree on k vertices as a (not necessarily induced) subgraph (equivalently, each component of (S) has cardinality less than k). When k = 2, the tree-free domination number is the independent domination number. We obtain a characterization of trees with equal domination and tree-free domination numbers. This generalizes a result of Cockayne et al. (A characterisation of (y,i)-trees. J. Graph Theory 34(4) (2000) 277-292).
|
4 |
Induced-Paired Domination in GraphsStuder, Daniel S., Haynes, Teresa W., Lawson, Linda M. 01 October 2000 (has links)
For a graph G = (V, E), a set S ⊆ V is a dominating set if every vertex in V - S is adjacent to at least one vertex in S. A dominating set S ⊆ V is a paired-dominating set if the induced subgraph 〈S〉 has a perfect matching. We introduce a variant of paired-domination where an additional restriction is placed on the induced subgraph 〈S〉. A paired-dominating set S is an induced-paired dominating set if the edges of the matching are the induced edges of 〈S〉, that is, 〈S〉 is a set of independent edges. The minimum cardinality of an induced-paired dominating set of G is the induced-paired domination number γip(G). Every graph without isolates has a paired-dominating set, but not all these graphs have an induced-paired dominating set. We show that the decision problem associated with induced-paired domination is NP-complete even when restricted to bipartite graphs and give bounds on γip(G). A characterization of those triples (a, b, c) of positive integers a ≤ b ≤ c for which a graph has domination number a, paired-domination number b, and induced-paired domination c is given. In addition, we characterize the cycles and trees that have induced-paired dominating sets.
|
5 |
Bounds on the Maximum Number of Minimum Dominating SetsConnolly, Samuel, Gabor, Zachary, Godbole, Anant, Kay, Bill, Kelly, Thomas 06 May 2016 (has links)
Given a graph with domination number γ, we find bounds on the maximum number of minimum dominating sets. First, for γ≥3, we obtain lower bounds on the number of γ-sets that do not dominate a graph on n vertices. Then, we show that γ-fold lexicographic product of the complete graph on n1/γ vertices has domination number γ and γn-O(nγ-γ/1) dominating sets of size γ. Finally, we see that a certain random graph has, with high probability, (i) domination number γ; and (ii) all but o(nγ) of its γ-sets being dominating.
|
6 |
Downhill Domination in GraphsHaynes, Teresa W., Hedetniemi, Stephen T., Jamieson, Jessie D., Jamieson, William B. 01 January 2014 (has links)
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 at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds.
|
7 |
Trees With Two Disjoint Minimum Independent Dominating SetsHaynes, Teresa W., Henning, Michael A. 28 November 2005 (has links)
The independent domination number of a graph G, denoted i(G), is the minimum cardinality of a maximal independent set of G. A maximal independent set of cardinality i(G) in G we call an i(G)-set. In this paper we provide a constructive characterization of trees G that have two disjoint i(G)-sets.
|
8 |
A Characterization of I-Excellent TreesHaynes, Teresa W., Henning, Michael A. 06 April 2002 (has links)
The independent domination number of a graph G, denoted i(G), is the minimum cardinality of a maximal independent set of G. A maximal independent set of cardinality i(G) in G we call an i(G)-set. The graph G is called i-excellent if every vertex of G belongs to some i(G)-set. We provide a constructive characterization of i-excellent trees.
|
9 |
Construction of Trees With Unique Minimum Semipaired Dominating SetsHaynes, Teresa W., Henning, Michael A. 01 February 2021 (has links)
Let G be a graph with vertex set V and no isolated vertices. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. We present a method of building trees having a unique minimum semipaired dominating set.
|
10 |
Unique Minimum Semipaired Dominating Sets in TreesHaynes, Teresa W., Henning, Michael A. 01 January 2020 (has links)
Let G be a graph with vertex set V. A subset S ? V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number is the minimum cardinality of a semipaired dominating set of G. We characterize the trees having a unique minimum semipaired dominating set. We also determine an upper bound on the semipaired domination number of these trees and characterize the trees attaining this bound.
|
Page generated in 0.0768 seconds