کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646627 1342308 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Split graphs and Nordhaus–Gaddum graphs
ترجمه فارسی عنوان
نمودارهای تقسیم و نمودارهای Nordhaus-Gaddum
کلمات کلیدی
قضیه Nordhaus-Gaddum؛ گرافهای NG؛ نمودارهای تقسیم ؛ نمودار شبه تقسیم. توصیف توالی درجه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A graph GG is an NG-graph if χ(G)+χ(G¯)=|V(G)|+1. We characterize NG-graphs solely from degree sequences leading to a linear-time recognition algorithm. We also explore the connections between NG-graphs and split graphs. There are three types of NG-graphs and split graphs can also be divided naturally into two categories, balanced and unbalanced. We characterize each of these five classes by degree sequence. We construct bijections between classes of NG-graphs and balanced and unbalanced split graphs which, together with the known formula for the number of split graphs on nn vertices, allows us to compute the sizes of each of these classes. Finally, we provide a bijection between unbalanced split graphs on nn vertices and split graphs on n−1n−1 or fewer vertices providing evidence for our conjecture that the rapid growth in the number of split graphs comes from the balanced split graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 339, Issue 9, 6 September 2016, Pages 2345–2356
نویسندگان
, , ,