کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418598 681693 2015 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Domination of maximal K4K4-minor free graphs and maximal K2,3K2,3-minor free graphs, and disproofs of two conjectures on planar graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Domination of maximal K4K4-minor free graphs and maximal K2,3K2,3-minor free graphs, and disproofs of two conjectures on planar graphs
چکیده انگلیسی

It is well known that a graph is outerplanar if and only if it is K4K4-minor free and K2,3K2,3-minor free. Campos and Wakabayashi (2013) recently proved that γ(G)≤⌊n+k4⌋ for any maximal outerplanar graph GG of order n≥3n≥3 with kk vertices of degree 2, where γ(G)γ(G) denotes the domination number of GG. Tokunaga (2013) provided a short proof for the above theorem. Based on some structural properties of K2,3K2,3-minor free graphs and K4K4-minor free graphs, applying the idea of Tokunaga we extend the theorem of Campos and Wakabayashi to all maximal K4K4-minor free graphs and all maximal K2,3K2,3-minor free graphs. We also disprove two conjectures of Tokunaga on planar graphs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 194, 30 October 2015, Pages 147–153
نویسندگان
, ,