Archive for November, 2009

One of the reasons I find graph theory so interesting is that one can ask so basic and fundamental questions that are extremely difficult to answer.  Here is one such problem.

It is easy to see that any pair of maximum length paths in a connected graph should share a vertex. Otherwise, we can get a longer path contradicting the maximality.  The natural question that arises is what can we say about three longest paths? What about k maximal paths? Do all of them share a vertex?

Zamfirescu and Skupien  show that for k \ge 7 this need not be the case.

Balister, Gyori, Lehel and Schelp show that for interval graphs and circular arc graphs, all paths do have non-empty intersection.

Recently, Maria Axenovich  shows that any 3 longest paths in outerplanar graphs have a common vertex.

It would be interesting to look at planar graphs now that outerplanar graphs are known.


Read Full Post »


Hi, I am Narayanan. I plan to write about open problems in graph theory and related topics that I happen to come across.

Read Full Post »