Properties of minimally t-toughgraphs

被引：8

作者：

Katona, Gyula Y. ^{[1
,2
]}

Soltesz, Daniel ^{[1
]}

Varga, Kitti ^{[1
]}

机构：

[1] Budapest Univ Technol & Econ, Dept Comp Sci & Informat Theory, Budapest, Hungary

[2] MTA ELTE Numer Anal & Large Networks Res Grp, Budapest, Hungary

来源：

DISCRETE MATHEMATICS | 2018年 / 341卷 / 01期

关键词：

Minimally t-tough; Toughness; Claw-free graph; Embedded subgraph; GRAPHS;

D O I：

10.1016/j.disc.2017.08.033

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G is minimally t-tough if the toughness of G is t and the deletion of any edge from G decreases the toughness. Kriesell conjectured that for every minimally 1-tough graph the minimum degree delta(G) = 2. We show that in every minimally 1-tough graph delta(G) <= n/3 + 1. We also prove that every minimally 1-tough, claw-free graph is a cycle. On the other hand, we show that for every positive rational number t any graph can be embedded as an induced subgraph into a minimally t-tough graph. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：221 / 231

页数：11

共 7 条

[1] ON THE COMPLEXITY OF RECOGNIZING TOUGH GRAPHS [J].

BAUER, D ;

MORGANA, A ;

SCHMEICHEL, E .

DISCRETE MATHEMATICS, 1994, 124 (1-3) :13-17

[2]

Chvatal V., 1973, Discrete Mathematics, V5, P215, DOI 10.1016/0012-365X(73)90138-6

[3] A REMARK ON HAMILTONIAN CYCLES [J].

HAGGKVIST, R ;

NICOGHOSSIAN, GG .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1981, 30 (01) :118-120

[4]

Kaiser T., PROBL WORKSH DOM CYC

[5]

Lovasz L., 2007, Combinatorial Problems and Exercises

[6] PROPERTY OF ATOMS OF FINITE GRAPHS [J].

MADER, W .

ARCHIV DER MATHEMATIK, 1971, 22 (03) :333-&

[7] HAMILTONIAN RESULTS IN K1,3 FREE GRAPHS [J].

MATTHEWS, MM ;

SUMNER, DP .

JOURNAL OF GRAPH THEORY, 1984, 8 (01) :139-146

← 1 →