REAL

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

[img] 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.

Item Type: Article
Uncontrolled Keywords: Vertex-oblique graphs; Lexicographic product; Irregular graphs; Independence number
Subjects: Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 15 Sep 2016 14:17
Last Modified: 15 Sep 2016 14:17
URI: http://real.mtak.hu/id/eprint/39568

Actions (login required)

Edit Item Edit Item