Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
SLO
Login
Search
Browsing
Upload document
Statistics
RUP
FAMNIT - Faculty of Mathematics, Science and Information Technologies
FHŠ - Faculty of Humanities
FM - Faculty of Management
FTŠ Turistica - Turistica – College of Tourism Portorož
FVZ - Faculty of Health Sciences
IAM - Andrej Marušič Institute
PEF - Faculty of Education
UPR - University of Primorska
ZUP - University of Primorska Press
COBISS
University of Primorska, University Library - all departments
First page
/
Show document
Show document
A-
|
A+
|
Print
Title:
On [plus/minus] 1 eigenvectors of graphs
Authors:
ID
Stevanović, Dragan
(Author)
Files:
RAZ_Stevanovic_Dragan_i2016.pdf
(325,02 KB)
MD5: BDF6848483772450D3FD922B3E1EB605
Language:
English
Work type:
Unknown
Typology:
1.01 - Original Scientific Article
Organization:
ZUP - University of Primorska Press
Abstract:
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 compositions.
Keywords:
eigenvector
,
adjacency matrix
,
Wilf's problem
Year of publishing:
2016
Number of pages:
str. 415-423
Numbering:
Vol. 11, no. 2
PID:
20.500.12556/RUP-17622
UDC:
519.17
ISSN on article:
1855-3966
COBISS.SI-ID:
1538772420
Publication date in RUP:
03.01.2022
Views:
735
Downloads:
26
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Average score:
(0 votes)
Your score:
Voting is allowed only for
logged in
users.
Share:
Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.
Record is a part of a journal
Title:
Ars mathematica contemporanea
Publisher:
Društvo matematikov, fizikov in astronomov, Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
ISSN:
1855-3966
COBISS.SI-ID:
239049984
Secondary language
Language:
Slovenian
Title:
O plus/minus 1 lastnih vektorjih grafov
Abstract:
Ko 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 grafov.
Keywords:
lastni vektorji
,
matrika sosednosti
,
Wilfov problem
Comments
Leave comment
You must
log in
to leave a comment.
Comments (0)
0 - 0 / 0
There are no comments!
Back
