Covering the edges of a graph with triangles
Motivated by a question of \textit{P. Erdős} et al. [ibid. 150, No. 1--3, 89--101 (1996; Zbl 0857.05077)], the authors study the relationship between the following graph invariants. Let~\(G\) be an undirected graph.\N\begin{itemize}\N\item \(\rho_{\Delta}(G)\) is the minimum cardinality of a set consisting of edges and triangles that together cover~\(E(G)\);\N\item \(\alpha_1(G)\) is the maximum cardinality of an edge set that contains at most one edge from each triangle in~\(G\), also called the triangle-independence number of~\(G\);\N\item \(\nu_{\Delta}(G)\) is the maximum number of pairwise edge-disjoint triangles in~\(G\).\N\end{itemize}\NAmong other results, they prove that for every graph~\(G\) with~\(m\) edges,\N\[\N\rho_\Delta(G) \le \left\lfloor\frac{1}{2}\left(m+\alpha_1(G)-\nu_\Delta(G)\right)\right\rfloor.\N\]\NThe above upper bound for \(\rho_\Delta(G)\) is tight as the authors show that, for any positive integer \(n\), there exists an \(n\)-vertex graph \(G\) with the equality. The authors also prove the following Nordhaus-Gaddum-type inequalities for~\(\alpha_1\) and~\(\rho_{\Delta}\): for any \(n\)-vertex graph~\(G\),\N\[\N\alpha_1(G)+\alpha_1(\overline{G})\le \frac{n^2}{4}+O\left(\frac{n^2}{\ln n}\right),\N\]\Nholds as \(n\to\infty\), and\N\[\N\rho_{\Delta}(G)+\rho_{\Delta}(\overline{G})\le\frac{n^2}{3}+o(n^2).\N\]\NBoth upper bounds are asymptotically tight.
- A survey of Nordhaus-Gaddum type relations
- Clique coverings and claw-free graphs
- Covering and independence in triangle structures
- Extremal clique coverings of complementary graphs
- scientific article; zbMATH DE number 4213989 (Why is no real title available?)
- On a Conjecture of Erdős, Gallai, and Tuza
- On Complementary Graphs
- Pairwise balanced designs and sigma clique partitions
- Some recent problems and results in graph theory
- The CRC handbook of combinatorial designs
- Triangle-free partial graphs and edge covering theorems
This page was built for publication: Covering the edges of a graph with triangles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6635092)
