Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 857.05077
Autor: Erdös, Paul; Gallai, Tibor; Tuza, Zsolt
Title: Covering and independence in triangle structures. (In English)
Source: Discrete Math. 150, No.1-3, 89-101 (1996).
Review: A graph is triangular if each edge is contained in at least one triangle. In the paper under review, several results concerning the following two invariants are proved. For i = 1,2 we have: (1) \alphai(G) is the smallest cardinality of an edge set containing at least i edges of each triangle, and (2) \taui(G) is the largest cardinality of an edge set containing at most i edges of each triangle. For example, every triangular graph G with n vertices satisfies \alphai(G) \leq \lfloor(n-1)2/4\rfloor, and every connected graph with n vertices satisfies \alpha1(G) \geq (n-1)/2. There is a positive constant c such that \alpha1(G)+\tau1(G) \geq ce2/3 holds for every graph G with e edges and \alpha1(G)+\tau1(G) \leq e-ce1/3 for every triangular graph with e edges.
Reviewer: A.Vince (Gainesville)
Classif.: * 05C70 Factorization, etc.
05C35 Extremal problems (graph theory)
05C55 Generalized Ramsey theory
Keywords: covering; independence; triangle; triangular graph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag