2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why is $P_3$ not an ASC graph? $\endgroup$ – Peter Košinár Dec 16 '13 at 1:38
  • $\begingroup$ @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 $\endgroup$ – monalisa Dec 16 '13 at 2:31
  • 1
    $\begingroup$ What is $P(G)$ and what is $C(G)$? $\endgroup$ – bof Dec 26 '13 at 6:34
  • $\begingroup$ @bof P(G) is the set of vertices having maximum eccentricity and C(G) is the center of graph containing vertices of minimum ecc $\endgroup$ – monalisa Dec 26 '13 at 8:46
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – monalisa Dec 16 '13 at 2:57
  • $\begingroup$ Is there any reason $P_3$ cannot belong to both classes? $\endgroup$ – Austin Mohr Dec 16 '13 at 3:01
  • $\begingroup$ that's where I am confused. In a way $P_3$ satisfying conditions of both definitions. $\endgroup$ – monalisa Dec 16 '13 at 3:07
  • 1
    $\begingroup$ @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. $\endgroup$ – Austin Mohr Dec 16 '13 at 3:09
  • $\begingroup$ 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. $\endgroup$ – monalisa Dec 16 '13 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.