کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646801 1342314 2016 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 1, 6 January 2016, Pages 95–102
نویسندگان
, , , ,