• Chỉ mục bởi
  • Năm xuất bản

3-arc-dominated digraphs

Tan N.D. Institute of Mathematics, Vietnam Academy of Science and Technology, 18 Hoang Quoc Viet Road, 10307 Hanoi, Viet Nam|

SIAM Journal on Discrete Mathematics Số 3, năm 2010 (Tập 24, trang 1153-1161)

ISSN: 8954801

ISSN: 8954801

DOI: 10.1137/080740143

Tài liệu thuộc danh mục: Scopus



Từ khóa: D-arc-dominated digraph; Inneighbor; Oriented digraph; Outdegree; Outneighbor; Graph theory
Tóm tắt tiếng anh
An oriented simple digraph D = (V,A) with the minimum outdegree d is called d-arc-dominated if for every arc (x,y) ∈ A there is a vertex u ∈ V with the outdegree d such that both (u, x) ∈ A and (u, y) ∈ A hold. At the 20th British combinatorial conference, Lichiardopol posed the problem of characterizing d-arc-dominated digraphs. He also has posed the conjecture that a d-arc-dominated digraph with d ≥ 2k-1 contains k vertex-disjoint directed cycles. In this paper, we give a characterization for 3-arc-dominated digraphs. Based on this characterization, we classify all 3-arc-dominated digraphs and show that the above conjecture is true when d = 3. © 2010 Society for Industrial and Applied Mathematics.

Xem chi tiết