Abstract
Given a graph G, and two vertex sets S and T of size k each, a many-to-many k-disjoint path cover of G joining S and T is a collection of k disjoint paths between S and T that cover every vertex of G. It is classified as paired if each vertex of S must be joined to a designated vertex of T, or unpaired if there is no such constraint. In this article, we first present a necessary and sufficient condition for the cube of a connected graph to have a paired 2-disjoint path cover. Then, a corresponding condition for the unpaired type of 2-disjoint path cover problem is immediately derived. It is also shown that these results can easily be extended to determine if the cube of a connected graph has a hamiltonian path from a given vertex to another vertex that passes through a prescribed edge
چکیده
گراف ارائه شده G و دو مجموعه راس S و T هر یک با اندازه k ، پوشش با k مسیر مجزای متنوع برای اتصال G به S و T ، مجموعه ای از k مسیر مجزا بین S و T را پوشش می دهد. این مجموعه به شکل زوج مرتب طبقه بندی می شود البته هر راس S باید به راس تعیین شده از T اتصال داشته یا در صورت عدم وجود هیچ محدودیتی ، باید به صورت زوج نباشد. در این مقاله ما ابتدا شرط لازم و کافی را برای مکعبی از گراف متصل و برای داشتن پوشش تزویج شده از 2 مسیر مجزا را ارائه می دهیم. سپس شرطی متناظر برای نوع تزویج نشده از مسئله پوشش دو مسیر مجزا فورا استنتاج می گردد. همچنین نشان داده می شود که این نتایج می توانند به آسانی برای تعیین مکعبی از گراف متصل با مسیر همیلتونی از راس ارائه شده تا راسی دیگر که از طریق یال تعیین شده ، تعمیم داده شوند.
1-مقدمه
مشخصات مسئله
گراف غیر مستقیم G ارائه شده ، یک پوشش مسیری ، مجموعه ای از مسیرها در G است که در آن هر راس در V(G) از طریق حداقل یک مسیر پوشش داده می شود. البته با تمرکزی خاص ، این حالت ، یک پوشش مسیری مجزا از رئوس یا به طور ساده تر پوشش مسیر مجزا است که نوعی با محدودیت افزون بوده و هر راس در آن ( احتمالا به جز برای رئوس پایانی ) باید متعلق به یک و تنها یک مسیر باشد...