کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646801 | 1342314 | 2016 | 8 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 339, Issue 1, 6 January 2016, Pages 95–102