no. 4
Global distribution center number of some graphs and an algorithm
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1217-1227

The global center is a newly proposed graph concept. For a graph G = (V(G), E(G)), a set S ⊆ V(G) is a global distribution center if every vertex v ∈ V(G)\S is adjacent to a vertex u ∈ S with |N[u] ∩ S| ≥ |N[v] ∩ (V(G)\S)|, where N(v) = {u ∈ V(G)|uv ∈ E(G)} and N[v] = N(v) ∪ {v}. The global distribution center number of a graph G is the minimum cardinality of a global distribution center of G. In this paper, we investigate the global distribution center number for special families of graphs. Furthermore, we develop a polynomial time heuristic algorithm to find the set of the global distribution center for general graphs.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018119
Classification : 05C40, 68M10, 68R10
Keywords: Network design and communication, complex networks, distribution centers, global distribution center number, trees

Durgut, Rafet 1 ; Kutucu, Hakan 1 ; Turaci, Tufan 1

1 
@article{RO_2019__53_4_1217_0,
     author = {Durgut, Rafet and Kutucu, Hakan and Turaci, Tufan},
     title = {Global distribution center number of some graphs and an algorithm},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {1217--1227},
     year = {2019},
     publisher = {EDP Sciences},
     volume = {53},
     number = {4},
     doi = {10.1051/ro/2018119},
     mrnumber = {3986374},
     zbl = {1440.05185},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2018119/}
}
TY  - JOUR
AU  - Durgut, Rafet
AU  - Kutucu, Hakan
AU  - Turaci, Tufan
TI  - Global distribution center number of some graphs and an algorithm
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 1217
EP  - 1227
VL  - 53
IS  - 4
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2018119/
DO  - 10.1051/ro/2018119
LA  - en
ID  - RO_2019__53_4_1217_0
ER  - 
%0 Journal Article
%A Durgut, Rafet
%A Kutucu, Hakan
%A Turaci, Tufan
%T Global distribution center number of some graphs and an algorithm
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 1217-1227
%V 53
%N 4
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ro/2018119/
%R 10.1051/ro/2018119
%G en
%F RO_2019__53_4_1217_0
Durgut, Rafet; Kutucu, Hakan; Turaci, Tufan. Global distribution center number of some graphs and an algorithm. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 4, pp. 1217-1227. doi: 10.1051/ro/2018119

[1] A. Aytac and Z.N. Odabas Berberler, Robustness of regular caterpillars. Int. J. Found. Comput. Sci. 28 (2017) 835–841. | MR | Zbl | DOI

[2] V. Aytac and Z.N. Berberler, Binding number and wheel related graphs. Int. J. Found. Comput. Sci. 28 (2017) 29–38. | MR | Zbl | DOI

[3] K.S. Bagga, L.W. Beineke, W.D. Goddard, M.J. Lipman and R.E. Pippert, A survey of integrity. Disc. Appl. Math. 37–38 (1992) 13–28. | MR | Zbl | DOI

[4] M.E. Berberler and Z.N. Berberler, Measuring the vulnerability in networks: a heuristic approach. Ars Comb. 135 (2017) 3–15. | MR | Zbl

[5] T. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms, 4th edition. The MIT Press, Cambridge (1990). | MR | Zbl

[6] M. Cygan, M. Pilipczuk and R. Skrekovski, Relation between randic index and average distance of trees. MATCH Commun. Math. Comput. Chem. 66 (2011) 605–612. | MR | Zbl

[7] W.J. Desormeaux, T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Distribution centers in graphs. Disc. Appl. Math. 243 (2018) 186–193. | MR | Zbl | DOI

[8] H. Frank and I.T. Frisch, Analysis and design of survivable networks. IEEE Trans. Commun. Technol. 18 (1970) 501–519. | MR | DOI

[9] J.W. Grossman, F. Harary and M. Klawe, Generalized ramsey theory for graphs, x: double star graphs. Disc. Math. 28 (1979) 247–254. | MR | Zbl | DOI

[10] I. Gutman, Distance of thorny graphs. Publ. Linstitut Math. Nouv. Ser. 63 (1998) 31–36. | MR | Zbl

[11] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundementals of domination in graphs. Advanced Topic, Marcel Dekker, Inc, New York, NY (1998). | MR | Zbl

[12] I. Mishkovski, M. Biey and L. Kocarev, Vulnerability of complex Networks. Commun. Nonlinear Sci. Numer. Simulat. 16 (2011) 341–349. | MR | Zbl | DOI

[13] M.V. Modha and K.K. Kanani, On k-cordial labeling of some graphs. Br. J. Math. Comput. Sci. 13 (2016) 1–7. | DOI

[14] S. Nazeer, S.K. Khan, I. Kousar and W. Nazeer, Radio labeling and radio number for generalized caterpillar graphs. J. Appl. Math. Inf. 34 (2016) 451–465. | MR | Zbl

Cité par Sources :