Problem Garden

This page contains a collection of problems in graph theory, which occurred to me when I was working on related research topics.  The problems are small, but  I think they are good appetizers, to get started in these areas.

  1.  Intersection of Longest Paths Problem: In 1966, Gallai asked whether all longest paths in a connected graph share a common vertex. Counterexamples indicate that this is not true in general. However, Gallai’s question is positive for certain well-known classes of connected graphs, such as split graphs, interval graphs, circular arc graphs, outerplanar graphs, series-parallel graphs, and $2K_2$-free graphs. Is Gallai’s question true for the following families of graphs:
    • 3K_2-free
    • 2K_2 union K_1-free
    • K_2 union P_3-free
    • Line graphs, particularly, line graphs of cubic graphs (a path in the line graph $L(G)$ of  $G$ is corresponding to an open trail in the graph $G$, and in a cubic graph, an open trail is just a path)
    • P_5-free graphs
    • graphs  which do not contain forbidden pairs  for hamiltonian paths
  2.  Generalization of Intersection of Longest Paths Problem: Is it true that in a connected graph, all longest open trails have a nonempty intersection?
  3. Characterize 2-edge-connected $n$-vertex graphs which satisfy $σ_3(G)>=n$ but contain no two edge-disjoint spanning trees.
  4.  Problems on Homeomorphically Irreducible Spanning Trees
    • if every 4-connected claw-free graph has a HIST
    • if every 4-connected line graph has a HIST
    • what is the minimum toughness for a graph to have a HIST, is 2-tough enough
  5.  Characterize forbidden pairs for prism hamiltonicity