2
$\begingroup$

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

enter image description here

enter image description here

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

$\endgroup$
11
  • 1
    $\begingroup$ 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. $\endgroup$
    – caduk
    Commented Jul 19 at 8:55
  • 1
    $\begingroup$ @caduk if center and periphery both contain n/2 vertices then there are no other vertices left? Am I right? $\endgroup$
    – Priya
    Commented Jul 19 at 8:59
  • 1
    $\begingroup$ We can have center and periphery with the same number of vertices, but lower than $n/2$ $\endgroup$
    – caduk
    Commented Jul 19 at 9:01
  • 1
    $\begingroup$ 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., $\endgroup$
    – Priya
    Commented Jul 19 at 9:14
  • 1
    $\begingroup$ 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. $\endgroup$
    – caduk
    Commented Jul 19 at 9:30

1 Answer 1

Reset to default
2
$\begingroup$

One other possible generalization would be the following:

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .