Covering and independence in triangle structures
type: Item
instance of: scholarly article
title: Covering and independence in triangle structures
zbMATH Open document ID: 0857.05077
DOI: 10.1016/0012-365X(95)00178-Y
author: Zsolt Tuza
author: P. Erdős
author: Tibor Gallai
published in: Discrete Mathematics
publication date: 1997-02-26T00:00:00Z
review text: 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) \(\alpha_i(G)\) is the smallest cardinality of an edge set containing at least \(i\) edges of each triangle, and (2) \(\tau_i(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 \(\alpha_i(G)\leq\lfloor(n-1)^2/4\rfloor\), and every connected graph with \(n\) vertices satisfies \(\alpha_1(G)\geq(n-1)/2\). There is a positive constant \(c\) such that \(\alpha_1(G)+\tau_1(G)\geq ce^{2/3}\) holds for every graph \(G\) with \(e\) edges and \(\alpha_1(G)+\tau_1(G)\leq e-ce^{1/3}\) for every triangular graph with \(e\) edges.
reviewed by: Andrew Vince
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 895990
zbMATH Keywords: covering
zbMATH Keywords: independence
zbMATH Keywords: triangle
zbMATH Keywords: triangular graph
MaRDI profile type: Publication
cites work: A note on Ramsey numbers
cites work: Clique-transversal sets of line graphs and complements of line graphs
cites work: Graph Theory and Probability. II
cites work: Covering the cliques of a graph with vertices
cites work: Q3270978
cites work: The minimum number of triangles covering the edges of a graph
cites work: Covering all cliques of a graph
cites work: Extensions of Gallai's graph covering theorems for uniform hypergraphs
cites work: Triangle-free partial graphs and edge covering theorems
Wikidata QID: Q105719850
description: scientific article; zbMATH DE number 895990