The Upper Connected Square Free Detour Number of a Graph

Abstract

For any two vertices u and v in a connected graph G = (V, E), the u - v path P is called a u - v square free path if no four vertices of P induce a square. The square free detour distance is the length of a longest u - v square free path in G. A u - v path of length is called a u - vsquare free detour. A subset S of V is called a square freedetour set if every vertex of G lies on a u - v square free detour joining a pair of vertices of S. The square free detour of G is the minimum order of its square free detour sets. A square free detour set S of G is called a minimal square free detour set if no proper subset of S is a square free detour set of G. The upper square free detour numberof G is the maximum cardinality of a minimal square free detour set of G. We introduce the upper connected square free detour number and determine the upper connected square free detour number of certain classes of graphs. Further, we investigate the bounds for it and characterize the graphs which realize these bounds. We show that there is no “Intermediate Value Theorem” for minimal connected square free detour sets.