Premium
Disjoint cycles with chords in graphs
Author(s) -
Babu Ch. Sobhan,
Diwan Ajit A.
Publication year - 2009
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.20349
Subject(s) - combinatorics , mathematics , vertex (graph theory) , disjoint sets , graph , discrete mathematics
Abstract Let $n_1,n_2,\ldots,n_k$ be integers, $n=\sum n_i$ , $n_i\ge 3$ , and let for each $1\le i\le k$ , $H_i$ be a cycle or a tree on $n_i$ vertices. We prove that every graph G of order at least n with $\sigma_2(G) \ge 2( n-k) -1$ contains k vertex disjoint subgraphs $H_1',H_2',\ldots,H_k'$ , where $H_i'=H_i$ , if $H_i$ is a tree, and $H_i'$ is a cycle with $n_i-3$ chords incident with a common vertex, if $H_i$ is a cycle. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 87–98, 2009