Abstract
In 1966 T. Gallai asked whether connected graphs with empty intersection of their longest paths do or do not exist. After examples of such graphs were found, the question was extended to graphs of higher connectivity, and to cycles instead of paths. Examples being again found, for connectivity up to 3, the question has been asked whether there exist large families of graphs without Gallai's property. The family of grid graphs, a special kind of graphs embedded in the planar square lattice , has been shown by B. Menke to contain no graph enjoying Gallai's property. In this paper we find several examples of graphs embedded in and enjoying that property with respect to both paths and cycles.