首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Weak sense of direction labelings and graph embeddings
Authors:Christine T Cheng  Ichiro Suzuki
Institution:
  • Department of Computer Science, University of Wisconsin-Milwaukee, United States
  • Abstract:An edge-labeling λ for a directed graph G has a weak sense of direction (WSD) if there is a function f that satisfies the condition that for any node u and for any two label sequences α and α generated by non-trivial walks on G starting at u, f(α)=f(α) if and only if the two walks end at the same node. The function f is referred to as a coding function of λ. The weak sense of direction number of G, WSD(G), is the smallest integer k so that G has a WSD-labeling that uses k labels. It is known that WSD(G)≥Δ+(G), where Δ+(G) is the maximum outdegree of G.Let us say that a function τ:V(G)→V(H) is an embedding from G onto H if τ demonstrates that G is isomorphic to a subgraph of H. We show that there are deep connections between WSD-labelings and graph embeddings. First, we prove that when fH is the coding function that naturally accompanies a Cayley graph H and G has a node that can reach every other node in the graph, then G has a WSD-labeling that has fH as a coding function if and only if G can be embedded onto H. Additionally, we show that the problem “Given G, does G have a WSD-labeling that uses a particular coding function f?” is NP-complete even when G and f are fairly simple.Second, when D is a distributive lattice, H(D) is its Hasse diagram and G(D) is its cover graph, then WSD(H(D))=Δ+(H(D))=d, where d is the smallest integer d so that H(D) can be embedded onto the d-dimensional mesh. Along the way, we also prove that the isometric dimension of G(D) is its diameter, and the lattice dimension of G(D) is Δ+(H(D)). Our WSD-labelings are poset-based, making use of Birkhoff’s characterization of distributive lattices and Dilworth’s theorem for posets.
    Keywords:Sense of direction  Isometric embeddings  Graph embeddings  Isometric dimension  Lattice dimension
    本文献已被 ScienceDirect 等数据库收录!
    设为首页 | 免责声明 | 关于勤云 | 加入收藏

    Copyright©北京勤云科技发展有限公司  京ICP备09084417号