کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653368 1632775 2015 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Vertex-transitive CIS graphs
ترجمه فارسی عنوان
گرافیک کشورهای غربی نسخه
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. A graph is well-covered if all its maximal stable sets are of the same size, co-well-covered if its complement is well-covered, and vertex-transitive if, for every pair of vertices, there exists an automorphism of the graph mapping one to the other. We show that a vertex-transitive graph is CIS if and only if it is well-covered, co-well-covered, and the product of its clique and stability numbers equals its order. A graph is irreducible if no two distinct vertices have the same neighborhood. We classify irreducible well-covered CIS graphs with clique number at most 3 and vertex-transitive CIS graphs of valency at most 7, which include an infinite family. We also exhibit an infinite family of vertex-transitive CIS graphs which are not Cayley.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 44, Part A, February 2015, Pages 87–98
نویسندگان
, , , ,