PDF

Discussiones Mathematicae Graph Theory 32(2) (2012) 271-278
DOI: https://doi.org/10.7151/dmgt.1601

Edge Maximal C_2k+1-edge Disjoint Free Graphs

M.S.A. Bataineh Department of Mathematics Yarmouk University Irbid-Jordan

M.M.M. Jaradat Yarmouk University Department of Mathematics Irbid-Jordan Department of Mathematics, Physics and Statistics Qatar University Doha-Qatar

Abstract

For two positive integers r and s, G(n;r,s) denotes to the class of graphs on n vertices containing no r of s-edge disjoint cycles and f(n;r,s) = max{E(G):G ∈ G(n;r,s)}. In this paper, for integers r ≥ 2 and k ≥ 1, we determine f(n;r,2k+1) and characterize the edge maximal members in G(n;r,2k+1).

Keywords: extremal graphs, edge disjoint, cycles

2010 Mathematics Subject Classification: 05C38, 05C35.

References

[1]	M.S. Bataineh, Some Extremal Problems in Graph Theory, Ph.D Thesis, Curtin University of Technology (Australia, 2007).
[2]	M.S. Bataineh and M.M.M. Jaradat, Edge maximal C3 and C5-edge disjoint free graphs, International J. Math. Combin. 1 (2011) 82--87.
[3]	J. Bondy, Large cycle in graphs, Discrete Math. 1 (1971) 121--132, doi: 10.1016/0012-365X(71)90019-7.
[4]	J. Bondy, Pancyclic graphs, J. Combin. Theory (B) 11 (1971) 80--84, doi: 10.1016/0095-8956(71)90016-5.
[5]	J. Bondy and U. Murty, Graph Theory with Applications (The MacMillan Press, London, 1976).
[6]	S. Brandt, A sufficient condition for all short cycles, Discrete Appl. Math. 79 (1997) 63--66, doi: 10.1016/S0166-218X(97)00032-2.
[7]	L. Caccetta, A problem in extremal graph theory, Ars Combin. 2 (1976) 33--56.
[8]	L. Caccetta and R. Jia, Edge maximal non-bipartite Hamiltonian graphs without cycles of length 5, Technical Report.14/97. School of Mathematics and Statistics, Curtin University of Technology (Australia, 1997).
[9]	L. Caccetta and R. Jia, Edge maximal non-bipartite graphs without odd cycles of prescribed length, Graphs and Combin. 18 (2002) 75--92, doi: 10.1007/s003730200004.
[10]	Z. Füredi, On the number of edges of quadrilateral-free graphs, J. Combin. Theory (B) 68 (1996) 1--6, doi: 10.1006/jctb.1996.0052.
[11]	R. Jia, Some Extremal Problems in Graph Theory, Ph.D Thesis, Curtin University of Technology (Australia, 1998).
[12]	P. Turán, On a problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436--452.

Received 27 August 2010
Revised 15 March 2011
Accepted 12 May 2011