2024/10/15 by Chengli Li, Feng Liu, Li, Chengli +3
Mathematics · Computer Science · #Graph theory and applications #Graph Labeling and Dimension Problems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2410.11183
A k-cycle in a graph is a cycle of length k. A graph G of order n is called edge-pancyclic if for every integer k with 3≤ k≤ n, every edge of G lies in a k-cycle. It seems difficult to determine the minimum size f(n) of a simple edge-pancyclic graph of order n. We give lower and upper bounds on f(n), and determine the maximum diameter of such a graph. In the 3-connected case, the precise value of f(n) is determined. We also determine the minimum size of a graph of a given order with connectivity conditions in which every edge lies in a triangle.