گراف های همسایه مشترک

عنوان فارسی مقاله: گراف های همسایه مشترک

چکیده

فرض کنید که G گراف ساده با مجموعه رئوس {v1, v2, . . . , vn} باشد. گراف همسایه مشترک G که با con(G) نشان داده می شود، گرافی با مجموعه رئوس {v1, v2, . . . , vn} است که در آن دو راس در صورتی همسایه هستند که اگر و تنها اگر حداقل یک همسایه مشترک در گراف G داشته باشد. در این مقاله، ما همسایه مشترک برخی از گراف های ترکیبی را محاسبه می کنیم. در ادامه ما به بررسی رابطه بین هم ارزی گراف G و con(G) می پردازیم. کران پایین تر برای تعداد گروه con(G) از حیث تعداد گراف G بدست می اید. در نهایت، بیان شده است که عدد کالریمتری کل G، با عدد کروماتیک con(T (G)) محدود می شود.

ادامه مطلب

راهنمای خرید:

لینک دانلود فایل بلافاصله بعد از پرداخت وجه به نمایش در خواهد آمد.
همچنین لینک دانلود به ایمیل شما ارسال خواهد شد به همین دلیل ایمیل خود را به دقت وارد نمایید.
ممکن است ایمیل ارسالی به پوشه اسپم یا Bulk ایمیل شما ارسال شده باشد.
در صورتی که به هر دلیلی موفق به دانلود فایل مورد نظر نشدید با ما تماس بگیرید.

Title: On the common neighborhood graphs

Abstract

Let G be a simple graph with vertex set {v1, v2, . . . , vn}. The common neighborhood graph (congraph) of G, denoted by con(G), is a graph with vertex set {v1, v2, . . . , vn}, in which two vertices are adjacent if and only if they have at least one common neighbor in the graph G. In this paper we compute the common neighborhood of some composite graphs. In continue we investigate the relation between hamiltonicity of graph G and con(G). Also we obtain a lower bound for the clique number of con(G) in terms of clique number of graph G. Finally we state that the total chromatic number of G is bounded by chromatic number of con(T (G)).