20.500.12556/DKUM-51788 Cage-amalgamation graphs, a common generalization of chordal and median graphs Grafi amalgamov kletk, skupna posplošitev tetivnih in medianskih grafov V članku je vpeljan in na različne načine okarakteriziran nov razred grafov, imenovan grafi amalgamov kletk, ki je vsebovan v šibko modularnih grafih in grafih zastraženih inverzov in ki vsebuje tako medianske kot tetivne grafe. Vpeljemo tudi variacijo Hammingovega polinoma in jo uporabimo pri izpeljavi dveh enakosti drevesnega tipa za ta razred grafov, ki sta bili prej znani za tetivne in medianske grafe. Prva enakost je ▫$sum_{ige 0}, (-1)^{i}, rho_i(G)=1$▫, kjer je ▫$rho_i(G)$▫ število ▫$i$▫-regularnih Hammingovih podgrafov v grafu amalgamov kletk ▫$G$▫. A class of graphs, called cage-amalgamation graphs, that is contained in weakly modular and fiber-complemented graphs and contains median and chordal graphs, is introduced and characterized in several ways. A variation of the Hamming polynomial is also introduced and used in obtaining two tree-like equalities for these graphs, that were previously known for both chordal and median graphs. The first equality is ▫$sum_{i ge 0}(-1)^i rho_i(G) = 1$▫, where ▫$rho_i(G)$▫ is the number of ▫$i$▫-regular Hamming subgraphs in a cage-amalgamation graph ▫$G$▫. matematika teorija grafov medianski grafi tetivni grafi konveksnost amalgamacija enakosti drevesnega tipa mathematics graph theory median graphs chordal graphs convexity amalgamation tree-like equalities true false false Angleški jezik Neznan jezik Delo ni kategorizirano 2015-07-10 15:08:26 2015-07-10 15:08:26 2022-05-30 03:07:23 2019-07-11 07:28:20 2009 0 0 str. 1071-1081 no. 5 Vol. 30 2009 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 25427968 15146329 0195-6698 URN:SI:UM:DK:8YUNTMZ8 http://dx.doi.org/10.1016/j.ejc.2008.09.003 1 https://dk.um.si/Dokument.php?lang=slv&id=76348 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0