Premium
Circuits including a given set of vertices
Author(s) -
Fraisse Pierre
Publication year - 1986
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.3190100415
Subject(s) - combinatorics , digraph , mathematics , cardinality (data modeling) , order (exchange) , set (abstract data type) , discrete mathematics , computer science , finance , economics , data mining , programming language
Let G = ( V, E ) be a digraph of order n , satisfying Woodall's condition ∀ x , y ∈ V , if ( x , y ) ∉ E , then d + ( x ) + d − ( y ) ≥ n . Let S be a subset of V of cardinality s. Then there exists a circuit including S and of length at most Min( n , 2 s ). In the case of oriented graphs we obtain the same result under the weaker condition d + ( x ) + d − ( y ) ≥ n – 2 (which implies hamiltonism).