Weak sense of direction labelings and graph embeddings

An edge-labeling λλ for a directed graph GG has a weak sense of direction   (WSD) if there is a function ff that satisfies the condition that for any node uu and for any two label sequences αα and α′α′ generated by non-trivial walks on GG starting at uu, f(α)=f(α′)f(α)=f(α′) if and only if the two walks end at the same node. The function ff is referred to as a coding function   of λλ. The weak sense of direction number of GG, WSD(G)(G), is the smallest integer kk so that GG has a WSD-labeling that uses kk labels. It is known that WSD(G)(G)≥Δ+(G)≥Δ+(G), where Δ+(G)Δ+(G) is the maximum outdegree of GG.Let us say that a function τ:V(G)→V(H)τ:V(G)→V(H) is an embedding   from GG onto HH if ττ demonstrates that GG is isomorphic to a subgraph of HH. We show that there are deep connections between WSD-labelings and graph embeddings. First, we prove that when fHfH is the coding function that naturally accompanies a Cayley graph HH and GG has a node that can reach every other node in the graph, then GG has a WSD-labeling that has fHfH as a coding function if and only if GG can be embedded onto HH. Additionally, we show that the problem “Given GG, does GG have a WSD-labeling that uses a particular coding function ff?” is NP-complete even when GG and ff are fairly simple.Second, when DD is a distributive lattice, H(D)H(D) is its Hasse diagram and G(D)G(D) is its cover graph, then WSD(H(D))=Δ+(H(D))=d∗(H(D))=Δ+(H(D))=d∗, where d∗d∗ is the smallest integer dd so that H(D)H(D) can be embedded onto the dd-dimensional mesh. Along the way, we also prove that the isometric dimension of G(D)G(D) is its diameter, and the lattice dimension of G(D)G(D) is Δ+(H(D))Δ+(H(D)). Our WSD-labelings are poset-based, making use of Birkhoff’s characterization of distributive lattices and Dilworth’s theorem for posets.