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

Mohammad Hailat

Journal of Mathematics Research, 2018, vol. 10, issue 1, 110-114

Abstract: 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.

Keywords: vertex-disjoint cycles; tripartite graphs (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.ccsenet.org/journal/index.php/jmr/article/view/72967/40037 (application/pdf)
http://www.ccsenet.org/journal/index.php/jmr/article/view/72967 (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ibn:jmrjnl:v:10:y:2018:i:1:p:110

Access Statistics for this article

More articles in Journal of Mathematics Research from Canadian Center of Science and Education Contact information at EDIRC.
Bibliographic data for series maintained by Canadian Center of Science and Education ().