Ahmet ÖTELEŞ, Diyar Omar Mustafa ZANGANA

Lucas Sayılarıyla İlişkili İki Parçalı Graflar

Bu çalışmada iki parçalı komşuluk matrisi n×n mertebeli (0,1)-circulant matrisi olan iki parçalı bir graf ele aldık. Daha sonra bu grafın mükemmel eşlemelerinin (1-factor) sayılarının Lucas sayıları ile arasındaki ilişkiyi verdik. Son olarak da bu mükemmel eşlemelerin sayısını hesaplamak için bazı maple prosedürleri verdik.

Anahtar Kelimeler:

Mükemmel eşleme, İki parçalı graf, Permanent, Fibonacci sayısı, Lucas sayısı

Bipartite Graphs Associated with Lucas Numbers

In this paper, we consider the bipartite graph whose bipartite adjacency matrix is an n×n (0,1)-circulant matrix. Then we show that the numbers of perfect matchings of this graph are equal to the well-known Lucas numbers. Finally, we give some Maple procedures in order to calculate the numbers of perfect matchings of the bipartite graph.

Keywords:

Fibonacci number, Lucas number, Perfect matching, bipartite graph, permanent, ,

PDF

___

Asratian, A. S., Denley, T. M. J. and Häggkvist, R. 1998. "Bipartite Graphs and their Applications", Cambridge Tracts in Mathematics, 131, Cambridge University Press.
Brualdi, R. A. and Gibson, P. M. 1977. "Convex polyhedra of doubly stochastic matrices I: applications of the permanent function", J. Combin. Theory, A 22, 194-230.
Brualdi, R. A. and Cvetkovic, D. 2009. "A Combinatorial Approach to Matrix Theory and Its Applications", CRC Press.
Fonseca, C. M. da, Sogabe, T. and Yilmaz, F. 2015. "Lower k-Hessenberg Matrices and k-Fibonacci, Fibonacci-p and Pell (p,i) Number", General Mathematics Notes, 31(1), 10-17.
Harary, F. 1969. "Determinants, permanents and bipartite graphs", Mathematics Magazine, 42, 146-148.
Kılıç, E. and Tasçı, D. 2007. "On the permanents of some tridiagonal matrices with applications to the Fibonacci and Lucas numbers", Rocky Mountain Journal of Mathematics, 37(6), 1953-1969.
Kılıç, E. and Tasçı, D. 2008. "On families of bipartite graphs associated with sums of Fibonacci and Lucas numbers", Ars Combinatoria, 89, 31-40.
Kılıç, E. and Stakhov, A. P. 2009. "On the Fibonacci and Lucas p-numbers, their sums, families of bipartite graphs and permanents of certain matrices", Chaos, Solitons&Fractals, 40(22), 10-21.
Koshy, T. 2001. "Fibonacci and Lucas Numbers with Applications", Wiley-Interscience, New York.
Koshy, T. 2011. "Fibonacci, Lucas, and Pell numbers, and Pascal's triangle", Mathematical Spectrum, 43(3), 125-132.
König, D. 1915. "Vonalrendszerek és determinások", Math. Termész. Ért., 33, 221-229.
König, D. 1916. "Über Graphen und ihre Anwendungen", Math. Annelen, 77, 453-465.
Lee, G. Y. and Lee, S. G. 1995. "A note on generalized Fibonacci numbers", The Fibonacci Quarterly, 33, 273-278.
Lee, G. Y., Lee, S. G. and Shin, H. G. 1997. "On the k-generalized Fibonacci matrix Q_{k}", Linear Algebra and its Applications, 251, 73-88.
Lee, G. Y. 2000. "k-Lucas numbers and associated bipartite graphs", Linear Algebra and its Applications, 320, 51-61.
Marcus, M. and Minc, H. 1965. "Permanents", American Mathematical Monthly, 72, 577-591.
Minc, H. 1978. "Permanents, Encyclopedia of mathematics and its applications", Addison-Wesley, New York.
Öteleş, A., 2017. "On the number of perfect matchings for some certain types of bipartite graphs", Filomat, 31(5), 4809-4818.
Özkan, E. and Altun, İ, M. 2019. "Generalized Lucas polynomials and relationships between the Fibonacci polynomials and Lucas polynomials", Communications in Algebra, 47(10), 4020-4030.
Özkan, E., Taştan, M. and Aydoğdu, A. 2018. "2-Fibonacci polynomials in the family of Fibonacci numbers", Notes on Number Theory and Discrete Mathematics, 24(3), 47-55.
Özkan, E. and Taştan, M. 2019. "k-Fibonacci Polynomials in The Family of Fibonacci Numbers", Research Reviews: Discrete Mathematical Structures, 6(3), 19-22.
Shiu, W. C. and Lam, P. C. B. 2003. "More on the generalized Fibonacci numbers and associated bipartite graphs", Int. Math., J., 3, 5-9.
The OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, http://oeis.org (Son Erişim Tarihi: 05.03.2020)
Wheland, G. W. 1953. "The Theory of Resonant and its Application to Organic Chemistry", Wiley, New York.
Yilmaz, F. and Bozkurt, D. 2012. "Some properties of Padovan sequence by matrix methods", Ars Combinatoria, 104, 149-160.