| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 3 / 3
First pagePrevious page1Next pageLast page
1.
Connectivity of Fibonacci cubes, Lucas cubes, and generalized cubes
Jernej Azarija, Sandi Klavžar, Jaehun Lee, Yoomi Rho, 2015, original scientific article

Abstract: If ▫$f$▫ is a binary word and ▫$d$▫ a positive integer, then the generalized Fibonacci cube ▫$Q_d(f)$▫ is the graph obtained from the ▫$d$▫-cube ▫$Q_d$▫ by removing all the vertices that contain ▫$f$▫ as a factor, while the generalized Lucas cube ▫$Q_d(\stackrel{\leftharpoondown}{f})$▫ is the graph obtained from ▫$Q_d$▫ by removing all the vertices that have a circulation containing ▫$f$▫ as a factor. The Fibonacci cube ▫$\Gamma_d$▫ and the Lucas cube ▫$\Lambda_d$▫ are the graphs ▫$Q_d({11})$▫ and ▫$Q_d(\stackrel{\leftharpoondown}{11})$▫, respectively. It is proved that the connectivity and the edge-connectivity of ▫$\Gamma_d$▫ as well as of ▫$\Lambda_d$▫ are equal to ▫$\left\lfloor \frac{d+2}{3}\right\rfloor$▫. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all ▫$f$▫ and all ▫$d \le9$▫.
Keywords: Fibonacci cube, Lucas cube, generalized Fibonacci cube, generalized Lucas cube, connectivity, combinatorics on words
Published: 10.07.2017; Views: 505; Downloads: 104
.pdf Full text (740,04 KB)
This document has many files! More...

2.
Nonrepetitive colorings of trees
Boštjan Brešar, J. Grytczuk, Sandi Klavžar, S. Niwczyk, Iztok Peterin, 2007, original scientific article

Abstract: Barvanje vozlišč grafa ▫$G$▫ je neponavljajoče, če nobena pot v ▫$G$▫ ne tvori zaporedja sestavljenega iz dveh identičnih blokov. Najmanjše število barv, ki jih potrebujemo za tako barvanje, je Thuejevo kromatično število, označimo ga s ▫$pi(G)$▫. Slavni Thuejev izrek trdi, da je ▫$pi(P) = 3$▫ za vsako pot ▫$P$▫ z vsaj štirimi vozlišči. V članku študiramo Thuejevo kromatično število na drevesih. Glede na to,da je v tem razredu ▫$pi(T)$▫ omejeno s 4, je naš namen opisati 4-kromatična drevesa. V posebnem obravnavamo 4-kritična drevesa, ki so minimalna glede na to lastnost. Čeprav obstaja mnogo dreves ▫$T$▫ s ▫$pi(T) = 4$▫, pokažemo, da ima vsako od njih primerno veliko subdivizijo ▫$H$▫, tako da je ▫$pi(H)=3$▫. Dokaz se opira na Thuejeva zaporedja z dodatnimi lastnostmi, ki vključujejo palindromske besede. Obravnavamo tudi neponavljajoča barvanja povezav na drevesih. S podobnimi argumenti dokažemo, da ima vsako drevo subdivizijo, ki jo lahko po povezavah pobarvamo z največ ▫$Delta +1$▫ barvami brez ponavljanja na poteh.
Keywords: kombinatorika na besedah, neponavljajoče zaporedje, Thuejevo kromatično število, drevo, palindrom, combinatorics on words, nonrepetitive sequence, Thue chromatic number, tree, palindrome
Published: 10.07.2015; Views: 596; Downloads: 72
URL Link to full text

3.
The number of partitions of a non-negative integer
Mateja Prešern, 2002, published professional conference contribution

Keywords: discrete mathematics, combinatorics, graph theory, paritions
Published: 07.06.2012; Views: 1784; Downloads: 30
URL Link to full text

Search done in 0.6 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica