Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651412 | Discrete Mathematics | 2006 | 4 Pages |
Abstract
The pair length of a graph G is the maximum positive integer k, such that the vertex set of G can be partitioned into disjoint pairs {x,x′}{x,x′}, such that d(x,x′)⩾kd(x,x′)⩾k for every x∈V(G)x∈V(G) and x′y′x′y′ is an edge of G whenever xyxy is an edge. Chen asked whether the pair length of the cartesian product of two graphs is equal to the sum of their pair lengths. Our aim in this short note is to prove this result.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Demetres Christofides,