“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
Paper IPM / M / 17411  


Abstract:  
The number of cycles in a graph is an important wellknown parameter in graph theory and there are a lot of investigations carried out in the literature for finding suitable bounds for it. In this paper, we delve into studying this parameter and the cycle structure of graphs through the lens of the cycle hypergraphs and VCdimension and find some new bounds for it, where the cycle hypergraph of a graph is a hypergraph with the edges of the graph as its vertices and the edge sets of the cycles as its hyperedges respectively. Note that VCdimension is an important notion in extremal combinatorics, graph theory, statistics, machine learning and logic. We investigate cycle hypergraph from the perspective of VCtheory, specially the celebrated SauerShelah lemma, in order to give our upper and lower bounds for the number of cycles in terms of the (dual) VCdimension of the cycle hypergraph and nullity of graph. We compute the VCdimension and the mentioned bounds in some graph classes and also show that in certain classes, our bounds are sharper than many previous ones in the literature.
Download TeX format 

back to top 