کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871839 | 681668 | 2016 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On strongly asymmetric and controllable primitive graphs
ترجمه فارسی عنوان
بر روی نمودارهای اولیه نامتقارن و کنترل شده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار کنترل نمودار ابتدایی کنترل شده، گراف کاملا نامتقارن،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A strongly asymmetric graph is a graph all of whose overgraphs are non-isomorphic. A graph whose 0-1 adjacency matrix has distinct and main eigenvalues is said to be controllable. We show that all controllable graphs are strongly asymmetric, thus strengthening the well-known result that controllable graphs have a trivial automorphism group. Moreover, we define the subclass of controllable primitive graphs (CP-graphs), and show that every controllable graph is either primitive or is the union or join of two controllable graphs. With the aid of CP-graphs, we prove that controllable graphs on at least six vertices have an induced path on four vertices. Furthermore, we show that the number of non-isomorphic controllable graphs and the number of non-isomorphic controllable primitive graphs on nâ¥2 vertices are both even. Using a computer search, we show that most of the controllable graphs on up to ten vertices are primitive. Among the controllable graphs on n<12 vertices, the controllable non-primitive graphs are proved to be related to the singular controllable graphs on nâ1 vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 58-67
Journal: Discrete Applied Mathematics - Volume 211, 1 October 2016, Pages 58-67
نویسندگان
Alexander Farrugia,