A note on total excess of spanning trees

Yukichika Ohnishi; Katsuhiro Ota

A note on total excess of spanning trees

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

Abstract

A graph G is said to be t-tough if ⌋ S ⌊ ≥ t. ω(G-S) for any subset S of V (G) with ω(G-S) ≥ 2, where ω(G-S) is the number of components in G-S. In this paper, we investigate t-tough graphs including the cases. Using the notion of total excess. We also investigate the relation between spanning trees in a graph obtained by different pairs of parameters (n, ε). As a consequence, we prove the existence of "a universal tree" in a connected t-tough graph G, that is a spanning tree T.

Original language	English
Pages (from-to)	97-103
Number of pages	7
Journal	AKCE International Journal of Graphs and Combinatorics
Volume	8
Issue number	1
Publication status	Published - 2011 Jun 1
Externally published	Yes

Keywords

Spanning trees
Total excess
Toughness

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

Cite this

@article{f9500dcb08e6446cafe45c8074cafe35,

title = "A note on total excess of spanning trees",

abstract = "A graph G is said to be t-tough if ⌋ S ⌊ ≥ t. ω(G-S) for any subset S of V (G) with ω(G-S) ≥ 2, where ω(G-S) is the number of components in G-S. In this paper, we investigate t-tough graphs including the cases. Using the notion of total excess. We also investigate the relation between spanning trees in a graph obtained by different pairs of parameters (n, ε). As a consequence, we prove the existence of {"}a universal tree{"} in a connected t-tough graph G, that is a spanning tree T.",

keywords = "Spanning trees, Total excess, Toughness",

author = "Yukichika Ohnishi and Katsuhiro Ota",

year = "2011",

month = jun,

day = "1",

language = "English",

volume = "8",

pages = "97--103",

journal = "AKCE International Journal of Graphs and Combinatorics",

issn = "0972-8600",

publisher = "Kalasalingam University",

number = "1",

}

TY - JOUR

T1 - A note on total excess of spanning trees

AU - Ohnishi, Yukichika

AU - Ota, Katsuhiro

PY - 2011/6/1

Y1 - 2011/6/1

N2 - A graph G is said to be t-tough if ⌋ S ⌊ ≥ t. ω(G-S) for any subset S of V (G) with ω(G-S) ≥ 2, where ω(G-S) is the number of components in G-S. In this paper, we investigate t-tough graphs including the cases. Using the notion of total excess. We also investigate the relation between spanning trees in a graph obtained by different pairs of parameters (n, ε). As a consequence, we prove the existence of "a universal tree" in a connected t-tough graph G, that is a spanning tree T.

AB - A graph G is said to be t-tough if ⌋ S ⌊ ≥ t. ω(G-S) for any subset S of V (G) with ω(G-S) ≥ 2, where ω(G-S) is the number of components in G-S. In this paper, we investigate t-tough graphs including the cases. Using the notion of total excess. We also investigate the relation between spanning trees in a graph obtained by different pairs of parameters (n, ε). As a consequence, we prove the existence of "a universal tree" in a connected t-tough graph G, that is a spanning tree T.

KW - Spanning trees

KW - Total excess

KW - Toughness

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

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

M3 - Article

AN - SCOPUS:79961142816

SN - 0972-8600

VL - 8

SP - 97

EP - 103

JO - AKCE International Journal of Graphs and Combinatorics

JF - AKCE International Journal of Graphs and Combinatorics

IS - 1

ER -

A note on total excess of spanning trees

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this