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:

001-es BibID:	BIBFORM058511
Első szerző:	Halász Veronika (matematikus)
Cím:	Distance-constrained labeling of complete trees / Veronika Halász, Zsolt Tuza
Dátum:	2015
ISSN:	0012-365X
Megjegyzések:	We study vertex labelings ? : V ? {0, 1, 2, . . .} of a graph G = (V , E ) which assign nonnegative integers to the vertices and the restrictions depend on the distances in G. Fixing a positive integer d, the requirement is that if vertices u and v are at distance i apart (where 1 ? i ? d), then \|?(u) ? ?(v)\| > d ? i must hold. A corollary of the main result of this paper is an exact formula for the smallest possible value of maxv?V ?(v) for trees whose internal vertices all have the same degree and all leaves are at distance d/2 from the central vertex (for d even) or at distance (d ? 1)/2 from the central edge (for d odd). The case of even diameter extends the main theorem of Li et al. (2010) on complete rooted trees with fixed down-degree and height.
Tárgyszavak:	Természettudományok Matematika- és számítástudományok idegen nyelvű folyóiratközlemény külföldi lapban Graph coloring Complete tree Multi-level distance labeling Radio labeling Radio number
Megjelenés:	Discrete Mathematics. - 338 : 8 (2015), p. 1398-1406. -
További szerzők:	Tuza Zsolt (1953-) (matematikus)
Pályázati támogatás:	TÁMOP-4.2.2.C-11/1/KONV-2012-0004 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:

001-es BibID:	BIBFORM063085
035-os BibID:	(WoS)000369564000011 (Scopus)84948438718
Első szerző:	Hegedüs László (informatikus, matematikus)
Cím:	On periodic properties of circular words / Hegedüs László, Nagy Benedek
Dátum:	2016
ISSN:	0012-365X
Megjegyzések:	The conjugacy relation defines a partition of words into equivalence classes. We call these classes circular words. Periodic properties of circular words are investigated in this article. The Periodicity Theorem of Fine and Wilf does not hold for weak periods of circular words; instead we give a strict upper bound on the length of a non-unary circular word that has two given relatively prime weak periods. Weak periods also lead to a way of representing circular words in a more compact form. We investigate in which cases are these representations unique or minimal. We will also analyze weak periods of circular Thue?Morse, Fibonacci and Christoffel words.
Tárgyszavak:	Műszaki tudományok Informatikai tudományok idegen nyelvű folyóiratközlemény külföldi lapban folyóiratcikk körszavak circular words periódus periodicity
Megjelenés:	Discrete Mathematics. - 339 : 3 (2016), p. 1189-1197. -
További szerzők:	Nagy Benedek (1973-) (informatikus, matematikus)
Internet cím:	Szerző által megadott URL DOI Intézményi repozitóriumban (DEA) tárolt változat
Borító:
Saját polcon: