Extremal number of theta graphs of order 7
Résumé
For a set of graphs F , let H(n; F ) denote the class of non-bipartite Hamiltonian graphs on n vertices that does not contain any graph of F as a subgraph and h(n; F ) = max{E (G) : G E H(n; F )} where E (G) is the number of edges in G. In this paper we determine h(n; {84, 85, 87}) and h(n; 87) for sufficiently odd large n. Our result confirms the conjecture made in [7] for k = 3.
Téléchargements
Références
M. Bataineh, ”Some extremal problems in graph theory”, Ph.D. thesis, Curtin University of Technology, Australia (2007).
M. Bataineh, M. M. M. Jaradat and E. Al-Shboul, Edge-maximal graphs without 5-graphs. Ars Combinatoria 124 (2016) 193-207.
M. Bataineh, M. M. M. Jaradat and E. Al-Shboul, Edge-maximal graphs without 7-graphs, SUT Journal of Mathematics, 47, 91-103 (2011).
M. S. A. Bataineh, M. M. M. Jaradat and I. Y. Al-Shboul, Edge-maximal graphs with-out theta graphs of order seven: Part II, Proceeding of the Annual International Conference on Computational Mathematics, Computational Geometry& Statistics. DOI#10.5176/2251-1911 CMCGS66.
J. A. Bondy, Pancyclic Graphs, J. Combinatorial Theory Ser B 11, 80- 84 (1971).
J. A. Bondy, Large cycle in graphs, Discrete Mathematics 1, 121- 132 (1971).
L. Caccetta and R. Jia, Edge maximal non-bipartite graphs without odd cycles of prescribed length, Graphs and Combinatorics, 18, 75-92 (2002).
L. Caccetta and K. Vijayan, Maximal cycles in graphs, Discrete Mathematics 98, 1-7 (1991).
R. Haggkvist, R.J. Faudree and R. H. Schelp, Pancyclic graphs – connected Ramsey number, Ars Combinatoria 11, 37-49 (1981).
G. R. T. Hendry and S. Brandt, An extremal problem for cycles in Hamiltonian graphs, Graphs Comb. 11, 255-262 (1995).
M. M. M. Jaradat, M.S. Bataineh and E. Al-Shboul, Edge-maximal graphs without 2k+1-graphs. Akce International Journal of Graphs and Combinatorics, 11 (2014) 57-65.
R. Jia, ”Some extermal problems in graph theory”, Ph.D. thesis, Curtin University of Technology, Australia (1998).
D. Woodall, Maximal Circuits of graphs I, Acta Math. Acad. Sci. Hungar. 28, 77-80 (1976).
Copyright (c) 2020 Boletim da Sociedade Paranaense de Matemática
Ce travail est disponible sous la licence Creative Commons Attribution 4.0 International .
When the manuscript is accepted for publication, the authors agree automatically to transfer the copyright to the (SPM).
The journal utilize the Creative Common Attribution (CC-BY 4.0).
