EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Edge-Maximal Graphs Containing No $r$ Vertex-Disjoint Triangles

Mohammad Hailat

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →