Spelling suggestions: "subject:"domination"" "subject:"comination""
101 |
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.
|
102 |
Total Domination Stable Graphs Upon Edge AdditionDesormeaux, Wyatt J., Haynes, Teresa W., Henning, Michael A. 28 December 2010 (has links)
A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge addition stable if the addition of an arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge addition stable graphs. We determine a sharp upper bound on the total domination number of total domination edge addition stable graphs, and we determine which combinations of order and total domination number are attainable. We finish this work with an investigation of claw-free total domination edge addition stable graphs.
|
103 |
Differentials in GraphsMashburn, J., Haynes, T. W., Hedetniemi, S. M., Hedetniemi, S. T., Slater, P. J. 01 March 2006 (has links)
Let G = (V, E) be an arbitrary graph, and consider the following game. You are allowed to buy as many tokens as you like, say k tokens, at a cost of $1 each. You then place the tokens on some subset of k vertices of V. For each vertex of G which has no token on it, but is adjacent to a vertex with a token on it, you receive $1. Your objective is to maximize your profit, that is, the total value received minus the cost of the tokens bought. Let B(X) be the set of vertices in V - X that have a neighbor in a set X. Based on this game, we define the differential of a set X to be ∂ (X) = |B(X)| - |X|, and the differential of a graph to equal the max{∂(X)} for any subset X of V. In this paper, we introduce several different variations of the differential of a graph and study bounds on, and properties of, these novel parameters.
|
104 |
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.
|
105 |
Detour Domination in GraphsChartrand, Gary, Haynes, Teresa W., Henning, Michael A., Zhang, Ping 01 April 2004 (has links)
For distinct vertices u and v of a nontrivial connected graph G, the detour distance D(u, v) between u and v is the length of a longest u-v path in G. For a vertex v ∈ V(G), define D-(v) = min{D(u, v) : u ∈ V(G) - {v}}. A vertex u (≠ v) is called a detour neighbor of v if D(u, v) = D -(v). A vertex u is said to detour dominate a vertex u if u = v or u is a detour neighbor of v. A set S of vertices of G is called a detour dominating set if every vertex of G is detour dominated by some vertex in S. A detour dominating set of G of minimum cardinality is a minimum detour dominating set and this cardinality is the detour domination number γD(G) . We show that if G is a connected graph of order n ≥ 3, then γD(G) ≤ n - 2. Moreover, for every pair k, n of integers with 1 ≤ k ≤ n - 2, there exists a connected graph G of order n such that γD(G) = k. It is also shown that for each pair a, b of positive integers, there is a connected graph G with domination number γ(G) = a and γD(G) = b.
|
106 |
Hamiltonian Domination in GraphsChartrand, Gary, Haynes, Teresa W., Henning, Michael A., Zhang, Ping 01 November 2004 (has links)
For distinct vertices u and ν of a nontrivial connected graph G, the detour distance D(u, ν) between u and ν is the length of a longest u-ν path in C. For a vertex ν in G, define D+(ν) = max{D(u, ν) : u ∈ V(G) - {ν}}. A vertex u is called a hamiltonian neighbor of ν if D(u, ν) -D+(ν). A vertex v is said to hamiltonian dominate a vertex u if u = ν or u is a hamiltonian neighbor of ν. A set 5 of vertices of G is called a hamiltonian dominating set if every vertex of G is hamiltonian dominated by some vertex in S. A hamiltonian dominating set of minimum cardinality is a minimum hamiltonian dominating set and this cardinality is the hamiltonian domination number γH(G) of G. It is shown that if T is a tree of order n ≥ 3 and p is the order of the periphery of T, then γH(T) = n - p. It is also shown that if G is a connected graph of order n ≥ 3, then γH(G) ≤ n - 2. Moreover, for every pair k, n of integers with 1 ≤ k ≤ n - 2, there exists a connected graph G of order n such that γH(G) = k. For a vertex ν in G, define D- (ν) -min{D(u, ν) : u ∈ V(G) -{ν}}. A vertex u is called a detour neighbor of ν if D(u, ν) = D- (ν). The detour domination number γD(G) of G is defined analogously to γH(G)- It is shown that every pair a, b of positive integers is realizable as the domination number and hamiltonian domination number, respectively, of some graph. For integers a, b ≥ 2, the corresponding result is shown for the detour domination number and hamiltonian domination number. The problem of determining those rational numbers r and s with 0 < r, s < 1 for which there exists a graph G of order n such that γD(G)/n = r and γH/(G)/n = s is discussed.
|
107 |
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.
|
108 |
Trees with Unique Minimum Semitotal Dominating SetsHaynes, Teresa W., Henning, Michael A. 01 May 2020 (has links)
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 is the minimum cardinality of a semitotal dominating set of G. We observe that the semitotal domination number of a graph G falls between its domination number and its total domination number. We provide a characterization of trees that have a unique minimum semitotal dominating set.
|
109 |
Towards a critical approach to art education: in action research projectKriel, Sandra January 1992 (has links)
Magister Philosophiae - MPhil / The action research project documented in this thesis was informed by Jurgen Habermas' theory of knowledge-constitutive interests. In this theory Habermas postulates three anthropologically deep-seated interests that inform our search for knowledge. These interests are the technical, the practical and the emancipatory. In the action-research project, which was done in collaboration with a group of first year art students at Bellville College of Education, I attempted to uncover the values, assumptions and interests underlying our educational interaction in the hope of transforming it to be more empowering and emancipatory. The project went through three stages, each of which was informed by a different interest. The first stage could be described as having a technical interest because it was based on positivist assumptions of reductionism, duality and linearity. In this "- stage art was understood as being value-free, objectively describing and
reflecting visual reality. It was believed that theory and skills could be applied to achieve a predetermined product. In the second stage of the project the positivist paradigm of perception was replaced by the assumption that our relationship to others and the world is mediated by language which needs to be interpreted in a socio-political and historical context. Art does not only have a descriptive role but it can express
subjective understandings of the networks of meanings and social rules involved in experienced reality. Finally, the third stage evolved within a critical framework informed by an emancipatory interest. In the drawing project we looked critically at aspects of our society which frustrate and constrain individuals to sustain dependence, inequality and oppression. We tried to uncover existing power relations and the
historical, social and material conditions underlying certain problems we were experiencing. We hoped to find ways in which we could contribute to the transformation of ourselves and our society. The process of making art was here seen as a form of communicative action which can be empowering, emancipatory and transformative.
|
110 |
The Limits of Popular Control over GovernmentCurtis, Samuel John 12 May 2022 (has links)
Philip Pettit argues that freedom is best defined as non-domination, where domination is understood as subjection to uncontrolled interference. Pettit further argues that government is legitimate when it succeeds in preventing citizens from dominating each other without dominating them in the process, as this allows citizens to enjoy the protection of government without surrendering their freedom. Since Pettit argues that democratic (popular) control over government prevents government from dominating its citizens, Pettit argues that a legitimate, non-dominating state is possible. In this paper I argue that popular control cannot prevent government domination unless one accepts controversial, substantive value judgments about freedom and equality that Pettit claims his theory avoids. / Master of Arts / Philip Pettit argues that freedom is best understood as non-domination. By this, Pettit means that we are free when we have a strong degree of control over our choices and actions. He uses this definition to argue that democracy maintains the freedom of citizens because it means that the actions of government are under the control of citizens. This paper argues, contra Pettit, that citizens lack sufficient individual control over the actions of the government to maintain freedom as Pettit understands it. It further argues that one can only accept that government interference is not freedom reducing if one accepts certain substantive claims about freedom and equality.
|
Page generated in 0.1132 seconds