Open Journal Systems

On the Halin Turán number of short cycles

Addisu Paulos

Abstract

A Halin graph is a graph constructed by embedding a tree with no vertex of degree two in the plane and then adding a cycle to join the tree’s leaves. The Halin Turán number of a graph F , denoted as exH(n, F ), is the maximum number of edges in an n-vertex Halin graph. In this paper, we give the exact value of exH(n, C4), where C4 is a cycle of length 4. We also pose a conjecture for the Halin Turán number of longer cycles.

Keywords

halin graphs; turán number; halin turán number

Full Text:

PDF

References

1. Turán P. On an external problem in graph theory. Matematikai és Fizikai Lapok,1941,48:436–452.

2. Mantel W. Problem 28. Wiskundige Opgaven, 10(60-61):320, 1907.

3. Erdös P, Stone AH. On the structure of linear graphs. Bulletin of the American Mathematical Society. 1946, 52(12): 1087-1091. doi: https://doi.org/10.1090/s0002-9904-1946-08715-7

4. Erdős P and Simonovits M. A limit theorem in graph theory. Studia Scientiarum Mathematicarum Hungarica, 1965.

5. Dowden C. ExtremalC4-Free/C5-Free Planar Graphs. Journal of Graph Theory. 2015, 83(3): 213-230. doi: https://doi.org/10.1002/jgt.21991

6. Lan Y, Shi Y, Song ZX. Extremal Theta-free planar graphs. Discrete Mathematics. 2019, 342(12): 111610. doi: https://doi.org/10.1016/j.disc.2019.111610

7. Ghosh D, Györi E, Martin RR, et al. Planar Turán Number of the 6-Cycle. SIAM Journal on Discrete Math- ematics. 2022, 36(3): 2028-2050. doi: https://doi.org/10.1137/21m140657x

8. Lan Y, Shi Y, and Song ZX. Planar Turán number and planar anti-Ramsey number of graphs. Operations Research Transactions, 25(3), 2021.

9. Cranston DW, Lidický B, Liu X, et al. Planar Turán Numbers of Cycles: A Counterexample. The Electronic Journal of Combinatorics. 2022, 29(3). doi: https://doi.org/10.37236/10774

10. Győri E, Varga K, and Zhu X. A new construction for planar Turán number of cycle. arXiv:2304.05584, 2023.

11. Lan Y and Song ZX. An improved lower bound for the planar Turán number of cycles. arXiv:2209.01312, 2022.

12. Fang L, Zhai M. Outerplanar Turán numbers of cycles and paths. arXiv:2110.10410, 2021.

13. Halin R. Studies on minimally n-connected graphs. Combinatorial Mathematics and its Applications, 129– 136, 1971.

14. Hazewinkel M. Encyclopedia of Mathematics: An Annotated translation of the “Soviet” Mathematical En- cyclopedia, 281–281.

15. Cornuéjols G, Naddef D, Pulleyblank WR. Halin graphs and the travelling salesman problem. Mathematical Programming. 1983, 26(3): 287-294. doi: https://doi.org/10.1007/bf02591867

16. Bondy JA, Lovász L. Lengths of cycles in halin graphs. Journal of Graph Theory. 1985, 9(3): 397-410. doi: https://doi.org/10.1002/jgt.3190090311

17. He S, Liu H. The maximum number of short paths in a Halin graph. Discrete Optimization. 2023, 50: 100809. doi: https://doi.org/10.1016/j.disopt.2023.100809


DOI: https://doi.org/10.59400/jam.v1i4.232
(62 Abstract Views, 48 PDF Downloads)

Refbacks

  • There are currently no refbacks.


Copyright (c) 2023 Addisu Paulos

License URL: http://creativecommons.org/licenses/by/4.0/


This site is licensed under a Creative Commons Attribution 4.0 International License.