On Traceability of Claw-o                          −1                         -heavy Graphs

Bin long Li; Sheng gui Zhang

doi:10.1007/s10255-019-0815-9

On Traceability of Claw-o ₋₁ -heavy Graphs

Bin long Li
, Sheng gui Zhang

School of Mathematics and Statistics

Northwestern Polytechnical University Xian

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

Abstract

A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o ₋₁ -heavy if every induced claw (K _1,3 ) of G has a pair of nonadjacent vertices with degree sum at least n − 1 in G. In this paper we show that a claw-o ₋₁ -heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.

Original language	English
Pages (from-to)	444-451
Number of pages	8
Journal	Acta Mathematicae Applicatae Sinica
Volume	35
Issue number	2
DOIs	https://doi.org/10.1007/s10255-019-0815-9
State	Published - 1 Apr 2019

Keywords

05C07
05C38
05C45
claw-o -heavy graphs
forbidden subgraphs
traceable graphs

Access to Document

10.1007/s10255-019-0815-9

Cite this

@article{f3b67a794eda488696b018c4ce335857,

title = " On Traceability of Claw-o −1 -heavy Graphs ",

abstract = " A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o −1 -heavy if every induced claw (K 1,3 ) of G has a pair of nonadjacent vertices with degree sum at least n − 1 in G. In this paper we show that a claw-o −1 -heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.",

keywords = "05C07, 05C38, 05C45, claw-o -heavy graphs, forbidden subgraphs, traceable graphs",

author = "Li, \{Bin long\} and Zhang, \{Sheng gui\}",

note = "Publisher Copyright: {\textcopyright} 2019, The Editorial Office of AMAS \& Springer-Verlag GmbH Germany.",

year = "2019",

month = apr,

day = "1",

doi = "10.1007/s10255-019-0815-9",

language = "英语",

volume = "35",

pages = "444--451",

journal = "Acta Mathematicae Applicatae Sinica",

issn = "0168-9673",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - On Traceability of Claw-o −1 -heavy Graphs

AU - Li, Bin long

AU - Zhang, Sheng gui

PY - 2019/4/1

Y1 - 2019/4/1

N2 - A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o −1 -heavy if every induced claw (K 1,3 ) of G has a pair of nonadjacent vertices with degree sum at least n − 1 in G. In this paper we show that a claw-o −1 -heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.

AB - A graph is called traceable if it contains a Hamilton path, i.e., a path passing through all the vertices. Let G be a graph on n vertices. G is called claw-o −1 -heavy if every induced claw (K 1,3 ) of G has a pair of nonadjacent vertices with degree sum at least n − 1 in G. In this paper we show that a claw-o −1 -heavy graph G is traceable if we impose certain additional conditions on G involving forbidden induced subgraphs.

KW - 05C07

KW - 05C38

KW - 05C45

KW - claw-o -heavy graphs

KW - forbidden subgraphs

KW - traceable graphs

UR - https://www.scopus.com/pages/publications/85065738880

U2 - 10.1007/s10255-019-0815-9

DO - 10.1007/s10255-019-0815-9

M3 - 文章

AN - SCOPUS:85065738880

SN - 0168-9673

VL - 35

SP - 444

EP - 451

JO - Acta Mathematicae Applicatae Sinica

JF - Acta Mathematicae Applicatae Sinica

IS - 2

ER -

On Traceability of Claw-o ₋₁ -heavy Graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this