Fashion game on graphs Shen, Chenli; Lin, Wensong
Discrete optimization,
November 2020, 2020-11-00, Volume:
38
Journal Article
Peer reviewed
In this paper, we propose and study an optimization problem of the fashion game on graphs, which can be regarded as a graph extension of matching pennies. There are two kinds of players in a graph G: ...Conformists and Rebels. All players choose their actions from an identical set of the two symmetric actions, say {0,1}. An action profile π of G is a mapping from the vertex set of G to the action set {0,1}. A conformist (resp. rebel) likes people having the same (resp. different) action with her and dislikes people having the different (resp. same) action. The utility u(v,π) of a player v under the action profile π is the number of neighbors she likes minus the number of neighbors she dislikes. The utility u(G,π) of G under π is the minimum utility among all players. Let t be an integer. A graph G is said to be t-satisfiable if there is an action profile of G such that all players have utilities at least t. The utility of G, denoted by u(G), is the maximum t such that G is t-satisfiable.
We provide simple characterizations to determine the utilities of paths, cycles, and complete graphs. We design a linear-time algorithm to determine the utility of a tree. We obtain lower bounds of utilities of graphs containing only rebels, t-degenerate graphs, and the kth power of paths, respectively. We also prove that for any fixed integer t≥−2, the problem of deciding if a graph containing both conformists and rebels is t-satisfiable is NP-complete, and for any fixed integer t≥1, the problem of deciding if a graph containing only rebels is t-satisfiable is also NP-complete. We finally propose some further research problems on this topic.
Display omitted
•PNA/g-C3N4 was synthesized by incorporating carbanyl and amido groups directly.•A series of PNA/g-C3N4 was obtained to adjust the amount of phenyl group.•The highest ...photo-degradation of 93% was achieved when the content of PNA was 1%.
A novel and straightforward operation was used to graft the p-nitrobenzoic acid (PNA) to the terminal of graphitic carbon nitride (g-C3N4) by incorporating carbanyl and amido groups. The synthesized product possessed good performance in the photodegradation of rhodamine B (RhB). FTIR and XPS results showed that PNA has successfully grafted onto g-C3N4. Optical tests indicated the band gap of g-C3N4 narrowed after being modified, greatly improved separation efficiency of electric carriers. According to the experimental results, the photodegradation rate of RhB increased significantly, and the degradation efficiency was about five times higher than that of the pristine g-C3N4.
An
L
(
2
,
1
)
-labelling of a graph
G is an assignment of nonnegative integers to the vertices of
G such that vertices at distance two get different numbers and adjacent vertices get numbers which ...are at least two apart. The
L
(
2
,
1
)
-labelling number of a graph
G,
λ
(
G
)
, is the minimum range of labels over all
L
(
2
,
1
)
-labellings of
G. Given two graphs
G and
H, the direct product of
G and
H is the graph
G
×
H
with vertex set
V
(
G
)
×
V
(
H
)
in which two vertices
(
x
,
y
)
and
(
x
′
,
y
′
)
are adjacent if and only if
xx
′
∈
E
(
G
)
and
yy
′
∈
E
(
H
)
. In this paper, we completely determine the
L
(
2
,
1
)
-labelling numbers of
K
m
×
K
n
for
m
,
n
⩾
2
, and
K
m
×
P
n
for
m
⩾
3
,
n
⩾
1
, where
P
n
is the path of length
n. The
L
(
2
,
1
)
-labelling numbers of
K
m
×
C
n
for
m
⩾
3
and some special values of
n are also determined, where
C
n
is the cycle of length
n.
A vertex coloring is called
2
-distance if any two vertices at distance at most
2
from each other get different colors. The minimum number of colors in 2-distance colorings of
G
is its 2-distance ...chromatic number, denoted by
χ
2
(
G
)
. Let
G
be a plane graph with girth at least
5
. In this paper, we prove that
χ
2
(
G
)
≤
Δ
+
8
for arbitrary
Δ
(
G
)
, which partially improves some known results.
An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. Let χi(G) be the injective chromatic number of a graph G. In ...this paper, we investigate the injective coloring of planar graphs with girth 6. We improve some results of Borodin and Ivanova (2011) 1, Doyon et al. (2010) 4 and Li and Xu (2012) 6 by showing that if G is a planar graph with girth at least 6, then (1) χi(G)≤Δ+3; (2) χi(G)≤Δ+2 if Δ≥9; (3) χi(G)≤Δ+1 if Δ≥17.
In this work, the CdS quantum dots (QDs) decorated Bi
2
MoO
6
/Bi
2
Mo
3
O
12
(BMO) heterojunction photocatalyst (C/BMO) has been successfully synthesized using a facile two-step hydrothermal method. ...The as-prepared photocatalysts were characterized by XRD, FTIR, XPS, FESEM, TEM, UV-vis DRS, PL and photoelectrochemical measurements to investigate the effects of CdS(QDs) and BMO heterojunction on the structure, morphology, optical and charge carrier transmission characteristics of the photocatalysts. Narrow band gap and superior catalytic activities were found in C/BMO as compared with pure BMO. Moreover, the C/BMO photocatalyst containing twice CdS content (2-C/BMO) exhibits even higher photocatalytic activity and stability. After exposure to visible light for 30 min, the degradation rate of Rhodamine B (RhB), Methylene blue (MB) and Ofloxacin (OFX) by 2-C/BMO reached 95%, 92% and 76%, respectively. Radicals scavenging experiments and electron spin-resonance spectroscopy (ESR) investigations indicated that the superoxide radical anions (
), hole (h
+
) and hydroxyl radicals (*OH) are the dominating active species in the photodegradation processes.
and h
+
are the key factors in the degradation of RhB and OFX solutions, and *OH is the major determinant in removal of MB. The process and photocatalytic mechanism on 2-C/BMO was discussed. Well absorption of visible light, effective separation of photoelectron-hole pairs and the transportation of photogenerated carriers at the interfaces of ternary semiconductor heterojunction are suggested as the key factors to enhance the photocatalytic performance of the photocatalysts.
An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. Let G be a plane graph with g(G)≥5 and χi(G) be the ...injective chromatic number of G. In this paper, we improve some known results by proving that χi(G)≤Δ+3 if Δ(G)≥35 and χi(G)≤Δ+6 for arbitrary Δ(G).
PDF
