Anti-Ramseyeva števila

magistrsko delo

Eva Zmazek (Avtor), Sandi Klavžar (Mentor)

Povzetek

Barvanje povezav $c$ grafa $G$ je mavrica, če poljubni različni povezavi grafa $G$ pri barvanju $c$ prejmeta različni barvi. Anti-Ramsejevo število $\text{ar}(G,H)$ urejenega para enostavnih grafov $G$ in $H$ je najmanjše naravno število $r$, pri katerem za vsako $r$-barvanje povezav $c$ grafa $G$ z natanko $r$ barvami obstaja $H$-podgraf, za katerega je zožitev $c|H$ mavrica. Za nekatere pare grafov znamo določiti točne vrednosti anti-Ramseyevih števil. Pokažemo na primer lahko, da je anti-Ramseyevo število $\text{ar}(K_n,P_4)$ na paru grafov $K_n$ in $P_4$ enako $4$, če je $n=4$, in je enako $2$, če je $n \geq 5$. Kljub temu, da imata grafa $P_4$ in $C_3$ enako število povezav, se anti-Ramseyevi števili $\text{ar}(K_n,P_4)$ in $\text{ar}(K_n,C_3)$ zelo razlikujeta. Anti-Ramseyevo število $\text{ar}(K_n,C_3)$ je namreč enako številu $n$ vozlišč grafa $K_n$. Anti-Ramseyevo število znamo natančno določiti tudi na paru hiperkock $Q_n$ in $Q_{n-1}$. To je pri $n=3,4,5$ le za $3$, pri $n \geq 6$ pa le za $2$ manjše od števila povezav grafa $Q_n$.

Ključne besede

matematika;barvanje povezav;mavrica;anti-Ramseyeva števila;hiperkocke;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.09 - Magistrsko delo
Organizacija:	UL FMF - Fakulteta za matematiko in fiziko
Založnik:	[E. Zmazek]
UDK:	519.1
COBISS:	18938457
Št. ogledov:	1016
Št. prenosov:	243
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Anti-Ramsey numbers
Sekundarni povzetek:	An edge coloring $c: E(G) \to [k]$ of a graph $G$ is called a rainbow if all of its edges are colored with different colors. An Anti-Ramsey number $\text{ar}(G,H)$ for an ordered pair of graphs $G$ and $H$ is the smallest number $r$ such that for every edge coloring $c$ of $G$ with exactly $r$ colors, there exists an $H$-subgraph of $G$ such that the coloring $c$ on $H$ is a rainbow. We determine exact values of the anti-Ramsey numbers for some particular pairs of graphs. For example, we show that the exact value of the anti-Ramsey number $\text{ar}(K_n,P_4)$ for a pair of graphs $K_n$ and $P_4$ is equal to $4$ if $n=4$, and is equal to $2$ if $n \geq 5$. Even though the graphs $P_4$ and $C_3$ have the same number of edges, the anti-Ramsey numbers $\text{ar}(K_n,P_4)$ and $\text{ar}(K_n,C_3)$ differ significantly. This is because the anti-Ramsey number $\text{ar}(K_n,C_3)$ is equal to the number $n$ of vertices in $K_n$. We also determine the exact value of the anti-Ramsey number for a pair of hypercubes $Q_n$ and $Q_{n-1}$. It turns out that when $n=3,4$ or $5$, the anti-Ramsey number $\text{ar}(Q_n,Q_{n-1})$ is smaller than the number of edges in graph $Q_n$ by $3$, and in case when $n \geq 6$ it is smaller by $2$.
Sekundarne ključne besede:	edge coloring;rainbow;anti-Ramsey numbers;hypercubes;
Vrsta dela (COBISS):	Magistrsko delo/naloga
Študijski program:	0
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 2. stopnja
Strani:	IX, 60 str.
ID:	11426397