| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Naslov: The k-independence number of direct products of graphs and Hedetniemi's conjecture Špacapan, Simon (Avtor) http://dx.doi.org/10.1016/j.ejc.2011.07.002 Angleški jezik Delo ni kategorizirano (r6) 1.01 - Izvirni znanstveni članek FS - Fakulteta za strojništvo 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$▫. matematika, teorija grafov, neodvisnostno število, kartezični produkt grafov, mathematics, graph theory, independence number, Cartesian product of graphs 2011 str. 1377-1383 Vol. 32, no. 8 519.17 16079705 0195-6698 URN:SI:UM:DK:NWLVHO8H 521 10 Ostalo

Skupna ocena: (0 glasov) Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.