na enopredmetnem študijskem programu 2. stopnje Izobraževalna matematika
Lea Podpečan (Avtor), Marko Jakovac (Mentor)

Povzetek

V magistrskem delu bomo predstavili igro barvanja vozlišč grafa in igralno kromatično število grafa. Podrobneje si bomo pogledali igro barvanja vozlišč grafa na kartezičnih, direktnih in leksikografskih produktih nekaterih družin grafov. Pri kartezičnih produktih ▫$K_2 \square P_n, n \in \NN, K_2 \square C_n, n \geq 3, K_2 \square K_n, n \in \NN$▫, in toroidnih grafih, ki jih dobimo s kartezičnim produktom dveh ciklov, ▫$C_{2m} \square C_n, m\geq 3, n \geq 7$▫, bomo predstavili in pokazali natančne vrednosti igralnih kromatičnih števil le-teh. Predstavili bomo tudi igralna kromatična števila naslednjih direktnih produktov: ▫$K_{1,n} \times K_{1,m}, m,n \in \NN, K_{m,n} \times K_{a,b}, a,b,n \geq 2, m \in \NN, P_n \times K_{1,m}, m \geq 3, n \geq 2, in P_2 \times W_n, n \geq 3, P_2 \times C_n, n \geq 3$▫. Nazadnje bomo predstavili še igralna kromatična števila naslednjih leksikografskih produktov: ▫$P_2 \circ P_n, n \geq 2, P_2 \circ K_{1,n}, n \in \NN, in P_2 \circ W_n, n \geq 8$▫.

Ključne besede

magistrska dela;igralno kromatično število;kartezični produkt;direktni produkt;leksikografski produkt;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
Založnik: [L. Podpečan]
UDK: 519.17(043.2)
COBISS: 24386824 Povezava se bo odprla v novem oknu
Št. ogledov: 754
Št. prenosov: 77
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Game chromatic number of some graph products
Sekundarni povzetek: In this masterʼs thesis we will present the vertex coloring game and the game chromatic number of graphs. We will take a closer look at the vertex coloring game on the Cartesian, direct, and lexicographic products of certain graph families. We will determine the exact values of the game chromatic number of the Cartesian products ▫$K_2 \square P_n, n \in \NN, K_2 \square C_n, n \geq 3, K_2 \square K_n, n \in \NN$▫, and toroidal grid graphs ▫$C_{2m} \square C_n, m\geq 3, n \geq 7$▫, which we obtain with the Cartesian product of two cycles. We will also derive the game chromatic number of the following direct products: ▫$K_{1,n} \times K_{1,m}, m,n \in \NN, K_{m,n} \times K_{a,b}, a,b,n \geq 2, m \in \NN, P_n \times K_{1,m}, m \geq 3, n \geq 2, and P_2 \times W_n, n \geq 3, P_2 \times C_n, n \geq 3$▫. Finally, we will present the game chromatic number of the following lexicographic products: ▫$P_2 \circ P_n, n \geq 2, P_2 \circ K_{1,n}, n \in \NN, and P_2 \circ W_n, n \geq 8$▫.
Sekundarne ključne besede: master theses;game chromatic number;Cartesian product;direct product;lexicographic product;
URN: URN:SI:UM:
Vrsta dela (COBISS): Magistrsko delo/naloga
Komentar na gradivo: Univ. v Mariboru, Fak. za naravoslovje in matematiko, Oddelek za matematiko in računalništvo
Strani: VIII, 54 f.
ID: 11005416
Priporočena dela:
, na enopredmetnem študijskem programu 2. stopnje Izobraževalna matematika
, ni podatka o podnaslovu
, zaključna naloga
, magistrsko delo