کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
13430901 | 1842444 | 2019 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Modular decomposition of graphs and the distance preserving property
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Modular decomposition of graphs and the distance preserving property Modular decomposition of graphs and the distance preserving property](/preview/png/13430901.png)
چکیده انگلیسی
Given a graph G, a subgraph H is isometric if dH(u,v)=dG(u,v) for every pair u,vâV(H), where d is the distance function. A graph G is distance preserving (dp) if it has an isometric subgraph of every possible order. A graph is sequentially distance preserving (sdp) if its vertices can be ordered such that deleting the first i vertices results in an isometric subgraph, for all iâ¥1. We introduce a generalisation of the lexicographic product of graphs, which can be used to non-trivially describe graphs. This generalisation is the inverse of the modular decomposition of graphs, which divides the graph into disjoint clusters called modules. Using these operations, we give a necessary and sufficient condition for graphs to be dp. Finally, we show that the Cartesian product of a dp graph and an sdp graph is dp.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 265, 31 July 2019, Pages 192-198
Journal: Discrete Applied Mathematics - Volume 265, 31 July 2019, Pages 192-198
نویسندگان
Emad Zahedi, Jason P. Smith,