Graphs whose square is panconnected

Abstract

The square of a graph G is the graph obtained from G by adding edges joining those pairs of vertices whose distance from each other in G is two. A graph is panconnected if, between any pair of distinct vertices, it contains a path of each length at least the distance between the two vertices. If G is connected, the cyclomatic number of G is defined as (G)| - (G)| + 1. Chia et al. [4] has already characterized all graphs with cyclomatic number no more than one whose square is panconnected. In this thesis, we characterize all graphs with cyclomatic number two whose square is panconnected. We show that if G has cyclomatic number three and the square of G is panconnected, then G is one of the eight families of graphs. Three of these families of graphs are generalized to three larger families of graphs. Necessary and sufficient conditions for these three larger families of graphs to have panconnected square are determined.