آمار
| تعداد نشریات | 6 |
| تعداد شماره‌ها | 131 |
| تعداد مقالات | 1,631 |
| تعداد مشاهده مقاله | 1,879,854 |
| تعداد دریافت فایل اصل مقاله | 1,741,188 |
A note on the Independence Polynomial of 3-Regular 2-Connected Planar Graphs Maximizing Triangular Elements | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 11 مهر 1405 اصل مقاله (508.94 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.30571.2538 | ||
| نویسندگان | ||
| Nakshee Mehta؛ S. Veeramani* | ||
| Department of Mathematics, School of Advanced Sciences, Vellore Institute of Technology, Vellore - 632 014, Tamil Nadu, India | ||
| چکیده | ||
| We establish a sharp upper bound on the number of triangles in 3-regular planar graphs. To demonstrate the tightness of this bound, we construct a finite family of 3-regular, 2-connected planar graphs that attain it, and we provide a complete characterization of the resulting extremal structures. Building on this characterization, we derive closed-form expressions for the independence polynomials of these extremal graphs. Together, these results establish an explicit connection between extremal tri- angle configurations in 3-regular planar graphs and the algebraic structure encoded in their independence polynomials, offering new insight into how local combinatorial extremality is reflected in global algebraic invariants. | ||
| کلیدواژه‌ها | ||
| Regular graphs؛ Graph indices؛ Planar graphs؛ Independence polynomial؛ connectivity | ||
| مراجع | ||
|
[1] V. Andova, F. Kardoš, and R. Škrekovski, Mathematical aspects of fullerenes, Ars Math. Contemp. 11 (2016), no. 2, 353–379. https://doi.org/10.26493/1855-3974.834.b02
[2] J.L. Arocha, Propriedades del polinomio independiente de un grafo, Revista Ciencias Matematicas 5 (1984), no. 3, 103–110.
[3] G. Chartrand and P. Zhang, A First Course in Graph Theory, Courier Corporation, 2013.
[4] H. Chen, X. Liu, and J. Shen, Matching polynomials and independence polynomials of benzenoid chains, MATCH Commun. Math. Comput. Chem 92 (2024), no. 3, 779–809. https://doi.org/10.46793/match.92-3.779C
[5] D.C. Fisher, Lower bounds on the number of triangles in a graph, J. Graph Theory 13 (1989), no. 4, 505–512. https://doi.org/10.1002/jgt.3190130411
[6] I. Gutman and F. Harary, Generalizations of the matching polynomial, Util. Math. 24 (1983), no. 1, 97–106.
[7] C. Hoede and X. Li, Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994), no. 1-3, 219–228. https://doi.org/10.1016/0012-365X(94)90163-5
[8] H. Hosoya, The topological index Z before and after 1971, Internet Electron. J. Mol. Des. 1 (2002), no. 9, 428–442.
[9] M. Jerrum, Two-dimensional monomer-dimer systems are computationally intractable, J. Stat. Phys. 48 (1987), no. 1, 121–134.
[10] P. Keevash and B. Sudakov, Packing triangles in a graph and its complement, J. Graph Theory 47 (2004), no. 3, 203–216. https://doi.org/10.1002/jgt.20031
[11] M.N. Kolountzakis, G.L. Miller, R. Peng, and C.E. Tsourakakis, Efficient triangle counting in large graphs via degree-based vertex partitioning, Internet Mathematics 8 (2012), no. 1-2, 161–185. https://doi.org/10.1080/15427951.2012.625260
[12] V.E. Levit and E. Mandrescu, The independence polynomial of a graph-A survey, vol. 233254, Aristotle Univ. Thessaloniki Thessaloniki, 2005, pp. 231–252.
[13] N. Mehta and S. Veeramani, A note on the independence polynomial of 3-regular 2-connected planar graphs, Boletim da Sociedade Paranaense de Matemática 44 (2026), no. 17, 1–28. https://doi.org/10.5269/bspm.82353
[14] R.E. Merrifield and H.E. Simmons, Topological Methods in Chemistry, Elsevier, 1989.
[15] A. Miličević, S. Nikolić, D. Plavšić, and N. Trinajstić, On the Hosoya Z index of general graphs, Internet Electron. J. Mol. Des. 2 (2003), no. 3, 160–178.
[16] H. Prodinger and R.F. Tichy, Fibonacci numbers of graphs, Fibonacci Quart. 20 (1982), no. 1, 16–21. https://doi.org/10.1080/00150517.1982.12430021
[17] J.S. Provan and M.O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected, SIAM J. Comput. 12 (1983), no. 4, 777–788. https://doi.org/10.1137/0212053
[18] M. Startek, A. W loch, and I. W loch, Fibonacci numbers and Lucas numbers in graphs, Discrete Appl. Math. 157 (2009), no. 4, 864–868. https://doi.org/10.1016/j.dam.2008.08.028
[19] S. Suri and S. Vassilvitskii, Counting triangles and the curse of the last reducer, Proceedings of the 20th international conference on World wide web, 2011, pp. 607–614.
[20] A. Vesel, Linear algorithms for the Hosoya index and Hosoya matrix of a tree, Mathematics 9 (2021), no. 2, 130–142. https://doi.org/10.3390/math9020142 | ||
|
آمار تعداد مشاهده مقاله: 55 تعداد دریافت فایل اصل مقاله: 21 |
||