Premium
Long paths through four vertices in a 2‐connected graph
Author(s) -
Barovich Mark V.
Publication year - 2000
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/(sici)1097-0118(200002)33:2<55::aid-jgt1>3.0.co;2-s
Subject(s) - combinatorics , mathematics , path graph , graph , bound graph , connectivity , path (computing) , wheel graph , discrete mathematics , graph power , line graph , computer science , programming language
Let G be a 2‐connected graph, let u and v be distinct vertices in V ( G ), and let X be a set of at most four vertices lying on a common ( u, v )‐path in G . If deg( x ) ≥ d for all x ∈ V ( G ) \ { u, v }, then there is a ( u, v )‐path P in G with X ⊂ V ( P ) and | E ( P )| ≥ d . © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000