کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646706 1342310 2016 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Counting ordered graphs that avoid certain subgraphs
ترجمه فارسی عنوان
شمارش نمودار های مرتب شده که از برخی از زیرگرافها اجتناب می کنند
کلمات کلیدی
نمودار مرتب شده تعداد شرودر، اثبات بی حوصلگی ارگانوگرافی،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We say that G is an ordered graph if there is a linear ordering on the set of its vertices. In this paper we count ordered graphs that avoid a fixed forbidden ordered subgraph. We forbid each ordered graph with 2 edges and no isolated vertices. After a few trivial cases we show a coding of linear subspaces of F2n using colored M-avoiding graphs. We also consider the connection between subspaces and their orthogonal complements. We show a bijection between non-crossing and non-nesting graphs of order n and some other objects.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 7, 6 July 2016, Pages 1871-1877
نویسندگان
,