Covering and independence in triangle structures |
| |
Authors: | Paul Erds Tibor Gallai Zsolt Tuza |
| |
Institution: | Computer and Automation Institute, Hungarian Academy of Sciences, Kende u.. 13–17, H-1111, Budapest, Hungary |
| |
Abstract: | Let G be a graph in which each edge is contained in at least one triangle (complete subgraph on three vertices). We investigate relationships between the smallest cardinality of an edge set containing at least i edges of each triangle and the largest cardinality of an edge set containing at most j edges of each triangle (i, j ε {1,2}), and also compare those invariants with the numbers of vertices and edges in G. Several open problems are raised in the concluding section. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|