Research article

Global distribution center number of some graphs and an algorithm

¹ Department of Computer Engineering, Faculty of Engineering, Karabuk University, 78050 Karabuk, Turkey
² Department of Mathematics, Faculty of Science, Karabuk University, 78050 Karabuk, Turkey

^* Corresponding author: tufanturaci@karabuk.edu.tr

Received: 13 June 2018
Accepted: 9 December 2018

Abstract

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.