Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649378 | Discrete Mathematics | 2009 | 6 Pages |
Abstract
Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollack [R.L. Graham, H. Pollack, On the addressing problem for loop switching, Bell System Technol. J. 50 (1971) 2495–2519; and D. Djoković, Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263–267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specifically, we deal with the case where this configuration is a connected graph of order 4, a complete graph of order 5 and the case of a kk-fan Fk(k≥3)Fk(k≥3).
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Méziane Aïder, Sylvain Gravier, Kahina Meslem,