ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION

Facta Universitatis. Series Mathematics and Informatics

article

Alireza Mofidi¹ 

[1] Department of Mathematics and Computer Science, Amirkabir University of Technology ,(Tehran Polytechnic) and Institute for research in fundamental sciences

关键词: VC-dimension;    Number of cycles;    cycle hypergraph;    cycle structure of graphs;   

DOI  :  10.22190/FUMI210301011M

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Nishu / University of Nis

【 摘 要 】

The number of the 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 and machine learning. 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 the cycles in terms of the (dual) VC-dimension of the cycle hypergraph and nullity of graph. We compute 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.

【 授权许可】

Unknown