Constructing and classifying neighborhood anti-Sperner graphs

For a simple graph GG let NG(u)NG(u) be the (open) neighborhood of vertex u∈V(G)u∈V(G). Then GG is neighborhood anti-Sperner (NAS) if for every uu there is a v∈V(G)∖{u}v∈V(G)∖{u} with NG(u)⊆NG(v)NG(u)⊆NG(v). And a graph HH is neighborhood distinct (ND) if every neighborhood is distinct, i.e.  , if NH(u)≠NH(v)NH(u)≠NH(v) when u≠vu≠v, for all uu and v∈V(H)v∈V(H).In Porter and Yucas [T.D. Porter, J.L. Yucas. Graphs whose vertex-neighborhoods are anti-sperner, Bulletin of the Institute of Combinatorics and its Applications 44 (2005) 69–77] a characterization of regular NAS graphs was given: ‘each regular NAS graph can be obtained from a host graph by replacing vertices by null graphs of appropriate sizes, and then joining these null graphs in a prescribed manner’. We extend this characterization to all   NAS graphs, and give algorithms to construct all NAS graphs from host ND graphs. Then we find and classify all connected rr-regular NAS graphs for r=0,1,…,6r=0,1,…,6.