# The G-Convexity and the G-Centroids of Composite Graphs
## 2 Definitions and Preliminary Results
### The G-Centroid Location Problem for Arbitrary Connected Graphs
This is done by adding \(r+2\) rows and columns to the \"adjacency matrix\". Creating adjacency entries that represents \(K_{r-1}\) takes \(O(r^{2})\) time. Joining \(a\) to all the vertices of \(G\) is obtained by setting 1 for all columns that correspond to the vertices of \(G\). This can be done in linear time. Similarly, joining \(b\) to all vertices ofcan be done in linear time. Joining \(c\) to \(a\) and \(b\) and to some arbitrary vertex \(d\) of \(K_{r-1}\) can be done in a constant time. Thus, the entire construction of \(G_{r}\) from \(G\) takes polynomial time. For an arbitrary connected graph \(G\), we now analyze the structure of the g-centroid of \(G_{r}\) for various values of \(r\). In what follows in this section, if the context is clear, we assume that the graph under consideration is \(G_{r}\). The following facts can easily be established. Proposition 4: Let \(G\) be a connected graph and \(G_{r}\) be defined as in Definition 3. Let \(x\) be a vertex in the copy of \(K_{r-1}\) of \(G_{r}\), then \(w(x)=\mid V(G_{r})\mid-1=r+\mid V(G)\mid+1\). The proof follows from the fact that \(N_{1}(x)\) is complete and therefore \(S_{x}=V(G_{r})-\{x\}\). Proposition 5: Let \(G\) be a connected graph and \(G_{r}\) be defined as in Definition 3. \(w(d)=\mid V(G)\mid+3\). The next proposition specifies the weight of the two vertices \(a\) and \(b\) based on the maximum clique size of \(G\). Proposition 6: Let \(G\) be a connected graph and \(G_{r}\) be defined as in Definition 3. \(w(a)=w(b)=max\{w+1,r+1\}\), where \(\omega(G)=w\) is the maximum clique size of \(G\). The following proposition determines the weight of the vertex \(c\) based on the chosen \(r\) and the maximum clique size of \(G\). Proposition 7: Let \(G\) be a connected graph and \(G_{r}\) be defined as in Definition 3. \(w(c)=max\{w+1,r-1\}\), where \(w=\omega(G)\). We now determine the weight of every vertex \(u\in V(G)\). The weight of these vertices depends on the maximum clique incident pattern of \(G\) and the chosen \(r\). Figure 1: \(G_{r}\) for a given graph \(G\). Proposition 8: _Let \(G\) be a connected graph and \(G_{r}\) be defined as in Definition 3. Let \(M_{1},M_{2},\cdots,M_{s}\) be the maximum cliques of \(G\), \(M=\cap_{i=1}^{s}M_{i}\), and \(w=\omega(G)\). Then, the following hold._  
1. _If_ \(M=\emptyset\)_, then for every_ \(u\in V(G)\)_,_ \(w(u)=\text{max {\{w+1,r+1\}}}\)_._
2. _If_ \(M\
eq\emptyset\)_, then for every_ \(u\in M\)_,_ \(w(u)=\text{max {\{w,r+1\}}}\)_. For every_ \(v\in V(G)-M\)_,_ \(w(v)=\text{max {\{w+1,r+1\}}}\)_._  
From the above propositions, for a given connected graph \(G\) and an integer \(r\) with \(2\leq r\leq\mid V(G)\mid\), we can find the weight of every vertex of \(G_{r}\). The following proposition analyze the structure of \(C_{g}(G_{r})\) for various values of \(r\). Proposition 9: _Let \(G\) be an arbitrary graph with the maximum clique size \(\omega(G)=w\). Let \(r\) be an integer such that \(2\leq r\leq w-1\). Let \(G_{r}\) be defined as in Definition 3. Then, the \(g\)-centroid of \(G_{r}\), \(C_{g}(G_{r})\)\(=V(G)\cup\{a,b,c\}\) or \(M\), depending upon whether the intersection of all the maximum cliques of \(G\) denoted by \(M\) is empty or not._  
The following two propositions relate the chosen \(r\) and the maximum clique size of \(G\). Proposition 10: _Let \(G\) be a connected graph with the maximum clique size \(\omega(G)=w\) and \(G_{r}\) be defined as in Definition 3. Let \(r\geq w+1\). Then, \(C_{g}(G_{r})=\{c\}\)._  
Proposition 11: _Let \(G\) be a connected graph with the maximum clique size \(\omega(G)=w\) and \(G_{r}\) be defined as in Definition 3. Let \(r=w\). Then, \(C_{g}(G_{r})=V(G)\cup\{a,b,c\}\), irrespective of whether \(M\) is empty or not._  
Combining all the results for \(G_{r}\), we have the following theorem. Theorem 1: _Let \(G\) be any connected graph and \(r\) be an integer such that \(2\leq r\leq n=\mid V(G)\mid\). Let \(G_{r}\) be defined as in Definition 3. Let \(\omega(G)=w\) be the maximum clique size of \(G\).