# The G-Convexity and the G-Centroids of Composite Graphs
## 2 Definitions and Preliminary Results
### The G-Centroid Location Problem for Arbitrary Connected Graphs  
The g-centroid location has several practical applications. One such application domain is MANET. It also has an application in measuring dissimilarities and information retrieval [5]. Due to its practical applications, it is thus necessary to devise an efficient algorithm to locate the g-centroid for an arbitrary graph. In this subsection, we outline the \(\mathcal{NP}\)-hardness of the g-centroid location algorithm. For the detailed proof, the readers may refer to our original paper [2]. If the context is clear, in what follows, by the term graph we always mean a connected graph. The following proposition specifies the structure of a g-centroid and its convexity. **Proposition 1**. : _For any connected graph \(G\), \(C_{g}(G)\) is a \(g\)-convex set of \(G\) and \(<C_{g}(G)>\) is connected._  
Based on this proposition, we have the following results. **Proposition 2**. : _For a connected graph \(G\), \(C_{g}(G)\) lies in a block of \(G\)._  
We now define the \(k\)-th neighborhood of a vertex \(u\). Let \(G=(V,E)\) be a connected graph and \(u\in V(G)\). The \(k\)-th neighborhood of \(u\), denoted by \(N_{k}(u)\) consists of all vertices in \(G\) that are at a distance \(k\) from \(u\), i.e., \(N_{k}(u)=\{v\in V\colon d(u,v)=k\}\). The next result is obvious from the definition of the \(k\)-th neighborhood of a vertex and its maximal g-convex set realizing its weight. **Proposition 3**. : _Let \(G\) be a connected graph and \(u\) be a vertex of \(G\). If \(x,y\in N_{k}(u)\cap S_{u}\), then \(d(x,y)<2k\)._  
The following corollary is immediate from Proposition 3. **Corollary 1**. : _Let \(G=(V,E)\) be a connected graph. For every vertex \(u\) in \(G\), \(N_{1}(u)\cap S_{u}\) is either empty or induces a complete subgraph of \(G\)._  
Note that for a vertex \(u\) of \(G\), \(N_{1}(u)\cap S_{u}\) may be empty.As a nice open problem it will be interesting to classify all graphs for which \(N_{1}(u)\cap S_{u}\
eq\emptyset\), for every vertex \(u\) and any arbitrary \(S_{u}\). One such class is a tree. We now outline the \(\mathcal{NP}\)-hardness of the g-centroid location algorithm. The proof is by polynomially reducing the \"clique decision\" problem to the g-centroid location problem. However, we could not establish the membership of the g-centroid location problem in \(\mathcal{NP}\)-class to establish the \(\mathcal{NP}\)-completeness. g-convexity is closely related to the clique incident pattern of the graph. We recall the definition of the \"clique decision problem\":  
Given a connected graph \(G\) and an integer \(r\) with \(2\leq r\leq n=\mid V(G)\mid\), does \(G\) has a clique of size \(r\)? The clique decision problem is one of the classical \(\mathcal{NP}\)-complete problem in graph theory. Several graph-theoretic and optimization problems were proved to be \(\mathcal{NP}\)-complete or \(\mathcal{NP}\)-hard by reducing to the clique decision problem [7]. **Definition 3**. : _For a given connected graph \(G\) and an integer \(r\) with \(2\leq r\leq n\), we construct the graph \(G_{r}\) from a copy of \(G\), \(K_{r-1}\) (the complete graph on \(r-1\) vertices) and three new vertices \(a\), \(b\), and \(c\) as follows._  
* \(V(G_{r})=V(G)\cup\{a,b,c\}\cup V(K_{r-1})\)__
* _The edge set of_ \(G_{r}\) _consists of all the edges of_ \(G\)_,_ \(K_{r-1}\)_, and the following new edges._
* _Join_ \(a\) _and_ \(b\) _to all the vertices of_ \(G\)_._
* _Join_ \(c\) _to_ \(a\) _and_ \(b\) _and to some arbitrary vertex_ \(d\) _of_ \(K_{r-1}\)_._  
For a given graph \(G\), the graph \(G_{r}\) will look as in Figure 1. Furthermore, it is easy to see that for a given graph \(G\) and a \(r\), \(2\leq r\leq n\), \(G_{r}\) can be constructed in polynomial time. We explain this polynomial-time construction now:  
We may assume that the graph is stored as an \"adjacency matrix\". To obtain \(V(G_{r})\), we need to add \(r-1\) vertices that corresponds to \(K_{r-1}\) and the three new vertices \(a\), \(b\), and \(c\).