A graph G is said to be hom-idempotent if there is a homomorphism from G2 to G, and weakly hom-idempotent if for some n≥1 there is a homomorphism from Gn+1 to Gn. Larose et al. (1998) proved that Kneser graphs KG(n,k) are ...

We prove that asymptotically (as n -> infinity) almost all graphs with n vertices and C(d)n(2-1/2d) log(1/d) n edges are universal with respect to the family of all graphs with maximum degree bounded by d. Moreover, we ...

A connected graph G=(V,E) with m edges is called universal antimagic if for each set B of m positive integers there is an bijective function f:E→B such that the function f˜:V→N defined at each vertex v as the sum of all ...

Circular-arc graphs are the intersection graphs of open arcs on a circle. Circle graphs are the intersection graphs of chords on a circle. These graph classes have been the subject of much study for many years and numerous ...

Hartsfield and Ringel in 1990 conjectured that any connected graph with q >= 2 edges has an edge labeling f with labels in the set {1,..., q}, such that for every two distinct vertices u and v, f(u) not equal= f(v), where ...