آمار
| تعداد نشریات | 6 |
| تعداد شماره‌ها | 129 |
| تعداد مقالات | 1,624 |
| تعداد مشاهده مقاله | 1,871,100 |
| تعداد دریافت فایل اصل مقاله | 1,731,224 |
Wiener Polarity Responses and Triangle Coverage | ||
| Communications in Combinatorics and Optimization | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 25 مهر 1405 اصل مقاله (569.41 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2026.31745.2953 | ||
| نویسنده | ||
| Kushal Cerlakola* | ||
| Montgomery High School, New Jersey, USA | ||
| چکیده | ||
| The Wiener polarity index W_p(G) counts unordered pairs of vertices at distance three. We study subdivisions in which each edge e of a connected simple graph receives an edge-dependent number a_e=>1 of new vertices. We obtain an exact formula for the resulting Wiener polarity index and then compare the ordinary subdivision with subdivisions in which a chosen set of edges receives one additional vertex. After removing a linear term, the change in W_p is exactly the number of triangles met by the chosen edges. This identifies the subdivision response with the coverage function of the triangle hypergraph. We use this identity to recover triangle edge sets from small responses, derive a cubic multilinear representation, and formulate fixed subdivision budgets as a maximum-coverage problem. The resulting maximization problem is NP-hard even for graphs with a universal vertex and diameter two, while a greedy rule gives the standard submodular approximation guarantee. Finally, we study a bivariate response polynomial, derive a general union formula, and obtain exact factorizations and sharp budget bounds for edge-disjoint triangles and book graphs. | ||
| کلیدواژه‌ها | ||
| Wiener polarity index؛ nonuniform subdivision؛ triangle coverage؛ combinatorial optimization؛ response polynomial | ||
| مراجع | ||
|
[1] N. Apollonio and B. Simeone, The maximum vertex coverage problem on bipartite graphs, Discrete Appl. Math. 165 (2014), 37–48. https://doi.org/10.1016/j.dam.2013.05.015
[2] A. Behmaram, H. Yousefi-Azari, and A.R. Ashrafi, Wiener polarity index of fullerenes and hexagonal systems, Appl. Math. Lett. 25 (2012), no. 10, 1510–1513. https://doi.org/10.1016/j.aml.2012.01.006
[3] H. Deng and H. Xiao, The Wiener polarity index of molecular graphs of alkanes with a given number of methyl groups, J. Serbian Chem. Soc. 75 (2010), no. 10, 1405–1412. https://doi.org/10.2298/JSC100320114D
[4] P. Erdös, T. Gallai, and Z. Tuza, Covering and independence in triangle structures, Discrete Math. 150 (1996), no. 1-3, 89–101. https://doi.org/10.1016/0012-365X(95)00178-Y
[5] M. Faghani, A.R. Ashrafi, and O. Ori, Remarks on the Wiener polarity index of some graph operations, J. Appl. Math. & Informatics 30 (2012), 353–364
[6] I. Gutman and K.C. Das, The first Zagreb index 30 years after, MATCH Commun. Math. Comput. Chem. 50 (2004), no. 1, 83–92.
[7] H. Hosoya, On some counting polynomials in chemistry, Discrete Appl. Math. 19 (1988), no. 1-3, 239–257. https://doi.org/10.1016/0166-218X(88)90017-0
[8] A. Ilić and M. Ilić, Generalizations of Wiener polarity index and terminal Wiener index, Graphs Combin. 29 (2013), no. 5, 1403–1416. https://doi.org/10.1007/s00373-012-1215-6
[9] G.L. Nemhauser, L.A. Wolsey, and M.L. Fisher, An analysis of approximations for maximizing submodular set functions-I, Math. Program. 14 (1978), 265–294. https://doi.org/10.1007/BF01588971
[10] J. Preen and A. Murray, Bivariate domination polynomial, J. Combin. Math. Combin. Comput. 111 (2019), 39–52. [11] N. Tratnik, Formula for calculating the Wiener polarity index with applications to benzenoid graphs and phenylenes, J. Math. Chem. 57 (2019), 370–383. https://doi.org/10.1007/s10910-018-0957-7 [12] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (1947), no. 1, 17–20. https://doi.org/10.1021/ja01193a005 | ||
|
آمار تعداد مشاهده مقاله: 6 تعداد دریافت فایل اصل مقاله: 1 |
||