Znano je, da spektralni radij drevesa maksimalne stopnje $\Delta$ ne presega $2\sqrt{\Delta-1}$. Tudi za ravninske grafe velja sorodna zgornja meja, spektralni radij ravninskih grafov ne presega $\sqrt{8 \Delta} + 10$. Bolj splošno, če je $G$ $d$-degeneriran graf, potem je njegov spektralni radij navzgor omejen z $\sqrt{4d\Delta}$. To nas napelje k definiciji spektralno degeneriranih grafov: $G$ je spektralno $d$-degeneriran, če ima vsak podgraf $H$ grafa $G$ spektralni radij navzgor omejen z $\sqrt{d\Delta(H)}$. V tem članku pokažemo približni obrat prej predstavljenih rezultatov, namreč, da ima vsak spektralno $d$-degeneriran graf $G$ točko stopnje največ $4d\log_2(\Delta(G)/d)$ (če je le $\Delta(G) \ge 2d$). Pri tem je odvisnost zgornje meje od $\Delta$ nujno potrebna, če je le odvisnost maksimalne stopnje od $d$ subeksponentna. Pokažemo tudi, da je odločitveni problem, ali je graf $G$ sprektralno $d$-degeneriran co-NP-poln.
COBISS.SI-ID: 16410457
Vizingova domneva iz leta 1968 trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije. Ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, dokazana je tudi nova spodnja meja za produkte grafov brez induciranega ▫$K_{1,3}$▫ s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve.
COBISS.SI-ID: 16083801
V članku študiramo optimizacijske probleme, kjer nas zanima minimalna lastna vrednost nekomutativnih polinomov, dosežena na polidisku ali krogli. Predstavimo tri glavne rezultate: (1) nekomunikativen polinom je nenegativen natanko tedaj, ko ga lahko zapišemo kot vsoto uteženih hermitskih kvadratov (2) optimalno vrednost lastne vrednosti nekomutativnega polinoma je mogoče izračunati z rešitvijo enega samega semidefinitnega programa (SDP), kar je v izrazitem nasprotju s podobnim problemom v komutativnih spremenljivkah, kjer je potrebno zaporedje semidefinitnih programov in (3) dualna rešitev tega semidefinitnega programa omogoča izračun matrike in vektorja, ki definirata optimalno lastno vrednost polinoma, kar naredimo z rešitvijo končnega problema momentov, izračunom ploščate razširitve ter Gelfard-Naimark-Segal konstrukcijo. V članku tudi predstavimo izvedbo teh postopkov v okviru našega računalniškega paketa za delo z nekomutativnimi polinomi NCsostools. Predstavimo tudi več primerov, ki demonstrirajo naše rezultate.
COBISS.SI-ID: 16276569
V jeziku matematične kemije lahko Fibonaccijeve kocke definiramo kot resonančne grafe fibonacenov. Lucasove kocke tvorijo simetrizacijo Fibonaccijevih kock in se pojavijo kot resonančni grafi cikličnih polifenantrenov. V članku je dokazano, da lahko Wienerjev indeks Fibonaccijevih kock zapišemo kot vsoto produktov štirih Fibonaccijevih števil. Kot posledico lahko zapišemo zaprto formulo za Wienerjev indeks Fibonaccijevih kock. Izpeljano je tudi asimptotično obnašanje povprečne razdalje Fibonaccijevih kock. Dobljena je rodovna funkcija zaporedja urejenih Hosoyevih polinomov Fibonacijevih kock. Izpeljani so tudi paralelni rezultati za Lucasove kocke.
COBISS.SI-ID: 16309337