Összesen 1 találat.
#/oldal:
Részletezés:
Rendezés:

1.

001-es BibID:BIBFORM058510
Első szerző:Halász Veronika (matematikus)
Cím:Asymptotically optimal induced decompositions / Veronika Halász, Zsolt Tuza
Dátum:2014
ISSN:1452-8630
Megjegyzések:Solving a problem raised by Bondy and Szwarcfiter [J. Graph Theory, 72 (2013), 462-477], we prove that if the edge set of a graph G of order n can be decomposed into edge-disjoint induced copies of the path P_4 or of the paw K_4 P_3 , then the complement of G has at least cn^{3/2} edges. This lower-bound is tight apart from the actual value of c, and settles the previously unsolved cases for the graphs with at most four vertices. More generally the lower bound cn^{3/2} holds for any graph without isolated vertices which is not a complete multipartite graph; but a linear upper bound is valid for any complete tripartite graph.
Tárgyszavak:Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban
Induced subgraph
decomposition
complete multipartite graph
extremal graph theory
Megjelenés:Applicable Analysis and Discrete Mathematics. - 8 : 2 (2014), p. 320-329. -
További szerzők:Tuza Zsolt (1953-) (matematikus)
Pályázati támogatás:T-81493
OTKA
TAMOP-4.2.2.A-11/1/KONV-2012-0072
TÁMOP
Internet cím:Szerző által megadott URL
DOI
Intézményi repozitóriumban (DEA) tárolt változat
Borító:
Rekordok letöltése1