Spanning closed trails in graphs

Zhi-Hong Chen

doi:10.1016/0012-365X(93)90324-M

Spanning closed trails in graphs

Zhi-Hong Chen

Butler University

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

Abstract

<div class="line" id="line-25"> Let  G  be a 2-edge-connected simple graph on  n >;95 vertices. Let  l  be the number of vertices of degree 2 in  G . We prove that if  l < n ⧸5−19 and if, for every edge  uvϵE ( G ), d ( v )+ d ( v )&ges;2 n ⧸5−2, then exactly one of the following holds: (a)  G  has a spanning closed trail; (b)  G  can be contracted to  K 2,  c −2 , where  c &les; max {5, 3+ l } is an odd number.</div><div class="line" id="line-976"> An example shows that if a graph satisfies the conditions above except that it has too many vertices of degree 2, then the conclusion fails. This result is related to a conjecture of Benhocine et al. (1986), recently proved by Veldman. We obtain some other related results.</div>

Original language	American English
Journal	Discrete Mathematics
Volume	117
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(93)90324-M
State	Published - Jul 1993

Disciplines

Computer Sciences
Mathematics

Access to Document

10.1016/0012-365X(93)90324-MLicense: Unspecified

Cite this

@article{585c677b160a4b40991767be0e9e1096,

title = "Spanning closed trails in graphs",

abstract = " Let\  G \ be a 2-edge-connected simple graph on\  n >;95 vertices. Let\  l \ be the number of vertices of degree 2 in\  G . We prove that if\  l < n ⧸5\−19 and if, for every edge\  uv\ϵE ( G ), d ( v )+ d ( v )\&ges;2 n ⧸5\−2, then exactly one of the following holds: (a)\  G \ has a spanning closed trail; (b)\  G \ can be contracted to\  K 2,\  c \−2 , where\  c \&les; max \{5, 3+ l \} is an odd number. An example shows that if a graph satisfies the conditions above except that it has too many vertices of degree 2, then the conclusion fails. This result is related to a conjecture of Benhocine et al. (1986), recently proved by Veldman. We obtain some other related results.",

author = "Zhi-Hong Chen",

note = "Get this from a library! Spanning closed trails in graphs. [Zhi-Hong Chen] -- Let G be a 2-edge-connected simple graph on n \>;95 vertices. Let l be the number of vertices of degree 2 in ...",

year = "1993",

month = jul,

doi = "10.1016/0012-365X(93)90324-M",

language = "American English",

volume = "117",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "1-3",

}

TY - JOUR

T1 - Spanning closed trails in graphs

AU - Chen, Zhi-Hong

N1 - Get this from a library! Spanning closed trails in graphs. [Zhi-Hong Chen] -- Let G be a 2-edge-connected simple graph on n >;95 vertices. Let l be the number of vertices of degree 2 in ...

PY - 1993/7

Y1 - 1993/7

N2 - Let  G  be a 2-edge-connected simple graph on  n >;95 vertices. Let  l  be the number of vertices of degree 2 in  G . We prove that if  l < n ⧸5−19 and if, for every edge  uvϵE ( G ), d ( v )+ d ( v )&ges;2 n ⧸5−2, then exactly one of the following holds: (a)  G  has a spanning closed trail; (b)  G  can be contracted to  K 2,  c −2 , where  c &les; max {5, 3+ l } is an odd number. An example shows that if a graph satisfies the conditions above except that it has too many vertices of degree 2, then the conclusion fails. This result is related to a conjecture of Benhocine et al. (1986), recently proved by Veldman. We obtain some other related results.

AB - Let  G  be a 2-edge-connected simple graph on  n >;95 vertices. Let  l  be the number of vertices of degree 2 in  G . We prove that if  l < n ⧸5−19 and if, for every edge  uvϵE ( G ), d ( v )+ d ( v )&ges;2 n ⧸5−2, then exactly one of the following holds: (a)  G  has a spanning closed trail; (b)  G  can be contracted to  K 2,  c −2 , where  c &les; max {5, 3+ l } is an odd number. An example shows that if a graph satisfies the conditions above except that it has too many vertices of degree 2, then the conclusion fails. This result is related to a conjecture of Benhocine et al. (1986), recently proved by Veldman. We obtain some other related results.

UR - http://www.worldcat.org/oclc/4923345199

U2 - 10.1016/0012-365X(93)90324-M

DO - 10.1016/0012-365X(93)90324-M

M3 - Article

SN - 0012-365X

VL - 117

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Spanning closed trails in graphs

Abstract

Disciplines

Access to Document

Other files and links

Cite this