31 |
Domination parameters of prisms of graphsSchurch, Mark. 10 April 2008 (has links)
No description available.
|
32 |
Disjunctive domination in graphs02 July 2015 (has links)
Ph.D. (Mathematics) / Please refer to full text to view abstract
|
33 |
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.$$
|
34 |
The 'coffee order' in Costa Rica, 1870-1889 : Formation and consolidation of a structure of dominationRodriguez, G. January 1983 (has links)
No description available.
|
35 |
Two conjectures on 3-domination critical graphsMoodley, Lohini 01 1900 (has links)
For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex
in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent
domination number i (G)) of G is the minimum cardinality amongst its dominating
sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1-
critical, if the domination number k decreases whenever an edge is added. Further, G
is hamiltonian if it has a cycle that passes through each of its vertices.
This dissertation assimilates research generated by two conjectures:
Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian.
Conjecture 2. If G is k-1-critical, then I ( G) = i ( G).
The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture
2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is
detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)
|
36 |
Semitotal domination in graphsMarcon, Alister Justin 02 July 2015 (has links)
Ph.D. (Mathematics) / Please refer to full text to view abstract
|
37 |
Paired-domination in graphsMcCoy, John Patrick 24 July 2013 (has links)
D.Phil. (Mathematics) / Domination and its variants are now well studied in graph theory. One of these variants, paired-domination, requires that the subgraph induced by the dominating set contains a perfect matching. In this thesis, we further investigate the concept of paired-domination. Chapters 2, 3, 4, and 5 of this thesis have been published in [17], [41], [42], and [43], respectively, while Chapter 6 is under submission; see [44]. In Chapter 1, we introduce the domination parameters we use, as well as the necessary graph theory terminology and notation. We combine the de nition of a paired-dominating set and a locating set to de ne three new sets: locating-paired- dominating sets, di erentiating-paired-dominating sets, and metric-locating-paired- dominating sets. We use these sets in Chapters 3 and 4. In Chapter 2, we investigate the relationship between the upper paired-domination and upper total domination numbers of a graph. In Chapter 3, we study the properties of the three kinds of locating paired-dominating sets we de ned, and in Chapter 4 we give a constructive characterisation of those trees which do not have a di erentiating- paired-dominating set. In Chapter 5, we study the problem of characterising planar graphs with diameter two and paired-domination number four. Lastly, in Chap- ter 6, we establish an upper bound on the size of a graph of given order and paired- domination number and we characterise the extremal graphs that achieve equality in the established bound.
|
38 |
Bounds on the Global Domination NumberDesormeaux, Wyatt J., Gibson, Philip E., Haynes, Teresa W. 01 January 2015 (has links)
A set S of vertices in a graph G is a global dominating set of G if S simultaneously dominates both G and its complement Ḡ. The minimum cardinality of a global dominating set of G is the global domination number of G. We determine bounds on the global domination number of a graph and relationships between it and other domination related parameters.
|
39 |
Total Domination Supercritical Graphs With Respect to Relative ComplementsHaynes, Teresa W., Henning, Michael A., Van Der Merwe, Lucas C. 06 December 2002 (has links)
A set S of vertices of a graph G is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γt(G) is the minimum cardinality of a total dominating set of G. Let G be a connected spanning subgraph of Ks,s, and let H be the complement of G relative to Ks,s; that is, Ks,s, = G ⊕ H is a factorization of Ks,s. The graph G is k-supercritical relative to Ks,s, if γt(G) = k and γ1(G + e) = k - 2 for all e ∈ E(H). Properties of k-supercritical graphs are presented, and k-supercritical graphs are characterized for small k.
|
40 |
Graphs with Large Italian Domination NumberHaynes, Teresa W., Henning, Michael A., Volkmann, Lutz 01 November 2020 (has links)
An Italian dominating function on a graph G with vertex set V(G) is a function f: V(G) → { 0 , 1 , 2 } having the property that for every vertex v with f(v) = 0 , at least two neighbors of v are assigned 1 under f or at least one neighbor of v is assigned 2 under f. The weight of an Italian dominating function f is the sum of the values assigned to all the vertices under f. The Italian domination number of G, denoted by γI(G) , is the minimum weight of an Italian dominating of G. It is known that if G is a connected graph of order n≥ 3 , then γI(G)≤34n. Further, if G has minimum degree at least 2, then γI(G)≤23n. In this paper, we characterize the connected graphs achieving equality in these bounds. In addition, we prove Nordhaus–Gaddum inequalities for the Italian domination number.
|
Page generated in 0.3746 seconds