Abstract | ||
---|---|---|
The Turan number of a graph H, ex ( n , H ), is the maximum number of edges in a graph of order n that does not contain a copy of H as a subgraph. LidickATIN SMALL LETTER Y WITH ACUTE, Liu and Palmer determined ex ( n , F k 1 , horizontal ellipsis , k m ) for sufficiently large n and proved that the extremal graph is unique, where F k 1 , horizontal ellipsis , k m is the union of pairwise vertex-disjoint paths on k 1 , horizontal ellipsis , k m vertices. There are a few kinds of graphs F for which ex ( n , F ) are known exactly for all n, including cliques, matchings, paths, cycles on odd number of vertices and some other special graphs. In this paper, using a different approach from LidickATIN SMALL LETTER Y WITH ACUTE, Liu and Palmer, we determine ex ( n , F k 1 , horizontal ellipsis , k m ) for all integers n when at most one of k 1 , horizontal ellipsis , k m is odd. Furthermore, we show that there exists a family of pairs of bipartite graphs ( F , G ) such that ex ( n , F ) = ex ( n , G ) for all integers n, which is related to an old problem of Erdos and Simonovits. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1002/jgt.22710 | JOURNAL OF GRAPH THEORY |
Keywords | DocType | Volume |
disjoint path, extremal graph, Turan number | Journal | 98 |
Issue | ISSN | Citations |
3 | 0364-9024 | 2 |
PageRank | References | Authors |
0.44 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Long-Tu Yuan | 1 | 2 | 0.44 |
Xiao-Dong Zhang | 2 | 97 | 19.87 |