メインナビゲーションにスキップ 検索にスキップ メインコンテンツにスキップ

Packing cycles through prescribed vertices

研究成果: Article › 査読

抄録

The well-known theorem of Erdo{double acute accent}s and Pósa says that a graph G has either k vertex-disjoint cycles or a vertex set X of order at most f(k) such that G\X is a forest. Starting with this result, there are many results concerning packing and covering cycles in graph theory and combinatorial optimization. In this paper, we generalize Erdo{double acute accent}s-Pósa's result to cycles that are required to go through a set S of vertices. Given an integer k and a vertex subset S (possibly unbounded number of vertices) in a given graph G, we prove that either G has k vertex-disjoint cycles, each of which contains at least one vertex of S, or G has a vertex set X of order at most f(k)=40k2log2k such that G\X has no cycle that intersects S.

本文言語English
ページ(範囲)378-381
ページ数4
ジャーナルJournal of Combinatorial Theory. Series B
巻101
号5
DOI
出版ステータスPublished - 2011 9月
外部発表はい

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • 離散数学と組合せ数学
  • 計算理論と計算数学

フィンガープリント

「Packing cycles through prescribed vertices」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル