Bigeodetic graphs (Q1110539)

Geodetic graph is a graph in which every pair of vertices has a unique distance path (the path of minimum length) between them. By relaxing the condition of uniqueness of distance path to at most two distance paths between every pair of vertices, the bigeodetic graph is defined. It is clear that bigeodetic graph is a generalization of geodetic graph and interval-regular graph. In section 2 of this paper the authors describe the structure for a separable graph to be bigeodetic; In Section 3 two necessary and sufficient conditions for a graph to be bigeodetic are given, and other properties of bigeodetic graph are presented; In the last section various bigeodetic graphs are constructed, such as planar bigeodetic block with given girth g and diameter d (d\(\geq \lfloor g/2\rfloor)\), Hamiltonian and Eulerian or non-Hamiltonian and non-Eulerian, and perfect bigeodetic blocks with given diameter \(d\geq 3\). All bigeodetic graphs constructed in this paper are of connectivity 2, the problem of constructing higher connectivity or extremal bigeodetic graphs will be interesting.