In 2011, Henning, Löwenstein, and Rautenbach observed that the domination number of a graph is bounded above by the product of the packing number and the maximum degree of the graph. In this paper, ...we prove a stronger statement in subcubic graphs: The independent domination number is at most three times the packing number.
This article develops a submerged aspect of James C Scott’s work on ‘hidden transcripts’. Whereas Scott focused predominantly on the hidden transcripts of the powerless, here we propose a research ...agenda based upon studying hidden transcripts of the powerful. First, we define our terms. Second, we map existing literature, observing that although plenty of research exists into the public transcripts of dominant and subordinate groups, and that Scott initiated a productive research agenda into the hidden transcripts of powerless groups, research into hidden transcripts of powerful actors is lacking. We identify an assumption within this literature that because existing social institutions are already structured in such a way as to reflect and advance the interests of dominant groups, there is no need for separate spaces to foster the consciousness, cohesivness, and mobilisation of the powerful. Third, we ask how social scientists might study the hidden transcripts of the powerful, and what methodological challenges and opportunities such a research programme might present, identifying in particular the promising avenue of studying what we have chosen to call ‘transcripts hidden in plain sight’. Fourth, and finally, we question the epistemological status of these hidden transcripts, focusing on whether they can be used by social researchers as a reliable indicator of the ‘true’ consciousness of the social group that expresses them.
Eternal domination is a problem that asks the following question: Can we eternally defend a graph ? The principle is to defend against an attacked vertex, that changes every turn, by moving guards ...along the edges of the graph. In the classical version of the game (Burger et al., 2004), only one guard can move at a time, but in the m-eternal version (Goddard et al., 2005), any number of guards can move in a single turn. This problem led to the introduction of two parameters: the eternal and m-eternal domination numbers of the graph, that are the minimum numbers of guards necessary to defend against any infinite sequence of attacks.
In this paper, we first study the (m-)eternal domination number on digraphs. We show that a lot of results proven for undirected graphs can be generalized to digraphs. Then, we introduce the problem of oriented (m-)eternal domination, that consists in finding an orientation of a graph that minimizes the eternal domination number. We prove that computing the oriented eternal domination number is a coNP-hard problem, and we give a complete characterization of the graphs for which the oriented m-eternal domination number is 2. We also study these two parameters on trees, cycles, complete graphs, complete bipartite graphs, and different kinds of grids and products of graphs.
A subset S of vertices of a graph G is a double dominating set of G if every vertex in V(G)−S has at least two neighbors in S and every vertex of S has a neighbor in S. The double domination number ...γ×2(G) is the minimum cardinality of a double dominating set of G. Chellali (2006) showed that if T is a nontrivial tree of order n, with ℓ leaves and s support vertices, then γ×2(T)≥(2n+ℓ−s+2)∕3. In this paper we generalize the above lower bound for any connected graph. We show that if G is a connected graph of order n≥2 with k≥0 cycles, ℓ leaves and s support vertices, then γ×2(G)≥(2n+ℓ−s+2)∕3−2k∕3. We also characterize all graphs achieving equality for this new bound.
A new concept of vertices in a fuzzy graph known as defective vertices is introduced here. A vertex in a fuzzy network is called defective if no edges incident with it are strong. Defective vertex ...cannot be ignored when determining dominance in a fuzzy network because they are a part of the network. Finding defective vertices in a network is not much difficult when the adjacency matrix is given. In this paper, the novel concept of defective vertices of a fuzzy graph is introduced. Based on this idea a stable domination set and a stable domination number are defined. This also optimised the network by establishing minimal connectivity. We have proposed three algorithms for finding the defective vertices, establishing stable connectivity, and determining the stable domination number for a given graph. An application of stable domination in the diagnosis of chickenpox disease is demonstrated to show the effectiveness of the proposed algorithms.
An isolating set in a graph is a set X of vertices such that every edge of the graph is incident with a vertex of X or its neighborhood. The isolation number of a graph, or equivalently the ...vertex-edge domination number, is the minimum number of vertices in an isolating set. Caro and Hansberg, and independently Żyliński, showed that the isolation number is at most one-third the order for every connected graph of order at least 6. We show that in fact all such graphs have three disjoint isolating sets. Further, using a family introduced by Lemańska, Mora, and Souto-Salorio, we determine all graphs with equality in the original bound.
Quand on croise la théorie des grands cycles structurels avec le modèle classique centre – périphérie, l’analyse de l’évolution de la périphérie du Québec génère un éclairage pertinent sur son ...contexte contemporain de développement. Après une période historique de simple extraction de ressources naturelles livrées sur le marché mondial, l’émergence d’activités économiques endogènes a joué son rôle de rétention progressive de la richesse créée, avant que les forces exogènes se réaffirment dans leur domination des flux financiers. À travers ce double renversement des forces, le processus d’intégration territoriale s’est avéré réel et constant, délaissant cependant les zones insuffisamment dotées en ressources ou bien dont les ressources ont été épuisées. La structure industrielle est demeurée immature et dépendante après les décollages locaux. Largement soutenue par la politique publique, la transition régionale en cours cherche sa voie en jonglant avec les options pour un nouveau grand cycle structurel de développement.
This paper is motivated by the concept of the mixed domination problem on graphs and dedicated to the complexity of variations of the problem such as the signed mixed domination, signed edge ...domination, minus mixed domination, and minus edge domination problems. In this paper, we present NP-completeness and MAX SNP-hardness results for some of them, and present a general framework of solving these problems and various dominating and covering problems for trees in linear time.
PDF
