Weak edge triangle free detour number of a graph

Abstract

For any two vertices u and v in a connected graph G = (V, E), a u − v path P is called a u − v triangle free path if no three vertices of P induce a triangle. The triangle free detour distance D_△f(u, v) is the length of a longest u − v triangle free path in G. A u − v path of length D_△f(u, v) is called a u − v triangle free detour. A set S ⊆ V is called a weak edge triangle free detour set of G if every edge of G has both ends in S or it lies on a triangle free detour joining a pair of vertices of S. The weak edge triangle free detour number wdn_△f(G) of G is the minimum order of its weak edge triangle free detour sets and any weak edge triangle free detour set of order wdn_△f(G) is a weak edge triangle free detour basis of G. Certain properties of these concepts are studied. The weak edge triangle free detour numbers of certain classes of graphs are determined. Its relationship with the triangle free detour diameter is discussed and it is proved that for any three positive integers a, b and n of integers with 3 ≤ b ≤ n − a + 1 and a ≥ 4, there exists a connected graph G of order n with triangle free detour diameter D_△f = a and wdn_△f(G)=b. It is also proved that for any three positive integers a, b and c with 3 ≤ a ≤ b and c ≥ b + 2, there exists a connected graph G such that R_△f = a, D_△f = b and wdn_△f(G)=c.