کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650330 | 1342485 | 2008 | 7 صفحه PDF | دانلود رایگان |
The concept of a kk-pairable graph was introduced by Z. Chen [On kk-pairable graphs, Discrete Mathematics 287 (2004), 11–15] as an extension of hypercubes and graphs with an antipodal isomorphism. In the present paper we generalize further this concept of a kk-pairable graph to the concept of a semi-pairable graph. We prove that a graph is semi-pairable if and only if its prime factor decomposition contains a semi-pairable prime factor or some repeated prime factors. We also introduce a special class of kk-pairable graphs which are called uniquely kk-pairable graphs. We show that a graph is uniquely pairable if and only if its prime factor decomposition has at least one pairable prime factor, each prime factor is either uniquely pairable or not semi-pairable, and all prime factors which are not semi-pairable are pairwise non-isomorphic. As a corollary we give a characterization of uniquely pairable Cartesian product graphs.
Journal: Discrete Mathematics - Volume 308, Issue 24, 28 December 2008, Pages 6104–6110