Proper distance and number of properly colored paths in edge-colored hypercubes and folded hypercubes

Abstract

In edge-colored graphs, a path is said to be properly colored when consecutive edges have different colors. A graph is properly connected if for every pair of vertices there exists such a path between them. The length of a shortest properly colored path connecting two vertices defines their proper distance . In this paper, we identify and correct a flaw in Theorem 2.2 of [1], supplying the revised statement and a complete proof. We then introduce the ( j )-coloring of the folded hypercube FH n , and establish both the proper distance and total number of distinct shortest properly colored paths for this class of edge-colored graphs. These results extend existing work on proper connectivity in hypercubes.