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

For a graph G with vertex set V(G) and function f:V(G)→{0,1,2,3}, let Vi be the set of vertices assigned i by f. A perfect double Roman dominating function of a graph G is a function f:V(G)→{0,1,2,3} satisfying the conditions that (i) if u∈V0, then u is either adjacent to exactly two vertices in V2 and no vertex in V3 or adjacent to exactly one vertex in V3 and no vertex in V2; and (ii) if u∈V1, then u is adjacent to exactly one vertex in V2 and no vertex in V3. The perfect double Roman domination number of G, denoted γdRp(G), is the minimum weight of a perfect double Roman dominating function of G. We prove that if T is a tree of order n≥3, then γdRp(T)≤9n∕7. In addition, we give a family of trees T of order n for which γdRp(T) approaches this upper bound as n goes to infinity.

For a graph G, a set S is a dominating set if every vertex in V-S has a neighbor in S. A vertex contained in some minimum dominating set is called good; otherwise it is bad. A graph G has g(G) good vertices and b(G) bad vertices. The relationship between the order of G and g(G) assigns the graph to one of four classes. Our results include a method of classifying caterpillars. Further, we develop realizability conditions for a graph G given a triple of nonnegative integers representing the domination number of γ(G), g(G), and b(G), respectively, and provide constructions of graphs meeting those conditions. We define the goodness index of a vertex v in a graph G as the ratio of distinct γ(G)-sets containing v to the total number of γ(G)-sets, and provide formulas that yield the goodness index of any vertex in a given path.

This thesis examines the domination number of the semi-strong product of two graphs G and H where both G and H are simple and connected graphs. The product has an edge set that is the union of the edge set of the direct product of G and H together with the cardinality of V(H), copies of G. Unlike the other more common products (Cartesian, direct and strong), the semi-strong product is neither commutative nor associative. The semi-strong product is not supermultiplicative, so it does not satisfy a Vizing like conjecture. It is also not submultiplicative so it shares these two properties with the direct product. After giving the basic definitions related with graphs, domination in graphs and basic properties of the semi-strong product, this paper includes a general upper bound for the domination of the semi-strong product of any two graphs G and H as less than or equal to twice the domination numbers of each graph individually. Similar general results for the semi-strong product perfect-paired domination numbers of any two graphs G and H, as well as semi-strong products of some specific types of cycle graphs are also addressed.

We consider a variety of types of vertex sequences, which are defined in terms of a requirement that the next vertex in the sequence must meet. For example, let S = (v1, v2, …, vk ) be a sequence of distinct vertices in a graph G such that every vertex vi in S dominates at least one vertex in V that is not dominated by any of the vertices preceding it in the sequence S. Such a sequence of maximal length is called a dominating sequence since the set {v1, v2, …, vk } must be a dominating set of G. In this paper we survey the literature on dominating and other related sequences, and propose for future study several new types of vertex sequences, which suggest the beginning of a theory of vertex sequences in graphs.

Two vertices are said to be identifed if they are combined to form one vertex whose neighborhood is the union of their neighborhoods. A graph is total domination dot-critical if identifying any pair of adjacent vertices decreases the total domination number. On the other hand, a graph is total domination dot-stable if identifying any pair of adjacent vertices leaves the total domination number unchanged. Identifying any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most two. Among other results, we characterize total domination dot-critical trees with total domination number three and all total domination dot-stable graphs.

No description available.

Pour commencer mon sujet de thèse est le suivant : « la théorie de la politique budgétaire : du régime de domination monétaire à la crise des dettes souveraines ». L’objet de ma thèse est d’analyser l’évolution théorique de la politique budgétaire de 1980 jusqu’à la crise des dettes souveraines. De ce fait, je dois analyser le statut de la politique budgétaire dans le cadre d’un régime de domination monétaire. Pourquoi la politique budgétaire est sous un régime de domination monétaire ? Pourquoi est-elle considérée comme, inefficace, neutre et inutile (équivalence ricardienne, théorie du revenue permanent, effet d’éviction, incohérence intertemporelle) ? Quelle est dans ce cas l’articulation entre le politique budgétaire et la politique monétaire sous un régime de domination monétaire (la théorie budgétaire du niveau des prix et la théorie des jeux) ? Par ailleurs, lors de la crise de 2008, la politique budgétaire a été mobilisée, à travers la mise en œuvre de plan de relance pour éviter un effondrement des économies avancées. De ce fait, s’agit-il d’un retour de la politique budgétaire comme étant le principal instrument de régulation de la conjoncture économique (un régime de domination budgétaire), ou une exception à la règle (le nouveau consensus macroéconomique est-il remis en cause) ? S’agit-il d’une remise en cause du régime de domination monétaire ? / To begin my thesis topic is the following: "the theory of fiscal policy: from the regime of monetary domination to the crisis of sovereign debt". The object of my thesis is to analyze the theoretical evolution of fiscal policy from 1980 to the crisis of sovereign debt. Therefore, I must analyze the status of fiscal policy within the framework of a regime of monetary dominance. Why is fiscal policy under monetary rule? Why is it considered as inefficient, neutral and unnecessary (Ricardian equivalence, permanent revenue theory, predatory effect, intertemporal incoherence)? What is the relationship between fiscal policy and monetary policy under a regime of monetary domination (budgetary price theory and game theory)? Moreover, during the 2008 crisis, fiscal policy was mobilized, through the implementation of a recovery plan to avoid a collapse of advanced economies. Hence, is it a return to fiscal policy as the main instrument for regulating the economic situation (a regime of fiscal dominance), or an exception to the rule (is the new macroeconomic consensus challenged) ? Is this a questioning of the regime of monetary domination?

Thesis (Ph.D.)--University of Nebraska-Lincoln, 2006. / Title from title screen (site viewed on Feb. 5, 2007). PDF text: 66 p. : ill. (some col.) UMI publication number: AAT 3216432. Includes bibliographical references. Also available in microfilm and microfiche format.

This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the dominating set problem and a review of known bounds, focusing on algebraic bounds. We then consider this problem in the Kneser graphs, discussing basic results and previous work. We compute the domination number for a few of the Kneser graphs with the aid of some original results. We also investigate the connections between Kneser graph domination and the theory of combinatorial designs, and introduce a new type of design that generalizes the properties of dominating sets in Kneser graphs. We then consider dominating sets in the vector space analogue of Kneser graphs. We end by highlighting connections between the dominating set problem and other areas of combinatorics. Conjectures and open problems abound.