|
Citace:
|
JENDROL', S., KAISER, T., RYJÁČEK, Z., SCHIERMEYER, I. A Dirac theorem for trestles. Discrete Mathematics, 2012, roč. 312, č. 12-13, s. 2000-2004. ISSN: 0012-365X
|
|
Druh:
|
ČLÁNEK
|
|
Jazyk publikace:
|
eng
|
|
Anglický název:
|
A Dirac theorem for trestles
|
|
Rok vydání:
|
2012
|
|
Autoři:
|
Doc. RNDr. Tomáš Kaiser Ph.D.
,
Prof. RNDr. Zdeněk Ryjáček DrSc.
,
Prof. RNDr. Zdeněk Ryjáček DrSc.
|
|
Abstrakt CZ:
|
V článku dokazujeme dolní odhad pro velikost největšího 2-souvislého podgrafu s maximálním stupněm nejvýše k v daném grafu G. Z výsledku plyne, že každý 2-souvislý graf s n vrcholy a minimálním stupněm alespoň 2n/(k+2) obsahuje podgraf tohoto typu, který pokrývá všechny vrcholy. Tento důsledek je zobecněním Diracovy věty.
|
|
Abstrakt EN:
|
A k-subtrestle in a graph G is a 2-connected subgraph of G of maximum degree at most k. We prove a lower bound on the order of a largest k- subtrestle of G, in terms of k and the minimum degree of G. A corollary of our result is that every 2-connected graph with n vertices and minimum degree at least 2n/(k + 2) contains a spanning k-subtrestle. This corollary is an extension of Dirac?s Theorem.
|
|
Klíčová slova
|
|