Some properties of vertex-oblique graphs

The type  tG(v)tG(v)of a vertex  v∈V(G)v∈V(G) is the ordered degree-sequence (d1,…,ddG(v))(d1,…,ddG(v)) of the vertices adjacent with vv, where d1≤⋯≤ddG(v)d1≤⋯≤ddG(v). A graph GG is called vertex-oblique   if it contains no two vertices of the same type. In this paper we show that for reals a,ba,b the class of vertex-oblique graphs GG for which |E(G)|≤a|V(G)|+b|E(G)|≤a|V(G)|+b holds is finite when a≤1a≤1 and infinite when a≥2a≥2. Apart from one missing interval, it solves the following problem posed by Schreyer et al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a function of the number of vertices. In addition we prove that the lexicographic product of two graphs is vertex-oblique if and only if both of its factors are vertex-oblique.