Structure of the extremal family ex(n; TKp)

STRUCTURE OF THE EXTREMAL FAMILY EX ( n  TK p ) M. Cera, A. Dianez and P.G. Vazquez Given a p ositiveinteger p ,agraph G is said to contain an homeomorphic subgraph to the complete graph of order p , and it is denoted by G  TK p ,ifit is p ossible to nd p vertices f v 1 :::v p g and  p 2  pairwaise vertex disjoint paths joining these vertices in G . The study of the existence of complete homeomorphic subgraphs of order p in a graph of order n follows to the extremal problem consisting of determining the maximum numb er of edges ex ( n  TK p ) of a graph not containing to TK p . Mader 7] was the rst one in nding out an upperb ound for the function ex ( n  TK p ), proving that: ex ( n  TK p )  t ( p ) n   t ( p )+1 2  where n  t ( p )=3  2 p  3  p with p  4. Among the dierent attempts to improve this upp erb ound, we can stand out the recentworks of M. Cera, A. Dianez and A. Marquez 2] where it is proved that: ex ( n  TK p )   n 2   (2 n  2 p +1) and the upp erb ound ex ( n  TK p )  256 p 2 n found by B. Bollobas and A. Thomason in 1]. It is noted that the upp erb ound given by W. Mader as the one given by B. Bollobas and A. Thomason, both are b etter than the one given by M. Cera, A. Dianez and A. Marquez i.e., for the large value of n versus p . However, this last one is optimum for the neighb ouring values of n and p . The problem b ecomes more dicult if the ob jective is not only to limit but also to nd exact values for this extremal function. Since the trivial case ex ( n  TK 3 )= n  1 and the case ex ( n  TK 4 )=2 n  3proved by G. A. Dirac 5], we do not nd exact values up to the last years. So, W. Mader 8] has proved that ex ( n  TK 5 )=3 n  6, values conjectured by G.A. Dirac 5] in 1964, and more recently, in the last works from M. Cera, A. Dianez and A. Marquez 2] 3] 4], exact values of the function ex ( n  TK p )have been found for an innitynumber of values n and p , with n and p related by the expression d 2 n +3 3 e  p < n characterizing also the extremal family EX ( n  TK p ) for these cases, i.e., the 72 family of the graphs with n vertices, ex ( n  TK p ) edges and not containing to TK p . In this work, we will improve the showed upperb ound (in the sense prop osed bytheworks of M. Cera, A. Dianez and A. Marquez) and we will nd out exact values of the extremal function. In order to get these goals, we will previously obtain some results that are going to p ermit us to establish relationship values of the function ex ( n  TK p ) for n and p with n  p = constant .In fact, we will prove that: Result 1 ex ( n  1 TK p  1 )  ex ( n  TK p )  ( n  1) Furthermore, we will give a necessary and sucient condition to get that the previous inequality will be an equality: Result 2 These expressions areequivalent: 1. ex ( n  1 TK p  1 )= ex ( n  TK p )  ( n  1) 2. max f ( G ) =G 2 EX ( n  TK p ) g = n  1 where ( G ) denote the maximum degreeof G . Consequently,we obtain: Result 3  n 2   ex ( n  TK p )   n + j 2   ex ( n + j  TK n + j )   n + k 2   ex ( n + k  TK n + k ) for j =1 :::k  1 : All these results will p ermit us to nd out a new upp erb ound that improves the one given byM.Cera, A. Dianez and A. Marquez, for related values of n and p . Furthermore, we will nd exact values for the function ex ( n  TK p )for related n and p by d 2 n +1 3 e p< d 2 n +3 3 e . References 1] B. BOLLOBAS AND A. THOMASON, Pro of of a Conjecture of Mader, Erdos and Ha jnal on Top ological Complete Subgraphs, Europ ean J. Combinatorics, 19(1998), pp. 883-887. 2] M. CERA, A. DI  ANEZ AND A. M  ARQUEZ, The size of a graph whithout top ological complete subgraphs, SIAM J. Discrete Math., 13(2000), pp. 295-301. 73 3] M. CERA, A. DI  ANEZ AND A. M  ARQUEZ, Family of extremal graphs whithout top ological complete subgraphs, (enviado a SIAM Journal on Discrete Mathematics). 4] M. CERA, A. DI  ANEZ AND P.G. V  AZQUEZ, Exact values and extremal graphs for the function ex ( n  TK p )  submitted. 5] G. A. DIRAC, In abstrakten Graphen vorhandene vollstndige 4- Graphenund ihre Unterteilungen, Math. Nachr., 22(1960), pp. 61-85. 6] G. A. DIRAC, Homeomorphism theorem for graphs, Math. Ann., 153(1964), pp. 69-80. 7] W. MADER, Hinreichende Bedingungen f ur die Existenz von Teilgraphen, die zu einem vollstandigen Graphen homoomorph sind, Math. Nachr., 53(1972), pp. 145-150. 8] W. MADER, 3 n  5 do force a subdivision of K 5  Combinatorica 18(1998), no. 4, pp. 569-595. 74