# Construction of a graph on even number of vertices with required eccentricities.

I was trying to construct a graph on an even number of vertices $$n$$ such that center and periphery contain an equal number of vertices, i.e. $$|C(G)|=|P(G)| =\frac{n}{2}$$. Till now, I was able to draw two such graphs. One is path graph $$P_4$$ and another two graphs as follows

My doubt: Are there any other graph (s) with different radius and diameter? Is there any generalized construction for the same?

• A clique with one pendant edge for each vertex seems a natural generalization. Also "center and periphery contain an equal number of vertices" is not equivalent to "$|C(G)|=|P(G)| =\frac{n}{2}$", since you can have vertices that are neither in $C(G)$ nor in $P(G)$. A more general class of such graphs: replace in my construction the complete graph with any graph of constant radius. Commented Jul 19 at 8:55
• @caduk if center and periphery both contain n/2 vertices then there are no other vertices left? Am I right? Commented Jul 19 at 8:59
• We can have center and periphery with the same number of vertices, but lower than $n/2$ Commented Jul 19 at 9:01
• yeah that is possible. That is why I have put a condition half vertices in centre and the rest of the half in the periphery., Commented Jul 19 at 9:14
• If you take a cycle graph with pendant edges for each vertex, then you have a graph with arbitrary big radius. The diameter will always be one more than the radius since peripheral vertices needs to be adjacent to some center vertices. Commented Jul 19 at 9:30

Take a graph $$G$$ on n-vertices and some integer $$r\ge 2$$. Now consider $$K_{nr}$$ and partition $$V(K_{nr})$$ into $$r$$ sets $$A_1,\ldots, A_r$$ all of size $$n$$. Also take $$r$$ copies $$G_1, \ldots, G_r$$ of $$G$$. Now for all $$i\in [r]$$ we add edges between all $$v\in A_i$$ and $$w\in G_i$$. The diameter of this constructed graph is $$3$$; all vertices in $$V(K_{nr})$$ have eccentricity $$2$$ and all vertices in $$G_1,\ldots, G_r$$ have eccentricity $$3$$. Your second example is a special case of this construction, if we pick $$G = K_2$$ and $$r = 2$$. It does not cover other cases though, like the example of taking a cycle and adding a pendant vertex to each vertex of the cycle.