ON THE NUMBER OF CYCLES OF GRAPHS AND VC-DIMENSION

Alireza Mofidi

DOI Number
https://doi.org/10.22190/FUMI210301011M
First page
121
Last page
135

Abstract


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.

Keywords

VC-dimension, Number of cycles, cycle hypergraph, cycle structure of graphs

Full Text:

PDF

References


W. Ahrens: Ueber das gleichungssystem einer kirchho_schen galvanischen stromverzweigung. Math. Ann. 49 (1897) 311-324 (German).

R. E. L. Aldred and C. Thomassen: On the maximum number of cycles in a planar graph. J. Graph Theory 57 (2008) 255-264.

R. Anstee, L. Ronyai and A. Sali: Shattering news. Graphs Combin 18 (1) (2002) 59-73.

A. Arman and S. Tsaturian: The maximum number of cycles in a graph with fixed number of edges. Electron. J. Comb. 26 (2019) P4.42.

L. Beaudou, P. Dankelmann, F. Foucaud, M. A. Henning, A. Mary and A. Parreau: Bounding the order of a graph using its diameter and metric dimension: a study through tree decomposition and VC dimension. SIAM Journal on Discrete Mathematics 32 (2018) 902-918.

C. Berge: Graphs and Hypergraphs. North-Holland (translation and revision of Graphes et Hypergraphes, Dunod, 1970), 1973.

B. Bollobas: Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press, 1986.

N. Bousquet and S. Thomasse: VC-dimension and Erdos-Posa property. Discrete Math. 338 (2015) 2302-2317.

A. Bretto: Hypergraph theory, an introduction. Springer, Newyork, 2013. 10. V. D. Chepoi, B. Estellon and Y. Vaxes: Covering planar graphs with a fixed number of balls. Discrete Comput Geom 37 (2007) 237-244.

V. D. Chepoi, B. Estellon and Y. Vaxes: Covering planar graphs with a xed number

of balls. Discrete Comput Geom 37 (2007) 237{244.

Z. Dvorak, N. Morrison, J. A. Noel, S. Norin and L. Postle: Bounding the number of cycles in a graph in terms of its degree sequence. arXiv:1907.12091v1(2019).

https://oeis.org, The on-line encyclopedia of integer sequences.

S. Jukna: Extremal Combinatorics. With Applications in Computer Science, 2ed. Springer, Heidelberg, 2011.

Z. Kiraly: Maximum number of cycles and Hamiltonian cycles in sparse graphs. Tech. rep., Egervary Research Group (2009).

E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia and G.Woeginger: The VC-dimension of set systems defined by graphs. Discrete Appl. Math. 77 (3) (1997) 237-257.

E. Kranakis, D. Krizanc and G. Woeginger: VC-dimensions for graphs. in: M. Nagl, editor, Graph-theoretic concepts in computer science, LNCS 1017, 1995, pp. 1-13.

J. Matousek: Lectures on Discrete Geometry. Springer-Verlag New York, 2002.

A. Mofidi: On partial cubes, well-graded families and their duals with some applications in graphs. Discrete Appl. Math, 283 (2020) 207-230.

A. Modi: On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs. Trans. Comb. 11(1) (2022) 29-43, Doi:10.22108/TOC.2021.127880.1832.

A. Modi: On some dynamical aspects of NIP theories. Arch. Math. Logic, 57(1), (2018) 37-71.

N. Sauer: On the density of families of sets. J. Comb. Theory, Ser. A 13 (1972) 145-147.

S. Shelah: A combinatorial problem; stability and order for models and theories in infinitary languages. Pac. J. Math. 41 (1972) 247-261.




DOI: https://doi.org/10.22190/FUMI210301011M

Refbacks

  • There are currently no refbacks.




© University of Niš | Created on November, 2013
ISSN 0352-9665 (Print)
ISSN 2406-047X (Online)