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.
An outer-independent double Roman dominating function (OIDRDF) of a graph
G
is a function
h
:
V
(
G
)
→
{
0,1,2,3
}
such that i) every vertex
v
with
f
(
v
)
=
0
is adjacent to at least one vertex ...with label 3 or to at least two vertices with label 2, ii) every vertex
v
with
f
(
v
)
=
1
is adjacent to at least one vertex with label greater than 1, and iii) all vertices labeled by 0 are an independent set. The weight of an OIDRDF is the sum of its function values over all vertices. The outer-independent double Roman domination number
γ
oidR
(
G
) is the minimum weight of an OIDRDF on
G
. It has been shown that for any tree
T
of order
n
≥ 3,
γ
oidR
(
T
) ≤ 5n/4 and the problem of characterizing those trees attaining equality was raised. In this article, we solve this problem and we give additional bounds on the outer-independent double Roman domination number. In particular, we show that, for any connected graph
G
of order
n
with minimum degree at least two in which the set of vertices with degree at least three is independent,
γ
oidR
(
T
) ≤ 4n/3.
Let G be a graph with no isolated vertex and let N(v) be the open neighbourhood of v∈V(G). Let f:V(G)→{0,1,2} be a function and Vi={v∈V(G):f(v)=i} for every i∈{0,1,2}. We say that f is a strongly ...total Roman dominating function on G if the subgraph induced by V1∪V2 has no isolated vertex and N(v)∩V2≠∅ for every v∈V(G)\V2. The strongly total Roman domination number of G, denoted by γtRs(G), is defined as the minimum weight ω(f)=∑x∈V(G)f(x) among all strongly total Roman dominating functions f on G. This paper is devoted to the study of the strongly total Roman domination number of a graph and it is a contribution to the Special Issue “Theoretical Computer Science and Discrete Mathematics” of Symmetry. In particular, we show that the theory of strongly total Roman domination is an appropriate framework for investigating the total Roman domination number of lexicographic product graphs. We also obtain tight bounds on this parameter and provide closed formulas for some product graphs. Finally and as a consequence of the study, we prove that the problem of computing γtRs(G) is NP-hard.
Perfect Graphs for Domination Games Bujtás, Csilla; Iršič, Vesna; Klavžar, Sandi
Annals of combinatorics,
03/2021, Volume:
25, Issue:
1
Journal Article
Peer reviewed
Open access
Let
γ
(
G
)
and
γ
t
(
G
)
be the domination number and the total domination number of a graph
G
, respectively, and let
γ
g
(
G
)
and
γ
tg
(
G
)
be the game domination number and the game total ...domination number of
G
, respectively. Then,
G
is
γ
g
-
perfect
(resp.
γ
tg
-
perfect
) if every induced subgraph
F
of
G
satisfies
γ
g
(
F
)
=
γ
(
F
)
(resp.
γ
tg
(
F
)
=
γ
t
(
F
)
). A recursive characterization of
γ
g
-perfect graphs is derived. The characterization yields a polynomial recognition algorithm for
γ
g
-perfect graphs. It is proved that every minimally
γ
g
-imperfect graph has domination number 2. All minimally
γ
g
-imperfect triangle-free graphs are determined. It is also proved that
γ
tg
-perfect graphs are precisely
2
P
3
¯
-free cographs.
The connected domination game is played just as the domination game, with an additional requirement that at each stage of the game the vertices played induce a connected subgraph. The number of moves ...in a D-game (an S-game, resp.) on a graph
G
when both players play optimally is denoted by
γ
cg
(
G
)
(
γ
cg
′
(
G
)
, resp.). Connected Game Continuation Principle is established as a substitute for the classical Continuation Principle which does not hold for the connected domination game. Let
G
|
x
denote the graph
G
together with a declaration that the vertex
x
is already dominated. The first main result asserts that if
G
is a graph with
γ
cg
(
G
)
≥
3
and
x
∈
V
(
G
)
, then
γ
cg
(
G
|
x
)
≤
2
γ
cg
(
G
)
-
3
and the bound is sharp. The second main theorem states that if
G
is a graph with
n
(
G
)
≥
2
and
x
∈
V
(
G
)
, then
γ
cg
(
G
|
x
)
≥
1
2
γ
cg
(
G
)
and the bound is sharp. Graphs
G
and their vertices
x
for which
γ
cg
′
(
G
|
x
)
=
∞
holds are also characterized.
Total dominating sequences in graphs Brešar, Boštjan; Henning, Michael A.; Rall, Douglas F.
Discrete mathematics,
06/2016, Volume:
339, Issue:
6
Journal Article
Peer reviewed
Open access
A vertex in a graph totally dominates another vertex if they are adjacent. A sequence of vertices in a graph G is called a total dominating sequence if every vertex v in the sequence totally ...dominates at least one vertex that was not totally dominated by any vertex that precedes v in the sequence, and at the end all vertices of G are totally dominated. While the length of a shortest such sequence is the total domination number of G, in this paper we investigate total dominating sequences of maximum length, which we call the Grundy total domination number, γgrt(G), of G. We provide a characterization of the graphs G for which γgrt(G)=|V(G)| and of those for which γgrt(G)=2. We show that if T is a nontrivial tree of order n with no vertex with two or more leaf-neighbors, then γgrt(T)≥23(n+1), and characterize the extremal trees. We also prove that for k≥3, if G is a connected k-regular graph of order n different from Kk,k, then γgrt(G)≥(n+⌈k2⌉−2)/(k−1) if G is not bipartite and γgrt(G)≥(n+2⌈k2⌉−4)/(k−1) if G is bipartite. The Grundy total domination number is proven to be bounded from above by two times the Grundy domination number, while the former invariant can be arbitrarily smaller than the latter. Finally, a natural connection with edge covering sequences in hypergraphs is established, which in particular yields the NP-completeness of the decision version of the Grundy total domination number.
The Grundy domination number, γgr(G), of a graph G is the maximum length of a sequence (v1,v2,…,vk) of vertices in G such that for every i∈{2,…,k}, the closed neighborhood Nvi contains a vertex that ...does not belong to any closed neighborhood Nvj, where j<i. It is well known that the Grundy domination number of any graph G is greater than or equal to the upper domination number Γ(G), which is in turn greater than or equal to the independence number α(G). In this paper, we initiate the study of the class of graphs G with Γ(G)=γgr(G) and its subclass consisting of graphs G with α(G)=γgr(G). We characterize the latter class of graphs among all twin-free connected graphs, provide a number of properties of these graphs, and prove that the hypercubes are members of this class. In addition, we give several necessary conditions for graphs G with Γ(G)=γgr(G) and present large families of such graphs.
PDF
