About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Cichacz, Sylwia ; Dzúrik, Martin
Combinatorial spectra using polynomials. (English). Archivum Mathematicum, vol. 61 (2025), issue 4, pp. 151-165
MSC: 05C12, 05C15, 05C25, 05C40 | MR 501440 | Zbl 08162261 | DOI: 10.5817/AM2025-4-151
Keywords:
Hamiltonian spectra; combinatorial spectra; domination; 1-2-3 labeling; antimagic; graph; graph theory; coloring
Summary:
In this paper, we would like to introduce some new methods for studying magic type-colorings of graphs or domination of graphs, based on the combinatorial spectrum on polynomial rings. We hope that this concept will be potentially useful for the graph theorists.
References:
[1] Addario-Berry, L., Dalal, K., McDiarmid, C., Reed, B.A., Thomason, A.: Vertex-colouring edge-weightings. Combinatorica 27 (2007), 1–12. DOI 10.1007/s00493-007-0041-6 | MR 2310785
[2] Addario-Berry, L., Dalal, K., Reed, B.A.: Degree constrainted subgraphs. Discrete Appl. Math. 156 (2008), 1168–1174. DOI 10.1016/j.dam.2007.05.059 | MR 2404230
[3] Aigner, M., Triesch, E.: Irregular assignments of trees and forests. SIAM J. Discrete Math. 3 (1990), no. 4, 439–449. DOI 10.1137/0403038
[4] Alon, N.: Combinatorial nullstellensatz. Combin. Probab. Comput. 8 (1999), 7–29. DOI 10.1017/S0963548398003411
[5] Alon, N., Kaplan, G., Lev, A., Roditty, Y., Yuster, R.: Dence graphs are antimagic. J. Graph Theory 47 (2004), 297–309. DOI 10.1002/jgt.20027 | MR 2096791
[6] Amar, D., Togni, O.: Irregularity strength of trees. Discrete Math. 190 (1998), no. 1, 15–38. DOI 10.1016/S0012-365X(98)00112-5
[7] Chartrand, G., Jacobson, M.S., Lehel, J., Oellermann, O.R., Ruiz, S., Saba, F.: Irregular networks. Congr. Numer. 64 (1988), 187–192.
[8] Chartrand, G., Thomas, T., Zhang, P.: A New Look at Hamiltonian Walks. Bull. Inst. Combin. Appl. 42 (2004), 37–52. MR 2082480
[9] Dzúrik, M.: An upper bound of a generalized upper Hamiltonian number of a graph. Arch. Math. (Brno) 57 (2021), 299–311. DOI 10.5817/AM2021-5-299 | MR 4346115
[10] Dzúrik, M.: Combinatorial spectra of graphs. arXiv preprint arXiv:2311.11682 (2023).
[11] Goodman, S.E., Hedetniemi, S.T.: On Hamiltonian walks in graphs. SIAM J. Comput. 3 (1974), 214–221. DOI 10.1137/0203017 | Zbl 0269.05113
[12] Kalkowski, M., Karoński, M., Pfender, F.: Vertex-coloring edge-weightings: Towards the 1-2-3-conjecture.
[13] Kalkowski, M., Karoński, M., Pfender, F.: A new upper bound for the irregularity strength of graphs. SIAM J. Discrete Math. 25 (2011), no. 3, 1319–1321. DOI 10.1137/090774112 | MR 2837601
[14] Karoński, M., Łuczak, T., Thomason, A.: Edge weights and vertex colours. J. Combin. Theory Ser. B 91 (2004), 151–157. DOI 10.1016/j.jctb.2003.12.001 | MR 2047539
[15] Keusch, R.: Vertex-Coloring Graphs with 4-Edge-Weightings. Combinatorica 43 (2023), 651–658. DOI 10.1007/s00493-023-00027-6 | MR 4630471
[16] Keusch, R.: A solution to the 1-2-3 conjecture. J. Combin. Theory Ser. B 166 (2024), 183–202. DOI 10.1016/j.jctb.2024.01.002 | MR 4695633
[17] ReVelle, C.S.: Can you protect the Roman Empire?. Johns Hopkins Magazine 49 (1997), 40.
[18] Ringel, G., Hartsfield, N.: Pearls in Graph Theory. Academic Press, 1994.
[19] Roushini Leely Pushpam, P., Malini Mai, T.N.M.: Edge Roman domination in graphs. J. Combin. Math. Combin. Comput. 69 (2009), 175–182. MR 2517318
[20] Wang, T., Yu, Q.: On vertex-coloring 13-edge-weighting. Front. Math. China 3 (2008), 581–587. DOI 10.1007/s11464-008-0041-x | MR 2456862
[21] Zhu, Xuding, Balakrishnan, R.: Combinatorial Nullstellensatz With Applications to Graph Colouring. Taylor and Francis, 2022.
Partner of
EuDML logo