کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
9514524 1632609 2005 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Edge intersection graphs of linear 3-uniform hypergraphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Edge intersection graphs of linear 3-uniform hypergraphs
چکیده انگلیسی
Let L3l be the class of edge intersection graphs of linear 3-uniform hypergraphs. The problem of recognizing G∈L3l is NP-complete. Denote by δALG the minimal integer such that the problem "G∈L3l" is polynomially solvable in the class of graphs G with the minimal vertex degree δ(G)≥δALG and by δFIS the minimal integer such that L3l can be characterized by a finite list of forbidden induced subgraphs in the class of graphs G with δ(G)≥δFIS. It is proved that δALG≤10 and δFIS≤16.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 22, 15 October 2005, Pages 33-40
نویسندگان
, , ,