485 KB45 KB205 KB3 KB2025Imrich, WilfriedKalinowski, RafałPilśniak, Monikaštevilka:1, article p1.06letnik:8str. 1-17DOI:10.26493/2590-9770.1701.10eISSN:2590-9770COBISSID_HOST:285591811URN:URN:NBN:SI:doc-9Q5KSCI1enFakulteta za matematiko, naravoslovje in informacijske tehnologijeThe art of discrete and applied mathematicsalgorithmsalgoritmidevesahierarchical products of graphshierarhični produkti grafovprafaktorizacijeprime factorizationstreesHierarchical product graphs and their prime factorization|The hierarchical and the generalized hierarchical product of graphs, together with their multiary and rooted versions, are variants of the Cartesian product. They are not commutative, and only the rooted versions are associative. We prove that finite connected graphs have unique prime factorizations with respect to the rooted hierarchical product, the multiary hierarchical product, and the rooted generalized hierarchical product. For the generalized hierarchical product, we disprove a claim about unique prime factorization by Anderson, Guob, Tenney, and Wash from 2017. We also describe the interrelation between the automorphism groups of connected graphs with the groups of their prime factors in the cases of unique prime factorization, and in the case of the standard prime factorization with respect to the hierarchical product. For finite trees, we show that their prime factors can be computed in subquadratic timeHierarhični in posplošeni hierarhični produkt grafov, skupaj z njunimi večstranskimi in korenskimi različicami, sta različici kartezičnega produkta. Nista komutativna, in samo korenske različice so asociativne. Dokažemo, da imajo končni povezani grafi enolične prafaktorizacije glede na korenski hierarhični produkt, večstranski hierarhični produkt in korenski posplošeni hierarhični produkt. Za posplošeni hierarhični produkt ovržemo trditev Andersona, Gua, Tenneyja in Washa o enolični prafaktorizaciji iz leta 2017. Opišemo tudi medsebojno razmerje med grupami avtomorfizmov povezanih grafov in grupami njihovih prafaktorjev v primerih enolične in standardne prafaktorizacije glede na hierarhični produkt. Za končna drevesa pokažemo, da je njihove prafaktorje mogoče izračunati v subkvadratnem časuTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije