کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
419605 683842 2013 18 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On minimal forbidden subgraph characterizations of balanced graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
On minimal forbidden subgraph characterizations of balanced graphs
چکیده انگلیسی

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.

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