Signed domination and Mycielski’s structure in graphs
RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 4, pp. 1077-1086.

Let G = (V, E) be a graph. The function f : V(G) → {−1, 1} is a signed dominating function if for every vertex v ∈ V(G), ∑xf(x)≥1. The value of ω(f)=∑xf(x) is called the weight of f. The signed domination number of G is the minimum weight of a signed dominating function of G. In this paper, we initiate the study of the signed domination numbers of Mycielski graphs and find some upper bounds for this parameter. We also calculate the signed domination number of the Mycielski graph when the underlying graph is a star, a wheel, a fan, a Dutch windmill, a cycle, a path or a complete bipartite graph.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2019109
Classification : 05C69, 05C75
Mots-clés : Signed domination number, Mycielski construction 
@article{RO_2020__54_4_1077_0,
     author = {Ghameshlou, Arezoo N. and Shaminezhad, Athena and Vatandoost, Ebrahim and Khodkar, Abdollah},
     title = {Signed domination and {Mycielski{\textquoteright}s} structure in graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1077--1086},
     publisher = {EDP-Sciences},
     volume = {54},
     number = {4},
     year = {2020},
     doi = {10.1051/ro/2019109},
     mrnumber = {4100701},
     language = {en},
     url = {https://numdam.org/articles/10.1051/ro/2019109/}
}
TY  - JOUR
AU  - Ghameshlou, Arezoo N.
AU  - Shaminezhad, Athena
AU  - Vatandoost, Ebrahim
AU  - Khodkar, Abdollah
TI  - Signed domination and Mycielski’s structure in graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2020
SP  - 1077
EP  - 1086
VL  - 54
IS  - 4
PB  - EDP-Sciences
UR  - https://numdam.org/articles/10.1051/ro/2019109/
DO  - 10.1051/ro/2019109
LA  - en
ID  - RO_2020__54_4_1077_0
ER  - 
%0 Journal Article
%A Ghameshlou, Arezoo N.
%A Shaminezhad, Athena
%A Vatandoost, Ebrahim
%A Khodkar, Abdollah
%T Signed domination and Mycielski’s structure in graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2020
%P 1077-1086
%V 54
%N 4
%I EDP-Sciences
%U https://numdam.org/articles/10.1051/ro/2019109/
%R 10.1051/ro/2019109
%G en
%F RO_2020__54_4_1077_0
Ghameshlou, Arezoo N.; Shaminezhad, Athena; Vatandoost, Ebrahim; Khodkar, Abdollah. Signed domination and Mycielski’s structure in graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 4, pp. 1077-1086. doi : 10.1051/ro/2019109. https://numdam.org/articles/10.1051/ro/2019109/

J.E. Dunbar, S.T. Hedetniemi, M.A. Henning and P.J. Slater, Signed domination in graphs. In, Signed domination in graphs. In: Vol. 1 of Graph Theory, Combinatorics and Applications. John Wiley & Sons, Inc. (1995) 311–322. | MR | Zbl

D.C. Fisher, P.A. Mckenna and E.D. Boyer, Hamiltonicity, diameter, domination, packing and biclique partitions of Mycielski’s graphs. Discrete Appl. Math. 84 (1998) 93–105. | DOI | MR | Zbl

R. Hass and T.B. Wexler, Bounds on the signed domination numbers of a graph. Discrete Math. 283 (2004) 87–92. | DOI | MR | Zbl

T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics. Marcel Deker Inc (1998). | MR | Zbl

F.T. Hu, M.Y. Sohn and J. Lee, Bondage numbers of Mycielski graphs. Bull. Malays. Math. Soc. 2 (2016) 229–245. | MR

A.P. Kazemi, Roman domination and Mycielski’s structure in graphs. Ars Combin. 106 (2012) 277–287. | MR | Zbl

D.A. Mojdeh and N. Jafari Rad, On domination and its forcing in Mycielski’s graphs. Sci. Iran. 15 (2008) 218–222. | MR | Zbl

J. Mycielski, Sur le coloriage des graphes. Colloq. Math. 3 (1955) 161–162. | DOI | MR | Zbl

S.M. Sheikholeslami, Forcing signed domination numbers in graphs. Oplooska 59 (2007) 171–179. | MR | Zbl

M.Y. Shon, J. Lee and Y.S. Kwon, Lower bounds of signed domination number of a graph. Bull. Korean Math. Soc. 41 (2004) 181–188. | DOI | MR | Zbl

D.B. West, Introduction to Graph Theory. Prentice-Hall (2000). | MR | Zbl

B. Zelinka, Signed and minus domination in bipartite graphs. Czeckoslovak Math. J. 56 (2006) 587–590. | DOI | MR | Zbl

Cité par Sources :