کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649644 1342462 2009 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Netlike partial cubes, V: Completion and netlike classes
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Netlike partial cubes, V: Completion and netlike classes
چکیده انگلیسی

We define a completion   of a netlike partial cube GG by replacing each convex 2n2n-cycle CC of GG with n≥3n≥3 by an nn-cube admitting CC as an isometric cycle. We prove that a completion of GG is a median graph if and only if GG has the Median Cycle Property (MCP) (see N. Polat, Netlike partial cubes III. The Median Cycle Property, Discrete Math.). In fact any completion of a netlike partial cube having the MCP is defined by a universal property and turns out to be a minimal median graph containing GG as an isometric subgraph. We show that the completions of the netlike partial cubes having the MCP preserves the principal constructions of these graphs, such as: netlike subgraphs, gated amalgams and expansions. Conversely any netlike partial cube having the MCP can be obtained from a median graph by deleting some particular maximal finite hypercubes. We also show that, given a netlike partial cube GG having the MCP, the class of all netlike partial cubes having the MCP whose completions are isomorphic to those of GG share different properties, such as: depth, lattice dimension, semicube graph and crossing graph.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 309, Issue 13, 6 July 2009, Pages 4362–4376
نویسندگان
,