Uniquely pairable graphs |
| |
Authors: | Zhongyuan Che |
| |
Institution: | Department of Mathematics, Penn State University, Beaver Campus, Monaca, PA 15061, USA |
| |
Abstract: | The concept of a k-pairable graph was introduced by Z. Chen On k-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 k-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 k-pairable graphs which are called uniquely k-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. |
| |
Keywords: | Automorphism Cartesian product Involution Pairable graph Prime factor decomposition Prime graph Semi-pairable graph Uniquely pairable graph |
本文献已被 ScienceDirect 等数据库收录! |
|