“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 17411
School of Mathematics
  Title:   On the number of cycles of graphs and VC-dimension
  Author(s):  Alireza Mofidi
  Status:   Published
  Journal: Facta Universitatis, Series: Mathematics and Informatics
  Vol.:  37
  Year:  2022
  Pages:   121-135
  Supported by:  IPM
The number of cycles in a graph is an important well-known 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 VC-dimension 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 VC-dimension is an important notion in extremal combinatorics, graph theory, statistics, machine learning and logic. We investigate cycle hypergraph from the perspective of VC-theory, specially the celebrated Sauer-Shelah lemma, in order to give our upper and lower bounds for the number of cycles in terms of the (dual) VC-dimension of the cycle hypergraph and nullity of graph. We compute the VC-dimension 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
scroll left or right