Uniquely pairable graphs

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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2008-12, Vol.308 (24), p.6104-6110
Main Author: Che, Zhongyuan
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Automorphism
Cartesian product
Computer science
control theory
systems
Exact sciences and technology
Functional analysis
Information retrieval. Graph
Involution
Mathematical analysis
Mathematics
Pairable graph
Prime factor decomposition
Prime graph
Sciences and techniques of general use
Semi-pairable graph
Theoretical computing
Uniquely pairable graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2007.11.029