کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648380 1632438 2010 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Boxicity and cubicity of asteroidal triple free graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Boxicity and cubicity of asteroidal triple free graphs
چکیده انگلیسی

The boxicity   of a graph GG, denoted box(G), is the least integer dd such that GG is the intersection graph of a family of dd-dimensional (axis-parallel) boxes. The cubicity  , denoted cub(G), is the least dd such that GG is the intersection graph of a family of dd-dimensional unit cubes. An independent set of three vertices is an asteroidal triple if any two are joined by a path avoiding the neighbourhood of the third. A graph is asteroidal triple free (AT-free) if it has no asteroidal triple. The claw number  ψ(G)ψ(G) is the number of edges in the largest star that is an induced subgraph of GG.For an AT-free graph GG with chromatic number χ(G)χ(G) and claw number ψ(G)ψ(G), we show that box(G)≤χ(G) and that this bound is sharp. We also show that cub(G)≤≤box(G)(⌈log2ψ(G)⌉+2)(⌈log2ψ(G)⌉+2)≤≤χ(G)(⌈log2ψ(G)⌉+2)χ(G)(⌈log2ψ(G)⌉+2). If GG is an AT-free graph having girth at least 55, then box(G)≤2, and therefore cub(G)≤2⌈log2ψ(G)⌉+4.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 10–11, 6 June 2010, Pages 1536–1543
نویسندگان
, ,