Forbidden subgraphs and the existence of paths and cycles passing through specified vertices

Jun Fujisawa; Katsuhiro Ota; Takeshi Sugiyama; Masao Tsugaki

doi:10.1016/j.disc.2007.11.033

Forbidden subgraphs and the existence of paths and cycles passing through specified vertices

Jun Fujisawa, Katsuhiro Ota, Takeshi Sugiyama, Masao Tsugaki

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

In [H. Broersma, H. Li, J. Li, F. Tian, H.J. Veldman, Cycles through subsets with large degree sums, Discrete Math. 171 (1997) 43-54], Duffus et al. showed that every connected graph G which contains no induced subgraph isomorphic to a claw or a net is traceable. They also showed that if a 2-connected graph G satisfies the above conditions, then G is hamiltonian. In this paper, modifying the conditions of Duffus et al.'s theorems, we give forbidden structures for a specified set of vertices which assures the existence of paths and cycles passing through these vertices.

Original language	English
Pages (from-to)	6111-6114
Number of pages	4
Journal	Discrete Mathematics
Volume	308
Issue number	24
DOIs	https://doi.org/10.1016/j.disc.2007.11.033
Publication status	Published - 2008 Dec 28

Keywords

Forbidden subgraphs cycle

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2007.11.033

Cite this

@article{e3a51ed4bc214d40959c444b3702b8cc,

title = "Forbidden subgraphs and the existence of paths and cycles passing through specified vertices",

abstract = "In [H. Broersma, H. Li, J. Li, F. Tian, H.J. Veldman, Cycles through subsets with large degree sums, Discrete Math. 171 (1997) 43-54], Duffus et al. showed that every connected graph G which contains no induced subgraph isomorphic to a claw or a net is traceable. They also showed that if a 2-connected graph G satisfies the above conditions, then G is hamiltonian. In this paper, modifying the conditions of Duffus et al.'s theorems, we give forbidden structures for a specified set of vertices which assures the existence of paths and cycles passing through these vertices.",

keywords = "Forbidden subgraphs cycle",

author = "Jun Fujisawa and Katsuhiro Ota and Takeshi Sugiyama and Masao Tsugaki",

year = "2008",

month = dec,

day = "28",

doi = "10.1016/j.disc.2007.11.033",

language = "English",

volume = "308",

pages = "6111--6114",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "24",

}

TY - JOUR

T1 - Forbidden subgraphs and the existence of paths and cycles passing through specified vertices

AU - Fujisawa, Jun

AU - Ota, Katsuhiro

AU - Sugiyama, Takeshi

AU - Tsugaki, Masao

PY - 2008/12/28

Y1 - 2008/12/28

N2 - In [H. Broersma, H. Li, J. Li, F. Tian, H.J. Veldman, Cycles through subsets with large degree sums, Discrete Math. 171 (1997) 43-54], Duffus et al. showed that every connected graph G which contains no induced subgraph isomorphic to a claw or a net is traceable. They also showed that if a 2-connected graph G satisfies the above conditions, then G is hamiltonian. In this paper, modifying the conditions of Duffus et al.'s theorems, we give forbidden structures for a specified set of vertices which assures the existence of paths and cycles passing through these vertices.

AB - In [H. Broersma, H. Li, J. Li, F. Tian, H.J. Veldman, Cycles through subsets with large degree sums, Discrete Math. 171 (1997) 43-54], Duffus et al. showed that every connected graph G which contains no induced subgraph isomorphic to a claw or a net is traceable. They also showed that if a 2-connected graph G satisfies the above conditions, then G is hamiltonian. In this paper, modifying the conditions of Duffus et al.'s theorems, we give forbidden structures for a specified set of vertices which assures the existence of paths and cycles passing through these vertices.

KW - Forbidden subgraphs cycle

UR - http://www.scopus.com/inward/record.url?scp=56649114288&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=56649114288&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2007.11.033

DO - 10.1016/j.disc.2007.11.033

M3 - Article

AN - SCOPUS:56649114288

SN - 0012-365X

VL - 308

SP - 6111

EP - 6114

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 24

ER -

Forbidden subgraphs and the existence of paths and cycles passing through specified vertices

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this