Positive graphs

Antolín, Camarena O; Csóka, E [Csóka, Endre (matematika), szerző] Lendület Struktúrák Limeszei Kutatócsoport (HRN RAMKI); Hubai, T [Hubai, Tamás (matematika), szerző] Algebra (HRN RAMKI); Lippner, Gábor [Lippner, Gábor (mat), szerző] MTA Rényi Alfréd Matematikai Kutatóintézet; Matematika Doktori Iskola (ELTE / TTK); Lovász, L [Lovász, László (Matematika, számí...), szerző] Számítógéptudományi Tanszék (ELTE / TTK / Mat_I)

Angol nyelvű Szakcikk (Folyóiratcikk) Tudományos
Megjelent: EUROPEAN JOURNAL OF COMBINATORICS 0195-6698 1095-9971 52 (B) pp. 290-301 2016
  • SJR Scopus - Computational Theory and Mathematics: Q1
Azonosítók
Szakterületek:
  • Diszkrét matematika és kombinatorika
  • Elméleti és alkalmazott matematika
  • Matematika
  • Számítás- és információtudomány
  • Tudományos alkalmazott matematika
We study ‘‘positive’’ graphs that have a nonnegative homomorphism number into every edge-weighted graph (where the edge weights may be negative). We conjecture that all positive graphs can be obtained by taking two copies of an arbitrary simple graph and gluing them together along an independent set of nodes. We prove the conjecture for various classes of graphs including all trees. We prove a number of properties of positive graphs, including the fact that they have a homomorphic image which has at least half the original number of nodes but in which every edge has an even number of pre-images. The results, combined with a computer program, imply that the conjecture is true for all but one graph up to 10 nodes. © 2015 Elsevier Ltd.All rights reserved.
Idézők (12)
Idézett közlemények (3)
Hivatkozás stílusok: IEEEACMAPAChicagoHarvardCSLMásolásNyomtatás
2026-04-13 20:06