Edge-Maximal Graphs Containing No $r$ Vertex-Disjoint Triangles
Journal of Mathematics Research · 2017
DOI: 10.5539/jmr.v10n1p110 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Mathematics Research, 2017. Verfasst von Mohammad Hailat. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
An important problem in graph theory is that of determining the maximum number of edges in a given graph $G$ that contains no specific subgraphs. This problem has attracted the attention of many researchers. An example of such a problem is the determination of an upper bound on the number of edges of a graph that has no triangles. In this paper, we let $\mathcal{G}(n,V_{r,3})$ denote the class of graphs on $n$ vertices containing no $r$-vertex-disjoint cycles of length $3$. We show that for large $n$, $\mathcal{E}(G)\les \lfloor \frac{(n-r+1)^2}{4} \rfloor +(r-1)(n-r+1)$ for every $G\in\mathcal{G}(n,V_{r,3})$. Furthermore, equality holds if and only if $G=\Omega(n,r)=K_{r-1,\lfloor \frac{n-r+1}2\rfloor,\lceil \frac{n-r+1}2\rceil}$ where $\Omega(n,r)$ is a tripartite graph on $n$ vertices.
Zitieren
APA
Hailat, M. (2017). Edge-Maximal Graphs Containing No $r$ Vertex-Disjoint Triangles. Journal of Mathematics Research. https://doi.org/10.5539/jmr.v10n1p110
Vancouver
Hailat M. Edge-Maximal Graphs Containing No $r$ Vertex-Disjoint Triangles. Journal of Mathematics Research. 2017. doi:10.5539/jmr.v10n1p110
BibTeX
@article{Hailat2017,
author = {Hailat, Mohammad},
title = {Edge-Maximal Graphs Containing No $r$ Vertex-Disjoint Triangles},
journal = {Journal of Mathematics Research},
year = {2017},
doi = {10.5539/jmr.v10n1p110}
}
EUVIMED