Circuits including a given set of vertices | Zendy

Fraisse Pierre | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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).

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research