Non-separating trees in connected graphs

被引：24

作者：

Diwan, Ajit A. ^{[1
]}

Tholiya, Namrata P. ^{[1
]}

机构：

[1] Indian Inst Technol, Dept Comp Sci & Engn, Bombay 400076, Maharashtra, India

来源：

DISCRETE MATHEMATICS | 2009年 / 309卷 / 16期

关键词：

Non-separating tree; Isomorphic subtree; Minimum degree;

D O I：

10.1016/j.disc.2009.03.037

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let T be any tree of order d >= 1. We prove that every connected graph G with minimum degree d contains a subtree T' isomorphic to T such that G - V(T') is connected. (C) 2009 Elsevier B.V. All rights reserved.

引用

页码：5235 / 5237

页数：3

共 7 条

[1]

Abreu M., 2002, Congressus Numerantium, V154, P21

[2]

Locke S.C., 1998, MAA Monthly, V105, P176

[3]

Lovasz L., 1979, Combinatorial Problems and Exercises, P40

[4] EXISTENCE OF CERTAIN CONFIGURATIONS IN N-SATURATED GRAPHS AND GRAPHS WITH SUFFICIENTLY LARGE EDGE DENSITY [J].

MADER, W .

MATHEMATISCHE ANNALEN, 1971, 194 (04) :295-&

[5] NON-SEPARATING INDUCED CYCLES IN GRAPHS [J].

THOMASSEN, C ;

TOFT, B .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 31 (02) :199-224

[6]

Tracy P, 2001, AM MATH MON, V108, P470

[7]

West D. B., 2001, INTRO GRAPH THEORY

← 1 →