Premium
Insertible vertices, neighborhood intersections, and hamiltonicity
Author(s) -
Ainouche A.,
Schiermeyer I.
Publication year - 1995
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.3190200203
Subject(s) - combinatorics , mathematics , graph , undirected graph , order (exchange) , discrete mathematics , finance , economics
Let G be a simple undirected graph of order n . For an independent set S ⊂ V ( G ) of k vertices, we define the k neighborhood intersections S i = { v ϵ V ( G )\ S | N ( v ) ∩ S| = i }, 1 ≦ i ≦ k , with s i = | S i |. Using the concept of insertible vertices and the concept of neighborhood intersections , we prove the following theorem.