CCL

Összesen 2 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ó:

2.

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ó:
Rekordok letöltése1