×

Proper distance in edge-colored hypercubes. (English) Zbl 1426.05023

Summary: An edge-colored path is called properly colored if no two consecutive edges have the same color. An edge-colored graph is called properly connected if, between every pair of vertices, there is a properly colored path. Moreover, the proper distance between vertices \(u\) and \(v\) is the length of the shortest properly colored path from \(u\) to \(v\). Given a particular class of properly connected colorings of the hypercube, we consider the proper distance between pairs of vertices in the hypercube.

MSC:

05C12 Distance in graphs
05C15 Coloring of graphs and hypergraphs
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adler, M.; Halperin, E.; Karp, R. M.; Vazirani, V. V., A stochastic process on the hypercube with applications to peer-to-peer networks, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, 575-584 (electronic) (2003), ACM, New York · Zbl 1192.68018
[2] V. Coll, J. Hook, C. Magnant, K. McCready, K. Ryan, Proper diameter of graphs, Manuscript.; V. Coll, J. Hook, C. Magnant, K. McCready, K. Ryan, Proper diameter of graphs, Manuscript.
[3] Harary, F.; Hayes, J. P.; Wu, H.-J., A survey of the theory of hypercube graphs, Comput. Math. Appl., 15, 4, 277-289 (1988) · Zbl 0645.05061
[4] Li, X.; Magnant, C., Properly colored notions of connectivity - a dynamic survey, Theory Appl. Graphs, 0, 1, 1-28 (2015)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.