384 KB30 KB200820252018Hou, JianfengZeng, Qinghouštevilka:1letnik:15str. 147-160COBISSID:18485593ISSN:1855-3966URN:URN:NBN:SI:doc-48YX15AGenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneagrafimaksimalni prerezparticijaMaximum cuts of graphs with forbidden cycles|Za graf ?$G$?, naj ?$f(G)$? označuje maksimalno število povezav v dvodelnem podgrafu grafa ?$G$?. Za celo število ?$m \ge 1$? in za množico ?$\mathcal{H}$? grafov, naj ?$f(m, \mathcal{H})$? označuje minimalno možno kardinalnost ?$f(G)$?, ko ?$G$? preteče vse grafe z ?$m$? povezavami, ki ne vsebujejo nobenega člana množice ?$\mathcal{H}$? kot podgrafa. Še posebej, za dani graf ?$H$?, enostavno pišemo ?$f(m, H)$?, za ?$f(m, \mathcal{H})$?, ko je ?$\mathcal{H} = \{H\}$?. Naj bo ?$r > 4$? fiksno sodo celo število. Alon in drugi (2003) so postavili domnevo, da obstaja pozitivna konstanta ?$c(r)$?, za katero je ?$f(m, C_{r-1}) \ge m/2 + c(r)m^{r/(r+1)}$? za vse ?$m$?. V tem članku pokažemo, da je ?$f(m, C_{r-1}) \ge m/2 + c(r)(m^r \log^4 m)^{1/(r+2)}$? za neko pozitivno konstanto ?$c(r)$? in za vse ?$m$?. Za poljubno določeno celo število ?$s \ge 2$? študiramo tudi funkcijo ?$f(m, \mathcal{H})$? za ?$\mathcal{H} = \{K_{2,s}, C_5\}$? in ?$\mathcal{H} = \{C_4, C_5,\dots , C_{r-1}\}$?, kar oboje izboljšuje rezultat Alona in drugihTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije