Published in Discrete Mathematics, 308(23), 5428-5445. doi: 10.1016/j.disc.2007.10.005


For a simple graph G let NG(u) be the (open) neighborhood of vertex uV (G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a vV(G)\{u} with NG(u) ⊆NG(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if NH(u) ≠ NH(v) when uv, for all u and vV(H).

In Porter and Yucas [3] 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 r-regular NAS graphs for r = 0, 1, . . ., 6.

nasAFIN.dvi (157 kB)
.dvi copy