Constructing and Classifying Neighborhood Anti-Sperner Graphs

Authors

John P. McSorley, Southern Illinois University CarbondaleFollow

Comments

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

Abstract

For a simple graph G let N_G(u) be the (open) neighborhood of vertex u ∈ V (G). Then G is neighborhood anti-Sperner (NAS) if for every u there is a v ∈ V(G)\{u} with N_G(u) ⊆N_G(v). And a graph H is neighborhood distinct (ND) if every neighborhood is distinct, i.e., if N_H(u) ≠ N_H(v) when u ≠ v, for all u and v ∈ V(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.

Recommended Citation

McSorley, John P. "Constructing and Classifying Neighborhood Anti-Sperner Graphs." (Dec 2008).