Edge sets contained in circuits

A graphG withn vertices has propertyp(r, s) ifG contains a path of lengthr and if every such path is contained in a circuit of lengths. G. A. Dirac and C. Thomassen Math. Ann.203 (1973), 65–75] determined graphs with propertyp(r,r+1). We determine the least number of edges in a graphG in order to insure thatG has propertyp(r,s), we determine the least number of edges possible in a connected graph with propertyp(r,s) forr=1 and alls, forr=k ands=k+2 whenk=2, 3, 4, and we give bounds in other cases. Some resulting extremal graphs are determined. We also consider a generalization of propertyp(2,s) in which it is required that each pair of edges is contained in a circuit of lengths. Some cases of this last property have been treated previously by U. S. R. Murty inProof Techniques in Graph Theory, ed. F. Harary, Academic Press, New York, 1969, pp. 111–118].