Some properties of vertex-oblique graphs

Drgas-Burchardt, Ewa and Kowalska, Kamila and Michael, Jerzy and Tuza, Zsolt (2016) Some properties of vertex-oblique graphs. Discrete Mathematics, 339 (1). pp. 95-102. ISSN 0012-365X

Text 1_s2.0_S0012365X15002794_main_u.pdf Restricted to Registered users only Download (464kB) | Request a copy

Abstract

The type tG(v) of a vertex v ∈ V(G) is the ordered degree-sequence (d1,...,ddG(<inf>v)</inf>) of the vertices adjacent with v, where d1≤⋯≤ddG(<inf>v)</inf>. A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a,b the class of vertex-oblique graphs G for which |E(G)|≤a|V(G)|+b holds is finite when a≤1 and infinite when a≥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. © 2015 Elsevier B.V.

Actions (login required)

Edit Item