# Smallest graph possessing a property

I was studying about Almost self-centered graphs.

http://link.springer.com/article/10.1007%2Fs10114-011-9628-3

My doubt is what would be the minimum number of vertices for such graphs.

My idea: I think its 4 and the graph that satisfy this condition is $P_4$ where end vertices are not in the center of $P_4$. Is my solution correct? If not, then kindly give hints or suggestions, thanks.

Definition : Almost self-centered (ASC) graphs are introduced as the graphs with exactly two non-central vertices.

NOTE : there is another class of graphs known as almost peripheral graphs. Almost peripheral (AP) graphs are introduced as graphs G with |P(G)| = |V (G)|−1 (and |C(G)| = 1). I think $P_3$ is AP graph

• Why is $P_3$ not an ASC graph? – Peter Košinár Dec 16 '13 at 1:38
• @PeterKošinár because there is another class of graphs known as almost peripheral graphs. Almost peripheral (AP) graphs are introduced as graphs G with |P(G)| = |V (G)|−1 (and |C(G)| = 1). I think $P_3$ is AP graph – monalisa Dec 16 '13 at 2:31
• What is $P(G)$ and what is $C(G)$? – bof Dec 26 '13 at 6:34
• @bof P(G) is the set of vertices having maximum eccentricity and C(G) is the center of graph containing vertices of minimum ecc – monalisa Dec 26 '13 at 8:46

## 1 Answer

Let $u \sim v \sim w$ be the path on three vertices. The vertex $v$ is the unique center, since it has eccentricity equal to 1, while the eccentricities of both $u$ and $w$ are equal to 2. Thus, the path on three vertices has precisely two non-central vertices ($u$ and $v$), which conforms to your definition of almost self-centered graphs.

• I am sorry to say that I gave some info in above comment. there is another class of graphs known as almost peripheral graphs. Almost peripheral (AP) graphs are introduced as graphs G with |P(G)| = |V (G)|−1 (and |C(G)| = 1). I think $P_3$ is AP graph. – monalisa Dec 16 '13 at 2:57
• Is there any reason $P_3$ cannot belong to both classes? – Austin Mohr Dec 16 '13 at 3:01
• that's where I am confused. In a way $P_3$ satisfying conditions of both definitions. – monalisa Dec 16 '13 at 3:07
• @monalisa There is no problem with a graph satisfying many definitions at once. The graph $P_3$ also satisfies the definition of "path" and "order 3" and "$(1,2)$-regular". Interesting graphs have many properties. – Austin Mohr Dec 16 '13 at 3:09
• sir is it possible to construct an AP graph on 4 vertices where radius = 2. I feel that the its possible to get an AP graph on 4 vertices where radius =1 only. – monalisa Dec 16 '13 at 4:32