Partial cubes as subdivision graphs and as generalized Petersen graphs
作者： Sandi Klavžar , Alenka Lipovec
DOI: 10.1016/S0012-365X(02)00575-7
关键词:
摘要: Isometric subgraphs of hypercubes are known as partial cubes. The subdivision graph a G is obtained from by subdividing every edge G. It proved that for connected its cube if and only block either cycle or complete graph. Regular cubes also considered. In particular, it shown among the generalized Petersen graphs P(10,3) P(2n, 1), n ≥ 2, (regular)
elsevier.com
sci-hub.se 参考文章(17)
Mark Ramras, Regular Subgraphs of Hypercubes. Ars Combinatoria. ,vol. 52, ,(1999)
Boštjan Brešar, Sandi Klavžar, On partial cubes and graphs with convex intervals Commentationes Mathematicae Universitatis Carolinae. ,vol. 43, pp. 537- 545 ,(2002)
Wilfried Imrich, Sandi Klavžar, Richard H Hammack, Product Graphs: Structure and Recognition ,(2000)
A. Dress, M. Hendy, K. Huber, V. Moulton, On the number of vertices and edges of the Buneman graph Annals of Combinatorics. ,vol. 1, pp. 329- 337 ,(1997) , 10.1007/BF02558484
R. L. Graham, P. M. Winkler, Isometric embeddings of graphs. Proceedings of the National Academy of Sciences of the United States of America. ,vol. 81, pp. 7259- 7260 ,(1984) , 10.1073/PNAS.81.22.7259
Martyn Mulder, n‐cubes and median graphs Journal of Graph Theory. ,vol. 4, pp. 107- 110 ,(1980) , 10.1002/JGT.3190040112
Carla D Savage, Peter Winkler, Monotone gray codes and the middle levels problem Journal of Combinatorial Theory, Series A. ,vol. 70, pp. 230- 248 ,(1995) , 10.1016/0097-3165(95)90091-8
R. L. Graham, P. M. Winkler, On isometric embeddings of graphs Transactions of the American Mathematical Society. ,vol. 288, pp. 527- 536 ,(1985) , 10.1090/S0002-9947-1985-0776391-5
Shoji Shinoda, On the characteristic polynomial of the adjacency matrix of the subdivision graph of a graph Discrete Applied Mathematics. ,vol. 2, pp. 349- 351 ,(1980) , 10.1016/0166-218X(80)90031-1
D.Ž Djoković, Distance-preserving subgraphs of hypercubes Journal of Combinatorial Theory, Series B. ,vol. 14, pp. 263- 267 ,(1973) , 10.1016/0095-8956(73)90010-5