Premium
Extremal problems involving neighborhood unions
Author(s) -
Faudree Ralph J.,
Gould Ronald J.,
Jacobson Michael S.,
Schelp Richard H.
Publication year - 1987
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190110413
Subject(s) - combinatorics , mathematics , path (computing) , graph , property (philosophy) , matching (statistics) , discrete mathematics , computer science , statistics , philosophy , epistemology , programming language
We examine several extremal problems for graphs satisfying the property | N ( x ) ∪ N ( y )| ⩾ s for every pair of nonadjacent vertices x, y ϵ V ( G ). In particular, values for s are found that ensure that the graph contains an s ‐matching, a 1‐factor, a path of a specific length, or a cycle of a specific length.