کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4652310 1632597 2009 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Some properties of edge intersection graphs of single bend paths on a grid
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Some properties of edge intersection graphs of single bend paths on a grid
چکیده انگلیسی

We consider the family of intersection graphs G of paths on a grid, where every vertex v in G corresponds to a single bend path Pv on a grid, and two vertices are adjacent in G if and only if the corresponding paths share an edge on the grid. We first show that these graphs have the Erdös-Hajnal property. Then we present some properties concerning the neighborhood of a vertex in these graphs, and finally we consider some subclasses of chordal graphs for which we give necessary and sufficient conditions to be edge intersection graphs of single bend paths in a grid.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 34, 1 August 2009, Pages 29-33