[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Extremal Graphs for Odd-Ballooning of Paths and Cycles

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

The odd-ballooning of a graph F is the graph obtained from F by replacing each edge in F by an odd cycle of length between 3 and \(q\ (q\ge 3)\) where the new vertices of the odd cycles are all different. Given a forbidden graph H and a positive integer n, the extremal number, ex(n, H), is the maximum number of edges in a graph on n vertices that does not contain H as a subgraph. Erdös et al. and Hou et al. determined the extremal number of odd-ballooning of stars. Liu and Glebov determined the extremal number of odd-ballooning of paths and cycles respectively when replacing each edge of the paths or the cycles by a triangle. In this paper we determine the extremal number and find the extremal graphs for odd-ballooning of paths and cycles, when replacing each edge of the paths or the cycles by an odd cycle of length between 3 and \(q \ (q \ge 3)\) and n is sufficiently large.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Chen, G., Gould, R., Pfender, F., Wei, B.: Extremal graphs for intersecting cliques. J. Combin. Theory Ser. B. 89(2), 159–171 (2003)

    Article  MathSciNet  Google Scholar 

  2. Erdős, P., Füredi, Z., Gould, R., Gunderson, D.: Extremal graphs for intersecting triangles. J. Combin. Theory Ser. B. 64(1), 89–100 (1995)

    Article  MathSciNet  Google Scholar 

  3. Glebov, R.: Extremal graphs for clique-paths. arXiv:1111.7029v1

  4. Hou, X., Qiu, Y., Liu, B.: Extremal graph for intersecting odd cycles. Electron. J. Combin. 23(2), P2.29 (2016)

    Article  MathSciNet  Google Scholar 

  5. Hou, X., Qiu, Y., Liu, B.: Turán number and decomposition number of intersecting odd cycles. Discrete Math. 341, 126–137 (2018)

    Article  MathSciNet  Google Scholar 

  6. Liu, H.: Extremal graphs for blow-ups of cycles and trees. Electron. J. Combin. 20(1), #P65 (2013)

    Article  MathSciNet  Google Scholar 

  7. Simonovits, M.: Extremal graph problems with symmetrical extremal graphs. Additional chromatic conditions. Discrete Math. 7(3–4), 349–376 (1974)

    Article  MathSciNet  Google Scholar 

  8. Turán, P.: On an extremal problem in graph theory. Mat. Fiz. Lapok. 48, 436–452 (1941)

    MathSciNet  Google Scholar 

  9. Turán, P.: On the theory of graphs. Colloquium Math. 3, 19–30 (1954)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We would like to thank referees for valuable comments and suggestions.

Author information

Authors and Affiliations

  1. Department of Mathematics, Shanghai University, Shanghai, 200444, People’s Republic of China

    Hui Zhu & Liying Kang

  2. School of Management, Shanghai University, Shanghai, 200444, People’s Republic of China

    Erfang Shan

Authors
  1. Hui Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Liying Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Erfang Shan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Erfang Shan.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Research was partially supported by NSFC (11871329, 11971298).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhu, H., Kang, L. & Shan, E. Extremal Graphs for Odd-Ballooning of Paths and Cycles. Graphs and Combinatorics 36, 755–766 (2020). https://doi.org/10.1007/s00373-020-02150-3

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-020-02150-3

Keywords

Mathematical Subject Classification