Találati lista | Tudóstér

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ó:
Saját polcon: