کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419632 683842 2013 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the anti-Kekulé number and odd cycle transversal of regular graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On the anti-Kekulé number and odd cycle transversal of regular graphs
چکیده انگلیسی

Let GG be a graph with a perfect matching. The anti-Kekulé number is the smallest number of edges of GG whose removal will result in a connected subgraph with no perfect matching. In this note, we show that, if GG is a cyclically (r+1)(r+1)-edge-connected rr-regular graph (r≥3r≥3) of even order, then either the anti-Kekulé number of GG is at least r+1r+1, or GG is not bipartite, and the smallest odd cycle transversal of GG has at most rr edges. For cubic graphs, the bound of the anti-Kekulé number is optimal. Our result generalizes previous results on anti-Kekulé numbers of fullerenes obtained by Kutnar et al. [K. Kutnar, J. Sedlar, D. Vukičević, On the anti-Kekulé number of leapfrog fullerenes, J. Math. Chem. 45 (2009) 431–441.] and Yang et al. [Q. Yang, D. Ye, H. Zhang, Y. Lin, On the anti-Kekulé number of fullerenes, MATCH Commun. Math. Comput. Chem. 67 (2) (2012) 281–288].

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 13–14, September 2013, Pages 2196–2199
نویسندگان
,