Article in press
Authors:
Title:
The maximum number of edges in a $\{K_{r+1},M_{k+1}\}$-free graph
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2022-09-20 , Revised: 2023-07-30 , Accepted: 2023-08-03 , Available online: 2023-09-19 , https://doi.org/10.7151/dmgt.2515
Abstract:
Let $G$ be a graph and $\mathcal{F}$ be a family of graphs. We say $G$ is
$\mathcal{F}$-free if it does not contain $F$ as subgraph for any
$F\in\mathcal{F}$. The Turán number $\textrm{ex}(n,\mathcal{F})$ is defined
as the maximum number of edges in an $\mathcal{F}$-free graph on $n$ vertices.
Let $K_{r+1}$ denote the complete graph on $r+1$ vertices and let $M_{k+1}$
denote the graph on $2k+2$ vertices with $k+1$ pairwise disjoint edges. By using
the alternating path technique and the Zykov symmetrization, we determine that
for $n>3k$,
$$
\textrm{ex}(n, \{M_{k+1},K_{r+1}\})= t_{r-1}(k)+k(n-k),
$$
where $t_{r-1}(k)$ is the number of edges in an $(r-1)$-partite $k$-vertex
Turán graph. Let $\nu(G)$, $\tau(G)$ denote the matching number and the
vertex cover number of $G$, respectively. For $n\geq 2k$, we prove that if
$\nu(G)\leq k$ and $\tau(G)\geq k+r$, then
$$
e(G)\leq \max\left\{\binom{2k+1}{2}, \binom{k+r+1}{2}+(k-r)(n-k-r-1)\right\}.
$$
Keywords:
Turán number, alternating path, Zykov symmetrization
References:
- H.L. Abbott, D. Hanson and N. Sauer, Intersection theorems for systems of sets, J. Combin. Theory Ser. A 12 (1972) 381–389.
https://doi.org/10.1016/0097-3165(72)90103-3 - J. Akiyama and P. Frankl, On the size of graphs with complete-factors, J. Graph Theory 9 (1985) 197–201.
https://doi.org/10.1002/jgt.3190090117 - N. Alon and P. Frankl, Turán graphs with bounded matching number (2022).
arXiv: 2210.15076 - N. Alon, M. Krivelevich and B. Sudakov, Turán numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput. 12 (2003) 477–494.
https://doi.org/10.1017/S0963548303005741 - I. Anderson, Perfect matching of a graph, J. Combin. Theory. Ser. B 10 (1971) 183–186.
https://doi.org/10.1016/0095-8956(71)90041-4 - C. Berge, Sur le couplage maximum d'un graphe, C.R. Acad. Sci. Paris 247 (1958) 2–29.
- C. Berge, The Theory of Graphs and its Applications (Methuen, London and Wiley, New York, 1962).
- J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
- W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver, Combinatorial Optimization (Wiley, 1998).
https://doi.org/10.1002/9781118033142 - P. Erdős and T. Gallai, On maximal paths and circuits of graphs, Acta. Math. Hungar. 10 (1959) 337–356.
https://doi.org/10.1007/BF02024498 - Z. Füredi, On a Turán type problem of Erdős, Combinatorica 11 (1991) 75–79.
https://doi.org/10.1007/BF01375476 - F. Gavril, Testing for equality between maximum matching and minimum node covering, Inform. Process. Lett. 6 (1977) 199–202.
https://doi.org/10.1016/0020-0190(77)90068-0 - P. Hall, On representatives of subsets, in: Classic Papers in Combinatorics, I. Gessel and G.-C. Rota (Ed(s)), (Modern Birkkäuser Classic 1987) 58–62.
https://doi.org/10.1007/978-0-8176-4842-8_4 - D. König, Theorie der endlichen und unendlichen Graphen (Akademischen Verlagsgesellchaft, Leipig, 1936).
- P. Kővári, V.T. Sós and P. Turán, On a problem of Zarankiewicz, Colloq. Math. 3 (1954) 50–57.
- W. Mantel, Problem $28$, Wiskundige Opgaven 10 (1907) 60–61.
- M.D. Plummer and L. Lovász, Matching Theory (Elsevier, 1986).
- A. Sidorenko, What we know and what we do not know about Turán numbers, Graphs Combin. 11 (1995) 179–199.
https://doi.org/10.1007/BF01929486 - P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452, in Hungarian.
- W.T. Tutte, The factorization of linear graphs, J. Lond. Math. Soc. 22 (1947) 107–111.
https://doi.org/10.1112/jlms/s1-22.2.107 - D.B. West, A short proof of the Berge-Tutte Formula and the Gallai-Edmonds Structure Theorem, European J. Combin. 32 (2011) 674–676.
https://doi.org/10.1016/j.ejc.2011.01.009 - L.-T. Yuan, Extremal graphs for the k-flower, J. Graph Theory 89 (2018) 26–39.
https://doi.org/10.1002/jgt.22237 - L.-T. Yuan, Extremal graphs for odd wheels, J. Graph Theory 98 (2021) 691–707.
https://doi.org/10.1002/jgt.22727 - L.-T. Yuan, Extremal graphs for edge blow-up of graphs, J. Combin. Theory. Ser. B. 152 (2022) 379–398.
https://doi.org/10.1016/j.jctb.2021.10.006 - A.A. Zykov, On some properties of linear complexes, Mat. Sb. (N.S.) 24(66) (1949) 163–188, in Russian.
Close