351 KB24 KB200820252016Stevanović, Draganletnik:11številka:2str. 415-423COBISSID:1538772420ISSN:1855-3966URN:URN:NBN:SI:doc-Z17NLJH9enUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaadjacency matrixeigenvectorlastni vektorjimatrika sosednostiWilfov problemWilf's problemOn plus/minus 1 eigenvectors of graphs|While discussing his spectral bound on the independence number of a graph, Herbert Wilf asked back in 1986 what kind of a graph admits an eigenvector consisting solely of ?$\pm 1$? entries? We prove that Wilf's problem is NP-complete, but also that the set of graphs having a ?$\pm 1$? eigenvector is quite rich, being closed under a number of different graph compositionsKo je obravnaval svojo spektralno mejo za neodvisnostno število grafa, je Herbert Wilf leta 1986 zastavil vprašanje, kakšna vrsta grafa dopušča lastni vektor, ki sestoji samo iz ?$\pm 1$? komponent? Dokažemo, da je Wilfov problem NP-poln, pa tudi, da je množica grafov, ki imajo ?$\pm 1$? lastni vektor precej bogata, saj je zaprta za številne različne kompozicije grafovTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije