home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / math / research / 673 < prev    next >
Encoding:
Text File  |  1993-01-28  |  1.6 KB  |  36 lines
  1. Newsgroups: sci.math.research
  2. Path: sparky!uunet!math.fu-berlin.de!ira.uka.de!scsing.switch.ch!univ-lyon1.fr!ghost.dsi.unimi.it!rpi!usc!sdd.hp.com!ux1.cso.uiuc.edu!news.cso.uiuc.edu!dan
  3. From: HSNEV@ROMEO.CALTECH.EDU
  4. Subject: conjecture about graphs
  5. Mime-Version: 1.0
  6. Message-ID: <01GU0TLRH3N69ANTVT@ROMEO.CALTECH.EDU>
  7. X-Envelope-To: sci-math-research@uiuc.edu
  8. Originator: dan@symcom.math.uiuc.edu
  9. Sender: Daniel Grayson <dan@math.uiuc.edu>
  10. Content-Transfer-Encoding: 7BIT
  11. X-Submissions-To: sci-math-research@uiuc.edu
  12. Organization: University of Illinois at Urbana
  13. X-Administrivia-To: sci-math-research-request@uiuc.edu
  14. Approved: Daniel Grayson <dan@math.uiuc.edu>
  15. X-Vms-To: IN%"sci-math-research@uiuc.edu"
  16. Date: Thu, 28 Jan 1993 01:20:35 GMT
  17. Lines: 17
  18.  
  19. Def. Let G be a graph and let v be in V(G). Let S_v = bigsum d(u,v)
  20. for all u not= v ( u in V(G)). G is called self-median if 
  21. S_v = S_u for all u and v in V(G).
  22. Def. A graph G is called self-centered if every vertex is in the center.
  23. (The eccenticity of a vertex v is max d(u,v) for all u in V(G). 
  24. v is in the center if v has minimum eccentricity. It is well-know that 
  25. a tree has at most two vertices in its center.)
  26.  
  27. CONJECTURE: Every self-median graph is self-centered.
  28. Note that every vertex transitive graph is self-median. There are 
  29. examples of self-centered graphs that are not self-median, so the 
  30. above inclusion would be strict. There is no known characterization of 
  31. self-median graphs. There are non-regular self-medain graphs - 
  32. see the recent book by Buckley and Harary "Distances in Graphs" for 
  33. more information.
  34. H.S. Snevily
  35.  
  36.