Constructing and classifying neighborhood anti-Sperner graphs |
| |
Authors: | John P. McSorley |
| |
Affiliation: | Department of Mathematics, Mailcode 4408, Southern Illinois University, Carbondale, IL 62901-4408, United States |
| |
Abstract: | For a simple graph G let NG(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 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 u≠v, for all u and 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 r-regular NAS graphs for r=0,1,…,6. |
| |
Keywords: | Graph Neighborhood Distinct Sperner Anti-Sperner Classify |
本文献已被 ScienceDirect 等数据库收录! |
|