Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $G$ is 2 - self centered graph. then how to prove that $G$ has at least $2n - 5$ edges? where $n\geq 5$.

I started by assuming if number of edges $\mid E\mid\leq 2n-6$ then there exist a vertex say $u$ such that $deg = 2$ otherwise if no such vertex exists then

$\mid E\mid\geq \frac{3n}{2}>2n-5$ (I am stucked here. How to prove this. Sincerely thanks for giving me time.)

share|improve this question
1  
Also posted to mathoverflow.net, where it ought to be closed sometime soon. So: what's a 2-self centered graph? –  Gerry Myerson May 15 '12 at 6:01
    
It probably means a self-centered graph (diameter=radius) of radius 2. –  hardmath May 15 '12 at 10:32
    
Since there are 2-self-centered graphs of arbitrarily large n, you will not be able to prove $\frac{3n}{2} \gt 2n-5$. –  hardmath May 16 '12 at 17:14
add comment

2 Answers

I take it $n$ is the number of vertices. You might be interested in http://mathoverflow.net/questions/32301/examples-of-self-centered-graphs-with-large-radius. Among the things you'll find there is a link to a complete list of all self-centered graphs with diameter 2 that have minimum number of edges, and a link to a survey paper by Fred Buckley.

share|improve this answer
add comment

i strongly recommend you to refere the following paper: Akiyama. j., Ando.K and Davis.D., Miscellaneous properties of equi eccentric graph in Convexity and Graph Theory. Proc. Conf. in Haifa Isreal-1981.

share|improve this answer
1  
Would you explain why this paper is useful for the Question? Answers are generally expected to address the Question being asked. –  hardmath May 15 '12 at 10:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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