Simon Špacapan (Avtor)

Povzetek

The ▫$k$▫-independence number of ▫$G$▫, denoted as ▫$\alpha_k(G)$▫, is the size of a largest ▫$k$▫-colorable subgraph of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫, denoted as ▫$G \times H$▫, is the graph with vertex set ▫$V(G) \times V(H)$▫, where two vertices ▫$(x_1, y_1)$▫ and ▫$(x_2, y_2)$▫ are adjacent in ▫$G \times H$▫, if ▫$x_1$▫ is adjacent to ▫$x_2$▫ in ▫$G$▫ and ▫$y_1$▫ is adjacent to ▫$y_2$▫ in ▫$H$▫. We conjecture that for any graphs ▫$G$▫ and ▫$H$▫, ▫$$\alpha_k(G \times H) \ge \alpha_k(G)|V(H)| + \alpha_k(H)|V(G)| - \alpha_k(G) \alpha_k(H).$$▫ The conjecture is stronger than Hedetniemi's conjecture. We prove the conjecture for ▫$k = 1, 2$▫ and prove that ▫$\alpha_k(G \times H) \ge \alpha_k(G)|V(H)| + \alpha_k(H)|V(G)| - \alpha_k(G) \alpha_k(H)$▫ holds for any ▫$k$▫.

Ključne besede

matematika;teorija grafov;neodvisnostno število;kartezični produkt grafov;mathematics;graph theory;independence number;Cartesian product of graphs;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FS - Fakulteta za strojništvo
UDK: 519.17
COBISS: 16079705 Povezava se bo odprla v novem oknu
ISSN: 0195-6698
Št. ogledov: 34
Št. prenosov: 21
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
Sekundarne ključne besede: matematika;teorija grafov;neodvisnostno število;kartezični produkt grafov;
Vrsta dela (COBISS): Delo ni kategorizirano
Strani: str. 1377-1383
Letnik: Vol. 32
Zvezek: no. 8
Čas izdaje: 2011
ID: 1475892