Subgraphs where every pair of edges is in a short cycle
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
Erdös and Duke[1] showed that for a graph \( G\) on \( n\) vertices and \( \alpha n^2\) edges, there is a subgraph \( G'\) with \( c\alpha^3 n^2 \) edges with the property that every two edges of \( G'\) lie together on a cycle of length at most six in \( G'\), and , if two edges of \( G'\) have a common vertex they are on a cycle of length four in \( G'\). In a subsequent paper[2] together with Rödl, they proved that for a graph \( G\) on \( n\) vertices and \( n^{2\beta}\) edges, there is a subgraph \( G'\) with \( c n^{25\beta} \) edges with the property that every two edges of \( G'\) lie together on a cycle of length at most six in \( G'\), and, if two edges of \( G'\) have a common vertex, they are on a cycle of length four in \( G'\). The following questions remain unresolved:
Problem
For any graph \(G\) on \(n\) vertices and \( n^{2\beta}\) edges, is it true that there is a subgraph \(G'\) with \(c n^{23\beta} \) edges with the property that every two edges of \(G'\) lie together on a cycle of length at most six in \(G'\), and, if two edges of \(G'\) have a common vertex, they are on a cycle of length four in \(G'\)?In [2] it was shown that "if two edges of \( G'\) have a common vertex, they are on a cycle of length four in \( G'\)" is not required, then the answer to the above question is affirmative.
Problem
For any graph \(G\) on \(n\) vertices and \( n^{2\beta}\) edges, is it true that there is a subgraph \(G'\) with \(c n^{22\beta} \) edges with the property that every two edges of \(G'\) lie together on a cycle of length at most eight in \(G'\)?In [2], it was shown that there is a subgraph \( G'\) of the above graph \( G\) with \( c n^{22\beta} \) edges with the property that every two edges of \( G'\) lie together on a cycle of length at most twelve in \( G'\).
Bibliography  

1  R. Duke and P. Erdös. Subgraphs in which each pair of edges lies in a short common cycle, Proceedings of the thirteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1982), Congr. Numer. 35 (1982), 253260.

2  R. Duke, P. Erdös and V. Rödl. More results on subgraphs with many short cycles. Proceedings of the fifteenth Southeastern conference on combinatorics, graph theory and computing (Baton Rouge, La., 1984), Congr. Numer. 43 (1984), 295300.
