پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شماره‌ها | 1,473 |
| تعداد مقالات | 12,039 |
| تعداد مشاهده مقاله | 22,292,573 |
| تعداد دریافت فایل اصل مقاله | 9,792,820 |
On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs | ||
| Transactions on Combinatorics | ||
| دوره 11، شماره 1، خرداد 2022، صفحه 29-43 اصل مقاله (256.34 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2021.127880.1832 | ||
| نویسنده | ||
| Alireza Mofidi* | ||
| Department of Mathematics and Computer Science, Amirkabir University of Technology (Tehran Poly- technic), Hafez Avenue, 15194, Tehran, Iran | ||
| چکیده | ||
| In this paper, we delve into studying some relations between the structure of the cycles and spanning trees of a graph through the lens of its cycle and spanning tree hypergraphs which are hypergraphs with the edge set of the graph as their vertices and the edge sets of the cycles and spanning trees as their hyperedges respectively. In particular, we investigate relations between these hypergraphs from the perspective of the VC-dimension and some important separating and covering features of hypergraph theory and amongst the results, for example show that the VC-dimension of the cycle hypergraph is less than or equal to the VC-dimension of the spanning tree hypergraph and their gap can be arbitrary large. Note that VC-dimension is an important measure of complexity and a fundamental notion in numerous fields such as extremal combinatorics, graph theory, statistics and the theory of machine learning. Also we compare the separating and covering features of the mentioned hypergraphs and for instance show that the separating number of the cycle hypergraph is less than or equal to that of the spanning tree hypergraph. These hypergraphs help us to make several connections between cycles and spanning trees of graphs and compare their complexities. | ||
| کلیدواژه‌ها | ||
| VC-dimension؛ Cycle hypergraphs of graphs؛ spanning tree hypergraphs of graphs؛ separating number؛ test cover | ||
| مراجع | ||
|
[1] R. Anstee, L. Ronyai and A. Sali, Shattering news, Graphs Combin., 18 (2002) 59–73.
[2] 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 J. Discrete Math., 32 (2018) 902–918. [3] C. Berge, Graphs and hypergraphs, Translated from the French by Edward Minieka, North-Holland Mathematical Library, 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. [4] B. Bollobas, Combinatorics: et systems, hypergraphs, families of vectors and combinatorial probability, Cambridge University Press, Cambridge, 1986. [5] N. Bousquet, S. Thomasse, VC-dimension and Erdos-Posa property, Discrete Math., 338 (2015) 2302–2317.
[6] A. Bretto, Hypergraph theory, an introduction, Mathematical Engineering, Springer, Cham, 2013.
[7] V. D. Chepoi, B. Estellon and Y. Vaxes, Covering planar graphs with a fixed number of balls, Discrete Comput. Geom., 37 (2007) 237–244. [8] K. Ch. Das, A sharp upper bound for the number of spanning trees of a graph, Graphs Combin., 23 (2007) 625–632.
[9] R. Diestel, Graph Theory, Third edition. Graduate Texts in Mathematics, 173, Springer-Verlag, Berlin, 2005.
[10] L. Feng, G. Yu, Z. Jiang and L. Ren, Sharp upper bounds for the number of spanning trees of a graph, Appl. Anal. Discrete Math., 2 (2008) 255–259. [11] G. R. Grimmett, An upper bound for the number of spanning trees of a graph, Discrete Math., 16 (1976) 323–324.
[12] S. Jukna, Extremal Combinatorics. With Applications in Computer Science, 2nd ed., Springer, Heidelberg, 2011.
[13] E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia and G. Woeginger, The VC-dimension of set systems defined by graphs, Discrete Appl. Math., 77 (1997) 237–257. [14] E. Kranakis, D. Krizanc and G. Woeginger, VC-dimensions for graphs, in: M. Nagl, editor, Graph-theoretic concepts in computer science, LNCS 1017, (1995) 1–13. [15] J. Li, W. C. Shiu and A. Chang, The number of spanning trees of a graph, Appl. Math. Lett., 23 (2010) 286–290.
[16] J. Matousek, Lectures on discrete geometry, Graduate Texts in Mathematics, 212, Springer-Verlag, New York, 2002.
[17] A. Mofidi, On some dynamical aspects of NIP theories, Arch. Math. Logic, 57 (2018) 37–71.
[18] A. Mofidi, On partial cubes, well-graded families and their duals with some applications in graphs, Discrete Appl. Math., 283 (2020) 207–230. | ||
|
آمار تعداد مشاهده مقاله: 144 تعداد دریافت فایل اصل مقاله: 203 |
||