GRAF MATRİSLERİ VE ENERJİ Çilem YAMAÇ T. C. BURSA ULUDAĞ ÜNİVERSİTESİ FEN BİLİMLERİ ENSTİTÜSÜ GRAF MATRİSLERİ VE ENERJİ Çilem YAMAÇ 0000-0001-6044-1578 Prof. Dr. İ. Naci CANGÜL (Danışman) 0000-0002-0700-5774 YÜKSEK LİSANS TEZİ MATEMATİK ANABİLİM DALI BURSA–2019 Her Hakkı Saklıdır TEZ ONAYI Çilem YAMAÇ tarafından hazırlanan “Graf Matrisleri ve Enerji” adlı tez çalışması aşağıdaki jüri tarafından oy birliği/oy çokluğu ile Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalı’nda YÜKSEK LİSANS TEZİ olarak kabul edilmiştir. Danışman : Prof. Dr. İ. Naci CANGÜL Başkan: Prof. Dr. İ. Naci CANGÜL İmza 0000-0002-0700-5774 Bursa Uludağ Üniversitesi Fen-Edebiyat Fakültesi Matematik Anabilim Dalı Üye: Doç. Dr. Musa DEMİRCİ İmza 0000-0002-6439-8439 Bursa Uludağ Üniversitesi Fen-Edebiyat Fakültesi Matematik Anabilim Dalı Üye: Prof. Dr. Sebahattin İKİKARDEŞ İmza 0000-0003-2924-5397 Balıkesir Üniversitesi Fen-Edebiyat Fakültesi Matematik Anabilim Dalı Yukarıdaki sonucu onaylarım Prof. Dr. Hüseyin Aksel EREN Enstitü Müdürü B.U.Ü. Fen Bilimleri Enstitüsü, tez yazım kurallarına uygun olarak hazırladığım bu tez çalışmasında; • tez içindeki bütün bilgi ve belgeleri akademik kurallar çerçevesinde elde ettiğimi, • görsel, işitsel ve yazılı tüm bilgi ve sonuçları bilimsel ahlak kurallarına uygun olarak sunduğumu, • başkalarının eserlerinden yararlanılması durumunda ilgili eserlere bilimsel normlara uygun olarak atıfta bulunduğumu, • atıfta bulunduğum eserlerin tümünü kaynak olarak gösterdiğimi, • kullanılan verilerde herhangi bir tahrifat yapmadığımı, • ve bu tezin herhangi bir bölümünü bu üniversite veya başka bir üniversitede başka bir tez çalışması olarak sunmadığımı beyan ederim. 26/09/2019 İmza Çilem YAMAÇ ÖZET Yüksek Lisans Tezi GRAF MATRİSLERİ VE ENERJİ Çilem YAMAÇ Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü Matematik Anabilim Dalı Danışman: Prof. Dr. İsmail Naci CANGÜL (Bursa Uludağ Üniversitesi) Bu çalışmanın amacı bazı graf matrisleri yardımıyla çeşitli graf sınıflarının karakteristik polinomlarının hesaplanması ve ayrıca kenar-Zagreb indekslerinin bulunmasıdır. Bu tez dört bölümden oluşmaktadır. Birinci bölüm giriş bölümüdür. Temel tanım ve kavramlar ile sonraki bölümlerde kullanılacak bazı önemli sonuçlar burada verilmiştir. İkinci bölümde graflarda kenar komşuluğu kavramı yardımıyla kenar komşuluk matrisleri tanımlanmış ve bunlara karşılık gelen karakteristik polinomlar elde edilmiştir. Üçüncü bölümde bitişiklik matrisleri ve polinomları çalışılmış, dördüncü ve son bölümde ise kenar kavramına bağlı olarak tanımlanan ve köşe kavramına bağlı olarak tanımlanan haline oranla daha az çalışılmış olan kenar-Zagreb indeksleri ele alınmıştır. Anahtar Kelimeler: Graf, graf indeksi, kenar-Zagreb matrisi, kenar-Zagreb indeksi 2019, vi + 38 sayfa. i ABSTRACT MSc Thesis GRAPH MATRICES AND ENERGY Çilem YAMAÇ Bursa Uludağ University Graduate School of Natural and Applied Sciences Department of Mathematics Supervisor: Prof. Dr. Ismail Naci CANGUL (Bursa Uludag University) The aim of this study is to calculate characteristic polynomials of several graph classes by means of some graph matrices and also to find edge-Zagreb indices. There are four chapters in this thesis. In the first chapter, there is introduction to the thesis. Fundamental definitions and notions together with some important results which are necessary in the following chapters. In the second chapter, the edge-adjacency matrices are defined by means of the edge-adjacency idea and also the corresponding characteristic polynomials are obtained. In the third chapter, the incidency matrices and polynomials are considered, and in the fourth chapter, the edge-Zagreb indices which have been studied relatively less compared with the vertex-based counterpart are studied. Key Words: Graph, graph index, edge-Zagreb matrix, edge-Zagreb index 2019, vi + 38 page ii ÖNSÖZ VE TEŞEKKÜR Yüksek lisans eğitimim boyunca güleryüzü ile destek veren, cesaretlendiren sözleri ile daima yanımda olan, tavsiye ve deneyimleriyle bana yol gösteren değerli hocam Prof. Dr. İsmail Naci CANGÜL’e; ve desteklerini hiçbir zaman esirgemeyen, benim için her türlü fedakarlığı yapan, başarıya ulaşacağıma beni inandıran canım aileme, sonsuz teşekkürler… Çilem YAMAÇ 26/09/2019 iii İÇİNDEKİLER Sayfa ÖZET ……………………………………………………………………………. i ABSTRACT ……………………………………………………………………... ii ÖNSÖZ VE TEŞEKKÜR ………………………………………………………... iii İÇİNDEKİLER …………………………………………………………………... iv SİMGELER DİZİNİ …………………………………………………………….. v ŞEKİLLER DİZİNİ …………………………………………………………….. vi 1. GİRİŞ ………………………………………………………………………….. 1 2. MATERYAL VE YÖNTEM ………………………………………………….. 7 3. GRAFLARDA KENAR KOMŞULUĞU …………………………………….. 8 4. BİTİŞİKLİK MATRİSLERİ VE POLİNOMLARI ………………………….. 23 5. GRAFLARIN KENAR-ZAGREB MATRİSLERİ VE POLİNOMLARI …….26 KAYNAKLAR ………………………………………………………………….. 37 ÖZGEÇMİŞ …………………………………………………………………..... 38 iv SİMGELER DİZİNİ Simgeler Açıklama G Graf V(G) G grafının köşe kümesi E(G) G grafının kenar kümesi 𝑑(𝑢) u köşesinin derecesi 𝐾𝑛 n köşeli tam graf 𝐶𝑛 n köşeli devir grafı 𝑃𝑛 n köşeli yol grafı 𝑆𝑛 n köşeli yıldız grafı 𝑇𝑛 n köşeli ağaç grafı 𝐾𝑟,𝑠 Tam iki parçalı graf Tr, s r+s köşeli larva grafı v ŞEKİLLER DİZİNİ Şekil 1.1. Pregel Nehri ...................................................................................................... 1 Şekil 1.2. Königsberg grafı………………………………………………………………2 Şekil 1.3. 5 köşeli ve 7 kenarlı graf örneği………………………………………………2 Şekil 1.4. Düzenli graf…………………………………………………………………...3 Şekil 1.5. P5 yol grafı ........................................................................................................ 4 Şekil 1.6. C4 Devir Grafı……………………………………………………………….. 4 Şekil 1.7. S7 yıldız grafı …………………………………………………………………4 Şekil 1.8. K5 tam grafı…………………………………………………………………...5 Şekil 1.9. K2,3 tam iki parçalı grafı………………………………………………………5 Şekil 1.10. T4,3 larva grafı………………………………………………………………..6 Şekil 3.1. G grafı………………………………………………………………………....6 Şekil 3.2.Aynı komşuluk matrisine sahip izomorfik olmayan iki graf…………………..6 vi 1. GİRİŞ Graf Teorinin 1736 yılında Euler’in (1707-1783) yazdığı bir makale ile başladığı düşünülmektedir. Bu makale Königsberg Köprü Problemini çözebilen bir teoriyi içeriyordu. Königsberg kasabasının içinden akan Pregel nehrinin ortasında nehrin kıyılarına ve birbirine Şekil 1.1’deki gibi köprüler ile bağlı bir ada ve yarımada bulunmaktadır. Şekil 1.1. Pregel Nehri Buradaki problem ‘Kıyıların veya adaların birinden başlayıp tüm köprülerden sadece birer kez geçerek başladığımız yere dönebilir miyiz? şeklindedir. Euler bu problemi aşağıdaki grafa dönüştürerek problemin çözümünün olmadığını göstermiştir. Bu graf ile verilen problem ‘Grafın tüm ayrıtlarını içeren kapalı bir yol var mıdır?’ haline dönüşmüştür. 1 Şekil 1.2. Königsberg grafı Aşağıdaki kısımda bu tezde kullanılacak olan bazı temel kavramları tanıyacağız. Bu kavramlarla ilgili daha geniş bilgi için Balakrishnan ve Ranganathan (2012), Berge (2001), Biggs ve Ark. (1986), Bondy ve Murty (2008), Bollobas (1998), West (1996), Chen (1976), Harary (1994), Foulds (1992), Golumbic ve Hartman (2005) ve Harris ve Ark. (2008) kaynaklarına başvurulabilir. 1.1. Tanım. V sonlu kümesinin elemanları köşeler (vertex) ve E sonlu kümesinin elemanları kenarlar (edge) olmak üzere kenar ve köşelerin sıralı olmayan ikililerini eleman kabul eden yapıya graf denir ve 𝐺 = (𝑉, 𝐸) ile gösterilir. a e1 e2 b e e3 e4 e7 e6 c e5 d Şekil 1.3. 5 köşeli ve 7 kenarlı bir graf örneği 2 Şekil 1.3.’de verilen graf örneğinin köşe kümesi V(G) = { a, b, c, d, e } ve kenar kümesi E(G) = { e1, e2, e3, e4, e5, e6, e7 } ’dir. 1.2. Tanım. Bir 𝐺 grafında bir 𝑢 köşesini uç kabul eden kenar sayısına 𝑢 köşesinin derecesi (degree) denir ve 𝑑(𝑢) ile gösterilir. Örneğin Şekil 1.3.’de 𝑑(𝑎) = 2 ve 𝑑(𝑏) = 4’tür. 1.3. Tanım. Bir 𝐺 grafında bulunan 𝑣 köşesi için 𝑑𝑒𝑟(𝑣) = 1 ise bu köşeye asılı veya sallanan köşe (pendant vertex); buna bitişik olan kenara da asılı veya sallanan kenar (pendant edge) denir. 1.4. Tanım. Bir 𝐺 grafında bütün köşe dereceleri aynı ise bu grafa düzenli (regular) graf denir. Bir 𝐺 grafının bütün köşelerinin dereceleri n ise bu grafa n-düzenli (n-regular) graf denir. Şekil 1.4. 2-düzenli graf 1.5. Tanım. Bir 𝐺 = (𝑉, 𝐸) grafının bazı köşeleri 𝑣1, 𝑣2,… , 𝑣𝑘 є 𝑉 olsun. 𝑖 = 1,2, … , 𝑘 için 𝑣𝑖𝑣𝑖+1 є 𝐸 dizisine 𝐺 grafının bir yolu (walk) denir. Eğer bir yolun tüm köşeleri farklıysa bu yola patika (path) denir. 𝑛 köşeli bir patika Pn ile gösterilir. Şekil 1.5. 𝑃5 yol grafı Tez boyunca patika için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 2 alınacaktır. 3 1.6. Tanım. 𝑛 köşeye sahip bir 𝐺 grafı kapalı bir patika ise, yani başlangıç ve bitiş noktaları aynıysa, bu grafa devir (cycle) graf denir ve Cn ile gösterilir. Şekil 1.6. 𝐶4 devir grafı Tez boyunca devir graf için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 3 alınacaktır. Çünkü 𝑛 = 1 ve 𝑛 = 2 için 𝐶𝑛 = 𝑃𝑛’dir. 1.7. Tanım. Merkezdeki bir köşenin diğer tüm köşelere bağlandığı bir grafa yıldız (star) graf denir ve Sn ile gösterilir. 𝑆𝑛 grafında merkezdeki köşenin derecesi 𝑛 − 1, diğer köşelerin dereceleri 1 olur. Şekil 1.7. 𝑆7 yıldız grafı Tez boyunca yıldız graf için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 4 alınacaktır. Çünkü 𝑛 = 1,2,3 için 𝑆𝑛 = 𝑃𝑛’dir. 1.8. Tanım. Bir 𝐺 grafındaki 𝑛 köşenin her biri diğer köşelerin hepsi ile birer kenar oluşturuyorsa bu grafa tam (complete) graf denir ve Kn ile gösterilir. 4 Şekil 1.8. K5 tam grafı Tez boyunca tam graf için 𝑛 köşe sayısı olmak üzere 𝑛 ≥ 4 alınacaktır. Çünkü 𝑛 = 1 ve 𝑛 = 2 için 𝐾𝑛 = 𝑃𝑛 ve 𝑛 = 3 için 𝐾𝑛 = 𝐶𝑛’dir. 1.9. Tanım. Bir 𝐺 grafının köşe kümesi 𝐴 ve 𝐵 gibi iki alt köşe kümesine ayrılabiliyor ve 𝐴 (𝑣𝑒𝑦𝑎 𝐵) kümesindeki bir köşe sadece 𝐵 (𝑣𝑒𝑦𝑎 𝐴) kümesindeki bir köşe veya köşeler ile birleşiyorsa bu grafa iki parçalı (bipartite) graf denir. Eğer 𝐴 (𝑣𝑒𝑦𝑎 𝐵) kümesindeki her köşe 𝐵 (𝑣𝑒𝑦𝑎 𝐴) kümesindeki her bir köşeyle birleşiyorsa bu grafa da tam iki parçalı (complete bipartite) graf denir ve 𝐴 kümesinin eleman sayısı 𝑟, 𝐵 kümesinin eleman sayısı 𝑠 olmak üzere Kr,s ile gösterilir. Şekil 1.9. 𝐾2,3 tam iki parçalı grafı İki parçalı graflarda 𝐴 ve 𝐵 kümelerindeki köşelerin iki farklı renkle gösterilmesi alışılmış bir uygulamadır. Tez boyunca 𝑟 ve 𝑠 köşe sayıları olmak üzere 2, 𝑟 = 2 𝑖𝑘𝑒𝑛 𝑠 = { ≥ 𝑟, 𝑟 > 2 𝑖𝑘𝑒𝑛 5 alınacaktır. 1.10. Tanım. Bir 𝐺 grafının köşe kümesi 𝐴 ve 𝐵 gibi iki alt köşe kümesine ayrılabilirse ve 𝐴 kümesindeki köşeler bir devir oluştururken, 𝐵 kümesindeki köşeler bir patika oluşturuyorsa ve bu devirin bir köşesi ile patikanın bir uç köşesi ortak ise bu grafa larva (tadpole) graf denir. Devir kısmındaki köşe sayısı 𝑟, patika kısmındaki köşe sayısı 𝑠 olan bir larva graf Tr,s ile gösterilir. Şekil 1.10. 𝑇4,3 larva grafı Tez boyunca 𝑟 ≥ 3 ve 𝑠 ≥ 1 alınacaktır. Çünkü diğer durumlarda 𝑇𝑟,𝑠 = 𝑃𝑟+𝑠 olur. 1.11. Tanım. Bir 𝐺 bağlantılı grafında, bir e kenarı ile bağlanan 𝑢 ve 𝑣 köşelerine komşu (adjacent) denir ve 𝑒 = 𝑢𝑣 ile gösterilir. 1.12. Tanım. 𝐺 bağlantılı bir graf olmak üzere 𝑢 ve 𝑣 köşeleri bir 𝑒 kenarı ile bağlantılı olsunlar. Bu 𝑒 kenarı 𝑢 ve 𝑣 köşelerine bitişiktir (incident) denir. 1.13. Tanım. Bir 𝐺 grafına ait komşuluk matrisinin tüm özdeğerlerinin kümesine G grafının spektrumu denir. 1.14. Tanım. 𝐴 matrisi bir 𝐺 grafına ait komşuluk matrisi olmak üzere |𝐴 − 𝜆𝐼𝑛| = 0 ifadesinin kökleri olan 𝜆1, 𝜆2, ⋯, 𝜆𝑛sayılarına 𝐴 matrisinin özdeğerleri denilir. Eşitliğin sol tarafı ile elde edilen polinoma 𝐺 grafının karakteristik polinomu denir. 1.15. Tanım. Bir 𝐺 bağlantılı grafında bir 𝑣 köşesine bitişik olan iki 𝑒, 𝑓 kenarına komşu (adjacent) kenarlar denilir. 6 2. MATERYAL VE YÖNTEM Lineer cebir, matematiğin Soyut Cebir ve Sayılar Teorisi alt dalının en önemli çalışma alanlarından birisidir. Lineer cebir yöntemleri, matematiğin ve uygulamalarının var olduğu tüm bilim alanlarının vaz geçilmez yöntemleri arasındadır. Herhangi bir matrisin determinantı yardımıyla oluşturulan karakteristik polinomun kökleri bize verilen matrisin öz değerleri adı verilen bazı sayıları vermektedir. Eğer verilen matris bir graf matrisi ise, bu öz değerlerin mutlak değerleri toplamı, graf enerjisi adı verilen ve birçok uygulamaları olan bir kavramı doğurmaktadır. Farklı graf matrislerine bağlı olarak farklı graf enerjileri tanımlanmıştır. Bu tezde lineer cebir metotları ve sonuçları kullanılarak bazı graf matrisleri yardımıyla çeşitli graf enerjileri çalışılmıştır. Bu enerjileri elde edebilmek için verilen matrislerin determinantları, satır-sütun operasyonları ve determinant özellikleri kullanılarak hesaplanmış, elde edilen karakteristik polinomların kökleri, yani öz değerler bulunarak bunlarla ilgili var olan sonuçlardan yararlanarak sonuçlar elde edilmiştir. Graf enerjisi ile ilgili sonuçların elde edilmesinde aynı zamanda graf teorinin ve kombinatorik teorinin temel bazı sonuçlarından ve yöntemlerinden faydalanılmıştır. 7 3. GRAFLARDA KENAR KOMŞULUĞU Bu bölümde en popüler graf matrisi olan komşuluk matrisine benzer olarak bir grafın kenar-komşuluk matrisini tanımlayacağız ve özelliklerini inceleyeceğiz. Bu bölümde elde edilen sonuçlar Yamaç ve Ark. (2018) ve Öz ve Ark. (2019)’da yayınlanmıştır. İlk olarak bir grafın komşuluk matrisi kavramını hatırlayalım. Tanım 3.1. 𝐺 grafı 𝑛 köşeli ve 𝑚 kenarlı bağlantılı bir basit graf olsun. 𝐴= [𝑎𝑖𝑗] 𝑛×𝑛 biçiminde gösterilen ve 1, 𝑣𝑖 𝑣𝑒 𝑣𝑗 𝑘öş𝑒𝑙𝑒𝑟𝑖 𝑘𝑜𝑚ş𝑢 𝑖𝑠𝑒 𝑎𝑖𝑗 = { 0, 𝑣𝑖 𝑣𝑒 𝑣𝑗 𝑘öş𝑒𝑙𝑒𝑟𝑖 𝑘𝑜𝑚ş𝑢 𝑑𝑒ğ𝑖𝑙 𝑖𝑠𝑒 şeklinde tanımlanan 𝑛 × 𝑛 boyutlu bir kare matrise 𝐺 grafının köşe-komşuluk matrisi denir. Komşuluk matrisi graf teori ve moleküler kimyada birçok alanda kullanılır. Komşuluk matrisine ait öz değerlerin mutlak değerlerinin toplamı bir grafının enerjisini verir. Enerji kavramı, graf teoride birçok kimyasal yorumlamaya sahip olduğundan oldukça kullanışlı ve geniş uygulama alanına sahip bir kavramdır. Bu yüzden komşuluk matrisi ve komşuluk ile ilgili notasyonlar birçok alanda sıklıkla kullanılır. Bu tezde komşuluk matrisine alternatif olarak tanımlanan benzeri birkaç matris ile çalışacağız. Örnek 3.1. Şekil 3.1’deki 𝐺 grafını ele alalım. Şekil 3.1. Bir 𝑮 grafı 8 Bu 𝐺 grafının komşuluk matrisi 0 1 0 0 0 0 0 0 0   1 0 1 0 0 0 0 0 0   0 1 0 1 1 0 0 0 1   0 0 1 0 1 0 0 0 0 𝐴 = 0 0 1 1 0 1 0 0 0   0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 1 0   0 0 0 0 0 0 1 0 1  0 0 1 0 0 0 0 1 0   şeklindedir. Şimdi komşuluk matrisinin en önemli benzeri olan kenar-komşuluk matrisini tanımlayacak ve özelliklerini inceleyeceğiz. Hatırlanacağı gibi komşuluk matrisinde köşelerin birbirlerine komşu olup olmamalarına göre hareket edilmekteydi. Kenar- komşuluk matrisinde ise, görüleceği gibi kenarların birbirine komşu olmalarına göre hareket edilecektir. Tanım 3.2. 𝐺 grafı 𝑛 köşeli ve 𝑚 kenarlı bağlantılı bir basit graf olsun. 𝐺 grafının kenar- komşuluk matrisi 1, 𝑒𝑖 𝑣𝑒 𝑒𝑗 𝑘𝑒𝑛𝑎𝑟𝑙𝑎𝑟𝚤 𝑘𝑜𝑚ş𝑢 𝑖𝑠𝑒 𝑎𝑖𝑗 = { 0, 𝑒𝑖 𝑣𝑒 𝑒𝑗 𝑘𝑒𝑛𝑎𝑟𝑙𝑎𝑟𝚤 𝑘𝑜𝑚ş𝑢 𝑑𝑒ğ𝑖𝑙 𝑖𝑠𝑒 olmak üzere 𝐴𝑒 = [𝑎𝑖𝑗] biçiminde tanımlanan bir 𝑚 ×𝑚 kare matrisidir. 𝑚×𝑚 Örnek 3.2. Şekil 3.1’de 10 tane isimlendirilmiş kenara sahip bir 𝐺 grafı ve altında da bu grafa ait kenar-komşuluk grafı verilmiştir. Bu grafın kenar-komşuluk matrisi 9 0 1 0 0 0 0 0 0 0 0   1 0 1 0 1 0 0 0 0 1   0 1 0 1 1 0 0 0 0 1   0 0 1 0 1 1 0 0 0 0 0 1 1 1 0 1 0 0 0 1 𝐴𝑒 =   0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0   0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1   0 1 1 0 1 0 0 0 1 0 şeklindedir. İzomorfik olmayan grafların komşuluk matrisleri farklı olmasına rağmen, kenar- komşuluk matrisleri aynı olabilir. Örneğin Şekil 3.2’deki grafların ikisi de aynı kenar- komşuluk matrisine sahiptir. 0 1 1 1 1 0 1 1 | | 1 1 0 1 1 1 1 0 Şekil 3.2. Aynı komşuluk matrisine sahip, izomorfik olmayan iki graf Literatürde bir 𝐺 grafı ile ilgili bir karakteristik özellikten, özdeğerlerden veya enerjiden bahsedildiğinde, 𝐴(𝐺) komşuluk matrisi ile çalışıldığı varsayılır. Başka bir matris kullanıldığında bu durum kesinlikle belirtilmelidir ve bu durumda kavramlar da uygun şekilde adapte edilmelidir. Örneğin kenar-komşuluk matrisiyle çalışıldığında elde edilen enerji artık kenar-komşuluk enerjisi olarak adlandırılacaktır. 10 Bu çalışmada 𝐴𝑒 kenar-komşuluk matrisi ile ilgili karakteristik polinomlar ele alınmıştır. Kenar-komşuluk matrisinin karakteristik polinomunun hesaplanmasıyla elde edilen kenar-karakteristik polinomunu komşuluk karakteristik polinomundan ayırt etmek için 𝑃𝑒𝐺 (𝜆) ile göstereceğiz. Burada literatürde çok sık kullanılan bazı graf sınıfları için kenar- karakteristik polinomunu inceleyeceğiz. İlk olarak 𝑃𝑛 patika grafı ele alınacaktır. Teorem 3.1. 𝑃𝑛 patika grafının kenar-komşuluk matrisi kullanılarak elde edilen kenar- karakteristik polinomu için indirgeme bağıntısı 𝑃𝑒𝑃 (λ) = λ𝑃 𝑒 (λ) - 𝑃𝑒 (λ) 𝑛 𝑃𝑛−1 𝑃𝑛−2 şeklindedir. İspat. 𝑃𝑛 patika grafının kenar-komşuluk matrisi 0 1 0 0 0 0 0 0   1 0 1 0 0 0 0 0   0 1 0 1 0 0 0 0   𝑒 0 0 1 0 1 0 0 0𝐴 (𝑃𝑛) =        0 0 0 0 0 1 0 1   0 0 0 0 0 0 1 0 ve karakteristik polinomu  −1 0 0 0 0 0 0 −1  −1 0 0 0 0 0 0 −1  −1 0 0 0 0 𝑒 0 0 −1  −1 0 0 0 |𝜆 ∙ 𝐼 − 𝐴 (𝑃𝑛)| = 0 0 0 0 0 −1  −1 0 0 0 0 0 0 −1  11 dir. Bu determinantı birinci satıra göre açarsak, −1 −1 0 0 0 0 0 0 0  −1 0 0 0 0 0 0 −1  −1 0 0 0 0 𝑒 0 0 −1  −1 0 0 0|𝜆 ∙ 𝐼 − 𝐴𝑒(𝑃𝑛)| = 𝜆𝑃𝑃 (𝜆) + 1 𝑛−1 0 0 0 0 0 −1  −1 0 0 0 0 0 0 −1  = 𝜆𝑃𝑒𝑃 (𝜆) − 𝑃 𝑒 𝑃 (𝜆) 𝑛−1 𝑛−2 ve son determinantı birinci sütuna göre açtığımızda istenen eşitlik elde edilir. Patika graflara ait ilk birkaç kenar-karakteristik polinom indirgeme bağıntısından kolayca elde edilebilir: 𝑃𝑒𝑃 (λ) = 𝜆 2 −1 3 𝑃𝑒𝑃 (λ) = 𝜆 3 − 2λ 4 𝑃𝑒𝑃 (λ) = 𝜆 4 −3𝜆2 − 1 5 𝑃𝑒 (λ) = 𝜆5 − 4𝜆3𝑃 + 3𝜆. 6 Öncelikle 𝑃𝑛 patika grafına ait kenar-karateristik polinomu için bir formül elde edeceğiz. Bunun için ilk olarak aşağıdaki sonuca ihtiyaç duyulmaktadır. Lemma 3.1. 𝑘 ≤ 𝑛 özelliğindeki tüm 𝑘 ve 𝑛 pozitif tamsayıları için 𝑛 𝑛 𝑛 + 1 ( ) + ( ) = ( ) 𝑘 𝑘 − 1 𝑘 eşitliği sağlanır. 12 İspat. Kombinasyon sayılarının kombinatorik özellikleri kullanılarak aşağıdaki şekilde sonuca ulaşılır: 𝑛 𝑛 𝑛! 𝑛! ( ) + ( ) = + 𝑘 𝑘 − 1 (𝑛 − 𝑘)! 𝑘! (𝑛 − 𝑘 + 1)! (𝑘 − 1)! 𝑛! (𝑛 + 1) = (𝑛 − 𝑘 + 1)! 𝑘! 𝑛 + 1! = (𝑛 + 1 − 𝑘)! 𝑘! 𝑛 + 1 = ( ) 𝑘 𝑛−1 ∑ 2 (−1)𝑙(𝑛−1−𝑙 𝑙=0 )𝜆 𝑛−1−2𝑙 , 𝑛 𝑡𝑒𝑘 𝑖𝑘𝑒𝑛 𝑙 Teorem 3.2. 𝑃𝑒𝑃 (𝜆) = 𝑛 𝑛−2 { ∑ 2 (−1)𝑙(𝑛−1−𝑙𝑙=0 )𝜆 𝑛−1−2𝑙 , 𝑛 ç𝑖𝑓𝑡 𝑖𝑘𝑒𝑛. 𝑙 İspat. Kuvvetli tümevarım kullanalım. 𝑛 tek olsun. 𝑃𝑒 = 𝜆2𝑃 − 1 3 2 = (−1)0 ( ) 𝜆2 + (−1)1 1 ( ) 𝜆0 0 1 3−1 3 = ∑ 2 (𝑙=0 −1) 𝑙(3−1−𝑙)𝜆−1−2𝑙. 𝑙 Bu durum 3,4,5, … , 𝑛 − 1, 𝑛 için doğru olsun. Biz bu durumun 𝑛 + 1 için doğru olduğunu ispatlamak istiyoruz. Tümevarım hipotezinden dolayı, 𝑛−1 𝑛−3 ∑ 2 (−1)𝑙(𝑛−1−𝑙)𝜆𝑛−1−2𝑙 ve ∑ 2 (−1)𝑙(𝑛−2−𝑙)𝜆𝑛−1−2𝑙𝑙=0 𝑙=0 𝑙 𝑙 olduğunu biliyoruz. Lemma 3.1’den dolayı 𝑃𝑒𝑃 = 𝜆𝑃 𝑒 (𝜆) − 𝑃𝑒 𝑛+1 𝑃𝑛 𝑃 (𝜆) 𝑛−1 13 𝑛−1 𝑛−3 2 2 𝑛 − 1 − 𝑙 𝑛 − 2 − 𝑙 = 𝜆 ∑(−1)𝑙 ( ) 𝜆𝑛−1−2𝑙 −∑(−1)𝑙 ( ) 𝜆𝑛−2−2𝑙 𝑙 𝑙 𝑙=0 𝑙=0 ( ) 𝑛−1 = 𝜆[(−1)0( )𝜆𝑛−1 + (−1)1(𝑛−2)𝜆𝑛−3+(−1)2(𝑛−3)𝜆𝑛−5 + (−1)3(𝑛−4)𝜆𝑛−7 0 1 2 3 𝑛−1 𝑛−1𝑛−1− +⋯+ (−1) ( 2 )𝜆0] − [ (−1)0(𝑛−2)𝜆𝑛−2 + (−1)1(𝑛−32 )𝜆𝑛−4𝑛−1 +0 1 2 𝑛−3 𝑛−3 (−1)2(𝑛−4)𝜆𝑛−6 + (−1)3(𝑛−5)𝜆𝑛−8 𝑛−2− +⋯+ (−1) 2 ( 2 )𝜆1 2 3 𝑛−3 2 𝑛 − 1 𝑛 − 1 𝑛 − 1 𝑛−1 𝑛 − = (−1)0 ( ) 𝜆𝑛 2 + (−1)1 ( ) 𝜆𝑛−2 +⋯+ (−1) 2 ( 𝑛 − 1 ) 0 1 2 𝑛−1 2 𝑛 − 𝑙 = ∑(−1)𝑙 ( ) 𝜆𝑛−2𝑙 𝑙 𝑙=0 elde edilir. Şimdi 𝑛 çift olsun. 𝑃𝑒 3𝑃 = 𝜆 − 2𝜆 4 3 2 = (−1)0 ( ) 𝜆3 + (−1)1 ( ) 𝜆 0 1 4−2 4−1−𝑙 = ∑ 2𝑙=0(−1) 𝑙 ( )𝜆4−1−2𝑙. 𝑙 Bu durum 3,4,5, … , 𝑛 − 1, 𝑛 için doğru olsun. Biz bu durumun 𝑛 + 1 için doğru olduğunu ispatlamak istiyoruz. Tümevarım hipotezinden dolayı 𝑛−2 𝑛−2 ∑ 2 (−1)𝑙(𝑛−1−𝑙)𝜆𝑛−1−2𝑙 ∑ 2 (−1)𝑙(𝑛−2−𝑙 ve )𝜆𝑛−2−2𝑙𝑙=0 𝑙 𝑙=0 𝑙 olduğunu biliyoruz. Lemma 3.1’den dolayı 14 𝑃𝑒 = 𝜆𝑃𝑒 (𝜆) − 𝑃𝑒𝑃 𝑃 𝑃 (𝜆) 𝑛+1 𝑛 𝑛−1 𝑛−2 𝑛−2 2 2 𝑛 − 1 − 𝑙 𝑛 − 2 − 𝑙 = 𝜆 ∑(−1)𝑙 ( ) 𝜆𝑛−1−2𝑙 − ∑(−1)𝑙 ( ) 𝜆𝑛−2−2𝑙 𝑙 𝑙 𝑙=0 𝑙=0 ( ) ( ) 𝑛 − 2 𝑛 2 = ( )0 𝑛 − 1 𝑛 − 1 −1 ( ) 𝜆𝑛 + (−1)1 ( ) 𝜆𝑛−2 +⋯++(−1)2 ( 0𝑛 − 2)𝜆 0 1 2 𝑛 𝑛 𝑛 − 1 𝑛 = (−1)0 ( ) 𝜆𝑛 + (−1)1 ( ) 𝜆𝑛−2 +⋯++(−1) 22 (𝑛)𝜆 0 0 1 2 𝑛 2 𝑛 − 𝑙 =∑(−1)𝑙 ( ) 𝜆𝑛−2𝑙 𝑙 𝑙=0 elde edilir. Teorem 3.3. 𝐶𝑛 devir grafının kenar-komşuluk matrisiyle elde edilen kenar-karakteristik polinomunun indirgeme bağıntısı 𝑃𝑒𝐶 (λ) = λ𝑃 𝑒 (λ) - 2𝑃𝑒𝑃 𝑃 (λ) -2 𝑛 𝑛 𝑛−1 şeklinde ifade edilir. İspat. Öncelikle  −1 −1 𝑃𝑒𝐶 (𝜆) = −1  −1 3 −1 −1   −1 −1 −1 −1  = 𝜆 + (−1)(−1) + (−1) −1  −1  −1 −1 = 𝜆𝑃𝑒𝑃 (𝜆) + (−𝜆 − 1) − (1 + 𝜆) 3 15 = 𝜆𝑃𝑒𝑃 (𝜆) − 2𝜆 − 2 3 ve  −1 0 −1 −1  −1 0 𝑃𝑒𝐶 (𝜆) = 4 0 −1  −1 −1 0 −1   −1 0 −1 −1 0 −1  −1 = 𝜆 −1  −1 + 0  −1 + 0 −1  0 −1  −1 −1  −1 0 −1 𝑒 𝑒 0 −1 −1  = 𝜆𝑃𝑃 (𝜆) − 𝑃𝑃 (𝜆) + − − 𝑃 𝑒 𝑃 (𝜆) 4 3 −1  0 −1 3 = 𝜆𝑃𝑒𝑃 (𝜆) − 2𝑃 𝑒 𝑃 (𝜆) − 1 − 1 4 3 = 𝜆𝑃𝑒𝑃 (𝜆) − 2𝑃 𝑒 𝑃 (𝜆) − 2 4 3 olduğunu belirtelim. Benzer şekilde  −1 0 0 −1 −1  −1 0 0 𝑃𝑒𝐶 (𝜆) = 0 −1  −1 0 5 0 0 −1  −1 −1 0 0 −1  −1 −1 0 0 −1  −1 0 0  −1 0 0 −1  −1 =λ𝑃𝑒𝑃 (𝜆) + − 5 0 −1  −1 0 0 −1  −1 0 −1  −1 0 0 −1 0 −1 0 −1  −1 = λ𝑃𝑒 (𝜆) − 𝑃𝑒𝑃 𝑃 (𝜆) + 0  −1 + 0 −1  − 𝑃 𝑒 𝑃 (𝜆) 5 4 4 −1 −1  0 0 −1 16 0 −1 = λ𝑃𝑒𝑃 (𝜆) − 2𝑃 𝑒 𝑃 (𝜆) + − 1 5 4 −1  = λ𝑃𝑒 𝑒𝑃 (𝜆) − 2𝑃𝑃 (𝜆) − 1 − 1 5 4 = λ𝑃𝑒𝑃 (𝜆) − 2𝑃 𝑒 𝑃 (𝜆) − 2 5 4 dir. Benzer şekilde devam edersek, ilk olarak birinci satıra göre determinant alınır. Buradan 𝑃𝑒𝑃 (λ) polinomu ile 𝑃 𝑒 𝐶 (λ) polinomunun alt matrisinden gelen iki determinant 𝑛 𝑛 elde edilir. Daha sonra sırayla son matrisin birinci sütuna göre ve önceki matrisin birinci satıra göre determinantı alınır. Son matrisin determinantından, determinantı −1 olan bir üst üçgensel matris elde edilir ve diğer matris bize - 𝑃𝑒𝑃 (λ) ifadesini verir. Önceki 𝑛−1 matrisin determinantından - 𝑃𝑒𝑃 (λ) ve bir matris daha elde edilir. Bu şekilde devam 𝑛−1 0 −1 edilerek sonunda | | ifadesi elde edilir. Bu ifade −1’e eşittir. Elde ettiğimiz −1 𝜆 terimlerin toplamı ise 𝑃𝑒𝐶 (λ) = λ𝑃 𝑒 𝑃 (λ) - 2𝑃 𝑒 𝑃 (λ) -2 𝑛 𝑛 𝑛−1 eşitliğini verir. 𝑃𝑒𝑃 (λ) karakteristik polinomunun formülünü elde etmiştik. Şimdi de bu formülü 𝑛 kullanarak 𝑃𝑒𝐶 (λ) karakteristik polinomunun formülünü elde edebiliriz: 𝑛 Teorem 3.4. 𝐶𝑛 devir grafının kenar-karakteristik polinomunun formülü 𝑛 çift iken 𝑛−2 𝑛−2 2 2 𝑛 − 1 − 𝑙 𝑛 − 2 − 𝑙 𝑃𝑒 (𝜆) = 𝜆∑(−1)𝑙 ( ) 𝜆𝑛−1−2𝑙 − 2∑(−1)𝑙 ( ) 𝜆𝑛−2−2𝑙𝐶 − 2 𝑛 𝑙 𝑙 𝑙=0 𝑙=0 ve 𝑛 tek iken 𝑛−1 𝑛−3 2 2 𝑛 − 1 − 𝑙 𝑛 − 2 − 𝑙 𝑃𝑒 (𝜆) = 𝜆∑(−1)𝑙 ( ) 𝜆𝑛−1−2𝑙𝐶 − 2∑(−1) 𝑙 ( ) 𝜆𝑛−2−2𝑙 − 2 𝑛 𝑙 𝑙 𝑙=0 𝑙=0 17 şeklindedir. Aşağıdaki iki sonuç 𝑃𝑒 𝑒𝑃 (λ) ve 𝑃𝐶 (λ) polinomlarının herbirisinin katsayılar toplamının 6 𝑛 𝑛 modunda özel bir forma sahip olduğunu kanıtlar: Teorem 3.5. 0, 𝑛 ≡ 0(6) 𝑣𝑒 𝑛 ≡ 3(6) 𝑃𝑒𝑃 (1) = { 1, 𝑛 ≡ 1(6) 𝑣𝑒 𝑛 ≡ 2(6) 𝑛 −1, 𝑛 ≡ 4(6) 𝑣𝑒 𝑛 ≡ 5(6) Teorem 3.6. 0, 𝑛 ≡ 0(6) 𝑒 −1, 𝑛 ≡ 1(6)𝑣𝑒 𝑛 ≡ 5(6)𝑃𝐶 (1) = 𝑛 −3, 𝑛 ≡ 2(6)𝑣𝑒 𝑛 ≡ 4(6) { −4, 𝑛 ≡ 3(6) Şimdi 𝑆𝑛yıldız grafına ait kenar-kararkteristik polinomunu inceleyelim: Teorem 3.7. 𝑆𝑛yıldız grafına ait kenar-karakteristik polinomunun indirgeme formülü 𝑃𝑒𝑆 (λ) = λ𝑃 𝑒 𝑆 (λ) – (n-2)(𝜆 + 1) 𝑛−3 𝑛 𝑛−1 şeklindedir. İspat. 𝑛 köşeli yıldız grafın kenar-komşuluk matrisi 0 1 1 1   1 0 1 1   𝐴𝑒(𝑆𝑛) =     1 1 0 1 1 1 1 0 (𝑛−1)×(𝑛−1) formundadır. 𝐴𝑒(𝑆𝑛)matrisinin karakteristik polinomu 18  −1 −1 −1 −1  −1 −1 |𝜆𝐼 − 𝐴𝑒(𝑆𝑛)| = −1 −1  −1 −1 −1 −1  (𝑛−1)×(𝑛−1) şeklinde ifade edilir. Eğer determinant birinci satıra göre açılırsa (𝑛 − 2) × (𝑛 − 2) tipinde üç adet determinant elde edilir. −1 −1 −1 −1 𝑃𝑒𝑆 (𝜆) = 𝜆𝑃 𝑒 (𝜆) + (−1)1+1(−1) + (−1)1+3𝑆 (−1) 𝑛 𝑛−1 −1 −1  −1 −1 −1 −1  −1  −1 −1 −1  −1 −1 +⋯+ (−1)1+𝑛(−1) −1 −1  −1 −1 −1 −1  −1 −1 −1  −1 −1 −1 −1 Daha sonra determinantlara elementer satır operasyonları uygulanırsa tüm determinantlar −1 −1 −1 −1 −1  −1 −1 −1  −1 −1 , ,…, −1 −1  −1 −1 −1  −1 −1 −1 −1  −1 −1 −1  −1 −1 −1  −1 −1 −1 −1 haline dönüşür ve kolayca görülebilir ki bunların tümü aynıdır. O halde −1 −1 −1 −1 𝑃𝑒𝑆 (𝜆) = 𝜆𝑃 𝑒 (𝜆) + (𝑛 − 2) 𝑛 𝑆𝑛−1 −1  −1 −1 −1 −1  −1 −1 −1 −1  (𝑛−2)×(𝑛−2) elde edilir. Son determinanta 𝑅2 → 𝑅2 − 𝑅1, 𝑅3 → 𝑅3 − 𝑅1,…, 𝑅𝑛 → 𝑅𝑛 − 𝑅1satır operasyonları uygulanırsa 19 −1 −1 −1 −1 0 +1 −1 −1 0 0 +1 −1 0 0 0 +1 (𝑛−2)×(𝑛−2) formuna dönüşür. Bu ifade (−1)(𝜆 + 1)𝑛−3’e eşittir. O halde 𝑃𝑒𝑆 (λ) = λ𝑃 𝑒 𝑆 (λ) – (n-2)(𝜆 + 1) 𝑛−3 𝑛 𝑛−1 elde edilir. Teorem 3.8. 𝑆𝑛 yıldız grafının kenar-karakteristik polinomu 𝑃𝑒𝑆 (𝜆) = [𝜆 − (𝑛 − 2)](𝜆 + 1) (𝑛−2) 𝑛 şeklindedir. İspat. n köşeli yıldız grafın kenar-komşuluk matrisine karşılık gelen determinant 0 1 1 1 1 0 1 1 𝑃𝑒𝑆 (𝜆) =𝑛 1 1 0 1 1 1 1 0 (𝑛−1)×(𝑛−1) olup 𝐴𝑒(𝑆𝑛)matrisinin kenar-karakteristik polinomu  −1 −1 −1 −1  −1 −1 |𝜆 ∙ 𝐼 − 𝐴𝑒(𝑆𝑛)| = −1 −1  −1 −1 −1 −1  (𝑛−1)×(𝑛−1) formundadır. Öncelikle 𝑅1 → 𝑅1 + 𝑅2+𝑅3+⋯+ 𝑅𝑛−1 satır operasyonlarını uygularsak determinant 20  − (n − 2)  − (n − 2)  − (n − 2)  − (n − 2) −1  −1 −1 −1 −1  −1 −1 −1 −1  halini alır. Daha sonra determinant özelliğinden 1 1 1 1 −1  −1 −1 [𝜆 − (𝑛 − 2)] −1 −1  −1 −1 −1 −1  (𝑛−1)×(𝑛−1) ifadesi elde edilir ve 𝑅2 → 𝑅2 + 𝑅1, 𝑅3 → 𝑅3 + 𝑅1, … , 𝑅𝑛−1 → 𝑅𝑛−1 + 𝑅1 satır operasyonlarını uygularsak 1 1 1 1 0  +1 0 0 = (𝜆 + 1)(𝑛−2) 0 0  +1 0 0 0 0  +1 (𝑛−1)×(𝑛−1) eşitliğine ulaşılır. Son olarak 𝑃𝑒𝑆 (𝜆) = [𝜆 − (𝑛 − 2)](𝜆 + 1) (𝑛−2) 𝑛 elde edilir. Aşağıdaki sonuçların ispatları yukarıda yapılanlara benzediğinden burada verilmeyecektir. Teorem 3.9. 𝑇𝑟,𝑠 larva grafına ait kenar-komşuluk matrisi ile elde edilen kenar- karakteristik polinomunun indirgeme bağıntısı 21 𝜆𝑃𝑒𝑇 (𝜆) − 𝑃 𝑒 𝑇 (𝜆), 𝑠 ≠ 1 𝑣𝑒 𝑠 ≠ 2𝑟,𝑠−1 𝑟,𝑠−2 𝑃𝑒 𝑒 𝑒𝑇 (𝜆) = { 𝜆𝑃𝑇 (𝜆) − 𝑃𝐶 (𝜆) , 𝑠 = 2 𝑟,𝑠−1 𝑟 𝑟,𝑠 𝜆𝑃𝑒𝐶 (𝜆) − 2𝑃 𝑒 𝑃 (𝜆) − 2𝑃 𝑒 𝑟 𝑟 𝑃 (𝜆) − 2 , 𝑠 = 1 𝑟−1 şeklindedir. Teorem 3.10. 𝐾𝑛 tam grafına ait kenar-karakteristik polinomu (𝜆 − 2)(𝜆 + 1)2 , 𝑛 = 3 𝑃𝑒𝐾 (𝜆) = { 𝑛 𝑛 [𝜆 − 2(𝑛 − 2)][𝜆 − (𝑛 − 4)]𝑛−1(𝜆 + 2)(2)−𝑛, 𝑛 ≠ 3 şeklindedir. Teorem 3.11. 𝐾𝑟,𝑠 tam iki parçalı grafına ait kenar-karakteristik polinomu 𝑃𝑒𝐾 (𝜆) = (𝜆 − 𝑠 − 𝑟 + 2)(𝜆 − 𝑠 + 2) 𝑟−1(𝜆 − 𝑟 + 2)𝑠−1(𝜆 + 2)(𝑟−1)(𝑠−1) 𝑟,𝑠 şeklindedir. Aşağıdaki sonuçlar kolayca daha önceki sonuçlardan elde edilebilir olup kenar- karakteristik polinomları ile (köşe-)karakteristik polinomları arasındaki bazı ilişkileri vermektedir ve ispatları açıktır: Teorem 3.12.𝑃𝑒 (𝜆) = 𝑃𝑣𝑃 𝑃 (𝜆). 𝑛 𝑛−1 Teorem 3.13. 𝑃𝑒𝐶 (𝜆) = 𝑃 𝑣 𝐶 (𝜆). 𝑛 𝑛 Teorem 3.14. 𝑃𝑒𝐾 (𝜆) = 𝑃 𝑒 𝑟,1 𝑆 (𝜆). 𝑟+1 Teorem 3.15. 𝑃𝑒 𝑣𝑆 (𝜆) = 𝑃𝑛 𝐾 (𝜆). 𝑛−1 22 4. BİTİŞİKLİK MATRİSLERİ VE POLİNOMLARI Şimdiye kadar köşe-karakteristik ve kenar-karakteristik polinomlar ile çalıştık. Bilindiği üzere, bu polinomlar spektral graf teoride bir grafın enerjisinin hesaplanmasında önemli rol oynar. Bu iki kavram da komşuluk matrislerine dayalı olarak tanımlanmakta ve kullanılmaktadır. Bu bölümde ise farklı olarak bitişiklik polinomlarını ele alacağız. Bir 𝐺 grafının bitişiklik polinomu 𝐼𝐺(𝜆) ile gösterilecektir. İlk bölümde bir 𝐺 grafının bir kenarını 𝑒 = 𝑢𝑣 ile ifade edip, 𝑒 kenarını 𝑢 ve 𝑣 köşelerine bitişik olarak adlandırmıştık. Bir 𝐺 grafına ait 𝐴𝑖(𝐺) = [𝑎𝑖𝑗] bitişiklik matrisi 𝑚×𝑛 1, 𝑣𝑖 𝑣𝑒 𝑒𝑗 𝑘𝑒𝑛𝑎𝑟𝑙𝑎𝑟𝚤 𝑏𝑖𝑡𝑖ş𝑖𝑘 𝑖𝑠𝑒 𝑎𝑖𝑗 = { 0, 𝑣𝑖 𝑣𝑒 𝑒𝑗 𝑘𝑒𝑛𝑎𝑟𝑙𝑎𝑟𝚤 𝑏𝑖𝑡𝑖ş𝑖𝑘 𝑑𝑒ğ𝑖𝑙 𝑖𝑠𝑒 biçiminde tanımlanır. Şimdi bitişiklik polinomlarına ait formülleri ve indirgeme bağıntılarını hesaplayacağız. Bir 𝐺 grafının bitişiklik matrisi kare matris olmayabileceğinden tüm graflar için bitişiklik polinomu hesaplamak mümkün değildir. Bu sebeple bitişiklik matrisi kare olan polinomları hesaplayacağız. Lemma 4.1. Bir matris 𝐴 ve 𝐵 matrisleri kare matrisler, 0 tüm elemanları 0 olan bir matris ve 𝐶 uygun boyutlu herhangi bir matris olmak üzere aşağıdaki gibi dört blok matrise bölünürse 𝐴 𝑂 [ ] 𝐶 𝐵 matrisinin determinantı |𝐴||𝐵| ifadesine eşit olur. Lemma 4.1 sayesinde larva graflar için indirgeme bağıntısını elde edebiliriz. Teorem 4.1. 𝑇𝑟,𝑠 larva grafına ait bitişiklik polinomu 𝐼𝑇 (𝜆) = (𝜆 − 1) 𝑠𝐼𝐶 (𝜆) 𝑟,𝑠 𝑟 23 bağıntısı ile elde edilir. Buradaki 𝐼𝐶 (𝜆) polinomu aşağıda hesaplanacak olan devirli grafların bitişiklik 𝑟 polinomunu göstermektedir. İspat. 𝑇𝑟,𝑠 larva grafının bitişiklik matrisi 1, 𝑖 = 𝑗 𝑖𝑠𝑒 1, 𝑖 − 𝑗 = 1 𝑖𝑠𝑒 𝑎𝑖𝑗 { 1, 𝑖 = 𝑠 + 1, 𝑗 = 𝑟 + 𝑠 𝑖𝑠𝑒 0, 𝑑𝑖ğ𝑒𝑟 𝑑𝑢𝑟𝑢𝑚𝑙𝑎𝑟𝑑𝑎 formundadır. 𝐴𝑖(𝑇𝑟,𝑠) matrisini aşağıdaki gibi dört blok matrise bölersek 1 0 0 0 0 0 0 0 0 0 0   1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0     0 0 0 0 1 1 0 0 0 0 0   𝑖 0 0 0 0 0 1 1 0 0 1𝐴 (𝑇𝑟,𝑠) =   0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0   0 0 0 0 0 0 0 0 0 0     0 0 0 0 0 0 0 0 1 0   0 0 0 0 0 0 0 0 1 1 olur ve −1 0 0 0 0 0 0 0 0 0 0     −1 −1 0 0 0 0 0 0 0 0 0   0 −1 −1 0 0 0 0 0 0 0 0       0 0 0 0 −1 −1 0 0 0 0 0    𝑖  0 0 0 0 0 −1 −1 0 0 −1 |𝜆𝐼 − 𝐴 (𝑇𝑟,𝑠)| =    0 0 0 0 0 0 −1 −1 0 0   0 0 0 0 0 0 0 −1 0 0     0 0 0 0 0 0 0 0 0 0       0 0 0 0 0 0 0 0 −1 0     0 0 0 0 0 0 0 0 −1 −1 ifadesi elde edilir. Burada sol üstteki üst üçgensel matrisin determinantı (𝜆 − 1)𝑠 ve alt sağ blok matrisin determinantı 𝐼𝐶 (𝜆) olur. Lemma 4.1’den dolayı 𝑟 24 |𝜆𝐼 − 𝐴| = (𝜆 − 1)𝑠𝐼𝐶 (𝜆) 𝑟 elde edilir. Aşağıda verilen iki sonuç benzer şekilde ispatlanır. Teorem 4.2. 𝐶𝑛 devir grafına ait bitişiklik polinomu 𝐼𝐶 (𝜆) = (𝜆 − 1) 𝑛 − 1 𝑛 bağıntısıyla elde edilir. Teorem 4.3. 𝐾2,2 tam-iki parçalı grafına ait bitişiklik polinomu 𝐼𝐾 (𝜆) = (𝜆 − 2)(𝜆 − 1)𝜆 2 2,2 bağıntısıyla elde edilir. 25 5. GRAFLARIN KENAR-ZAGREB MATRİSLERİ VE POLİNOMLARI Graf matrislerinin cebirsel çalışılması graf teorinin, moleküler yapıların kimyasal ve fiziksel özellikleri hakkında bilgi veren önemli bir alt alanıdır. Bu bölümde graf indekslerinden en çok kullanılanları arasında olan ve Zagreb indeksleri olarak adlandırılan indekslerden faydalanılarak elde edilen kenar-Zagreb matrisleri üzerinde çalışılmıştır. Bu bölümde elde edilen sonuçlar Yamaç ve Ark. (2019)’da yayınlanmıştır. 𝐺 = (𝑉, 𝐸) grafı, |𝑉(𝐺)| = 𝑛 köşeli ve |𝐸(𝐺)| = 𝑚 kenarlı bir graf olsun. Hatırlanacağı gibi bir 𝑣𝜖𝑉(𝐺) köşesinin derecesi 𝑑𝑣 ya da 𝑑𝐺(𝑣) ile gösterilir. Ayrıca derecesi 1 olan bir köşe sallanan köşe olarak adlandırılır. Benzer şekilde bir sallanan köşeye sahip olan bir kenara da sallanan kenar denildiğini belirtmiştik. Bir 𝐺 grafında 𝑢 ve 𝑣 köşeleri bir𝑒 kenarı ile bağlı ise bu durum 𝑒 = 𝑢𝑣 ile gösterilmekteydi. Bu durumda 𝑢 ve 𝑣 köşeleri komşudur ve 𝑒 kenarı 𝑢 ve 𝑣 köşelerine bitişiktir denilmektedir. Komşuluk ve bitişiklik ile ilgili matrislere ait çalışmalar, moleküler kimyaya yardımcı olup graf teorinin iyi bilinen bir uygulamasıdır. Ayrıca graf teorinin grafların enerjisi ile ilgilenen alt alanı olan spektral graf teoride lineer cebirsel metotlar ile bir grafın öz değerleri hesaplanarak bu değerler o grafa ait moleküler enerjinin bulunmasında kullanılır. Bu nedenle bazı kimyasal yapıların graf modellerinin spektral olarak çalışılmasında matrisler oldukça yardımcıdır. Bir 𝐺 grafı 𝑛köşeye ve 𝑚 kenara sahip bağlantılı basit bir graf olsun. Bu 𝐺 grafına ait kenar-Zagreb matrisi 𝑑(𝑣𝑖)𝑑(𝑣𝑗), 𝑣𝑖 𝑣𝑒 𝑣𝑗 𝑘öş𝑒𝑙𝑒𝑟𝑖 𝑘𝑜𝑚ş𝑢 𝑖𝑠𝑒𝑎𝑖𝑗 = { 0, 𝑣𝑖 𝑣𝑒 𝑣𝑗 𝑘öş𝑒𝑙𝑒𝑟𝑖 𝑘𝑜𝑚ş𝑢 𝑑𝑒ğ𝑖𝑙 𝑖𝑠𝑒 formundadır ve 𝑍𝑀(𝐺) = [𝑎𝑖𝑗] ile gösterilir. Bu matrisler yardımıyla hesaplanan 𝑛×𝑛 kenar-Zagreb polinomlarını 𝑃𝑒𝑧𝐺 (𝜆) ile göstereceğiz. Bu polinomlar karakteristik polinomlardır ve polinomun kökleri kenar-Zagreb matrisinin öz değerleridir. Bu 26 özdeğerlerin mutlak değerlerinin toplamı ise kenar-Zagreb matrisine karşılık gelen grafın kenar-Zagreb enerjisini verir. Bu bölümde 0 4 0 0 0 0   4 0 4 0 0 0   0 4 0 0 0 0     0 0 0 0 4 0   0 0 0 4 0 4 0 0 0 0 4 0 formunda olan özel bir kare matris kullanılacaktır. Bu matris herhangi bir grafa karşılık gelmemesine rağmen hesaplamalarda sıkça kullanılacağından burada determinantını ve karakteristik polinomunu hesaplayacağız. n boyutlu bu matrisi ∆𝑛 ile gösterelim. Bu matrise karşılık gelen karakteristik polinom ise 𝑃∆ (𝜆) ile gösterilecek olup 𝑛 𝑛 ⌊ ⌋ 2 𝑃 (𝜆) = ∑(−1)𝑘 24𝑘 𝑛 − 𝑘 ( ) 𝜆𝑛−2𝑘∆ 𝑛 𝑛 − 2𝑘 𝑘=0 formunda olduğu kolayca hesaplanabilir. İlk olarak 𝑃𝑛 patika grafına ait kenar-Zagreb polinomu ele alınacaktır. Teorem 5.1. 𝑛 ≥ 4 için, 𝑃𝑒𝑧𝑃 (𝜆) = 𝜆, 𝑃 𝑒𝑧(𝜆) = 𝜆2𝑃 − 1 ve 𝑃 𝑒𝑧(𝜆) = 𝜆3𝑃 − 8𝜆 1 2 3 olmak üzere, 𝑃𝑛 patika grafının kenar-Zagreb matrisi kullanılarak elde edilen kenar- Zagreb polinomunun formülü 𝑃𝑒𝑧𝑃 (𝜆) = 𝜆 2𝑃 𝑛 ∆ (𝜆) − 8𝜆𝑃 𝑛−2 ∆ (𝜆) + 16𝑃 𝑛−3 ∆ (𝜆) 𝑛−4 27 formundadır. İspat. 𝑃𝑛 patika grafının kenar-Zagreb matrisi 0 2 0 0 0 0 0 0   2 0 4 0 0 0 0 0   0 4 0 4 0 0 0 0   0 0 4 0 4 0 0 0𝑍𝑀(𝑃 ) = 𝑛     0 0 0 0 0 0 4 0 0 0 0 0 0 4 0 2   0 0 0 0 0 0 2 0 formundadır. Dolayısıyla kenar-Zagreb polinomunu elde etmek için  −2 0 0 0 0 0 0 −2  −4 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 −4  −4 0 0 0 𝑃𝑒𝑧𝑃 (𝜆) = |𝜆𝐼 − 𝑍𝑀(𝑃 )| = 𝑛 𝑛 0 0 0 0 0  −4 0 0 0 0 0 0 −4  −2 0 0 0 0 0 0 −2  determinantını hesaplamak gerekir. 𝑛 = 1 için tek boyutlu 0 matrisi ortaya çıkar; dolayısıyla 𝑃𝑒𝑧𝑃 (𝜆) = 𝜆 elde edilir. 𝑛 = 2 ve 𝑛 = 3 için ispat açıktır.𝑛 ≥ 4 olsun. 𝑃 𝑒𝑧 𝑃 (𝜆) 1 𝑛 birinci satıra göre hesaplanırsa  −4 0 0 0 0 −2 −4 0 0 0 0 −4  −4 0 0 0 0  −4 0 0 0 0 −4  0 0 0 0 −4  0 0 0 |𝜆𝐼 − 𝑍𝑀(𝑃𝑛)| = 𝜆 +2 0 0 0  −4 0 0 0 0  −4 0 0 0 0 −4  −2 0 0 0 −4  −2 0 0 0 0 −2  0 0 0 0 −2  ifadesi elde edilir. İkinci determinant birinci sütuna göre açılırsa 28  −4 0 0 0 0  −4 0 0 0 0 −4  −4 0 0 0 −4  −4 0 0 0 |𝜆𝐼 − 𝑍𝑀(𝑃 )| = 𝜆 0 −4  0 0 0 − 4 0 −4  0 0 0𝑛 0 0 0  −4 0 0 0 0  −4 0 0 0 0 −4  −2 0 0 0 −4  −2 0 0 0 0 −2  0 0 0 0 −2  olur. Birinci determinant (𝑛 − 1) × (𝑛 − 1), ikinci determinant ise (𝑛 − 2) × (𝑛 − 2) boyutludur. Bu determinantları son satıra göre açarak hesaplarsak  −4 0 0 0 0  −4 0 0 0 0 −4  −4 0 0 0 −4  −4 0 0 0 𝜆(−1)2𝑛−3(−2) 0 −4  0 0 0 + (−1)2𝑛−2𝜆2 0 −4  0 0 0 0 0 0  −4 0 0 0 0  −4 0 0 0 0 −4  0 0 0 0 −4  −4 0 0 0 0 −4 −2 0 0 0 0 −4   −4 0 0 0 0  −4 0 0 0 0 −4  −4 0 0 0 −4  −4 0 0 0 +(4)(−1)2𝑛−5(2) 2𝑛−40 −4  0 0 0 + (−1) (−4)𝜆 0 −4  0 0 0 0 0 0  −4 0 0 0 0  −4 0 0 0 0 −4  0 0 0 0 −4  −4 0 0 0 0 −4 −2 0 0 0 0 −4  ifadesi elde edilir. Bu ifadedeki birinci ve üçüncü determinantlar son sütuna göre açılırsa  −4 0 0 0 0  −4 0 0 0 0 −4  −4 0 0 0 −4  −4 0 0 0 0 −4  0 0 0 0 −4  0 0 0 (−4)𝜆 + 𝜆2 0 0 0  −4 0 0 0 0  −4 0 0 0 0 −4  −4 0 0 0 −4  −4 0 0 0 0 −4  0 0 0 0 −4  29  −4 0 0 0 0  −4 0 0 0 0 −4  −4 0 0 0 −4  −4 0 0 0 0 −4  0 0 0 0 −4  0 0 0 +16 + (−4)λ 0 0 0  −4 0 0 0 0  −4 0 0 0 0 −4  −4 0 0 0 −4  −4 0 0 0 0 −4  0 0 0 0 −4  elde edilir. Bu ifadedeki ilk ve son determinant (𝑛 − 3) × (𝑛 − 3), ikinci determinant (𝑛 − 2) × (𝑛 − 2) ve son determinant (𝑛 − 4) × (𝑛 − 4) boyutludur. Sonuç olarak, 𝑃𝑛 patika grafına ait kenar-Zagreb polinomu 𝑃𝑒𝑧𝑃 (𝜆) = 𝜆 2𝑃∆ (𝜆) − 8𝜆𝑃 (𝜆) + 16𝑃 (𝜆) 𝑛 𝑛−2 ∆𝑛−3 ∆𝑛−4 formundadır. Şimdi 𝐶𝑛 devir grafına ait kenar-Zagreb polinomu ele alınacaktır. Teorem 5.2. 𝐶𝑛 devir grafının kenar-Zagreb matrisi kullanılarak elde edilen kenar- Zagreb polinomunun formülü 𝑃𝑒𝑧(𝜆) = −22𝑛+1𝐶 − 32𝑃∆ (𝜆) − 𝜆𝑃 (𝜆) 𝑛 𝑛−2 ∆𝑛−1 formundadır. İspat. 𝐶𝑛 devir grafının kenar-Zagreb matrisi 0 4 0 0 0 0 0 4   4 0 4 0 0 0 0 0 0 4 0 4 0 0 0 0   𝑍𝑀(𝐶𝑛) 0 0 4 0 4 0 0 0     0 0 0 0 0 4 0 4   4 0 0 0 0 0 4 0 formundadır. Dolayısıyla 30  −4 0 0 0 0 0 −4 −4  −4 0 0 0 0 0 0 −4  −4 0 0 0 0 |𝜆𝐼 − 𝑍𝑀(𝐶𝑛)| = 0 0 −4  −4 0 0 0 0 0 0 0 0 −4  −4 −4 0 0 0 0 0 −4  ifadesi elde edilir. Bu matrisin determinantı son satıra göre hesaplanırsa −4 0 0 0 0 0 0 −4  −4 0 0 0 0 0 −4  −4 0 0 0 0 0 0 −4  −4 0 0 0 0 0 (−1)𝑛+24 2𝑛−4  −4 0 0 0 0 0 + (−1) 4 0 −4  −4 0 0 0 0 0 −4  −4 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0  −4 0 0 0 0 0 0 −4  0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 −4 −4  −4 0 0 0 0 0 0 −4  −4 0 0 0 0 0 +(−1)2𝑛𝜆 0 −4  −4 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 −4  elde edilir. İlk determinantı birinci satıra göre ve ikinci determinantı son sütuna göre açarsak sırasıyla boyutları (𝑛 − 2) × (𝑛 − 2), (𝑛 − 2) × (𝑛 − 2), (𝑛 − 2) × (𝑛 − 2), (𝑛 − 2) × (𝑛 − 2) ve (𝑛 − 1) × (𝑛 − 1) olan beş determinant elde edilir. Dolayısıyla 𝑃𝑒𝑧𝐶 (𝜆) = (−1) 𝑛+516(−4)𝑛−2+(−1)2𝑛+316𝑃∆ (𝜆) + (−1) 3𝑛+116(−4)𝑛−2 𝑛 𝑛−2 +(−1)4𝑛−116𝑃∆ (𝜆)+λ 𝑃∆ (𝜆) 𝑛−2 𝑛−1 =−22𝑛+1 − 32𝑃∆ (𝜆) − 𝜆𝑃 (𝜆) 𝑛−2 ∆𝑛−1 eşitliği elde edilir. Şimdi 𝑇𝑟,𝑠 larva grafına ait kenar-Zagreb polinomu ele alınacaktır. 31 Teorem 5.3. 𝑇𝑟,𝑠 larva grafına ait kenar-Zagreb matrisi kullanılarak elde edilen kenar- Zagreb polinomunun formülü (𝜆2 − 9)𝑃 (𝜆) − 72𝜆𝑃 (𝜆) − 9. 22𝑟−1∆ ∆ 𝜆, 𝑠 = 1 𝑟−1 𝑟−2 𝜆2[𝜆𝑃∆ (𝜆) − 72𝑃 2𝑟−1 𝑟−1 ∆ (𝜆) − 9. 2 ] 𝑟−2 −40𝜆𝑃∆ (𝜆) + 288(𝑃∆ (𝜆) + 2 2𝑟−4, 𝑠 = 2 𝑟−1 𝑟−2 𝑃𝑒𝑧𝑇 (𝜆) = 𝑟,𝑠 𝜆𝑃∆ (𝜆)[𝜆𝑃∆ (𝜆) − 72𝑃 (𝜆) − 9. 2 2𝑟−1] 𝑠−1 𝑟−1 ∆𝑟−2 +𝑃∆ (𝜆)[−40𝜆𝑃∆ (𝜆) + 288(𝑃 2𝑟−4 𝑠−2 𝑟−1 ∆ (𝜆) + 2 )] , 𝑠 > 2 𝑟−2 +𝑃∆ (𝜆)[144𝑃∆ (𝜆)] 𝑠−3 𝑟−1 { formundadır. İspat. 𝑠 = 1 olsun. O halde  −3 0 0 0 0 0 0 −3  −6 0 0 0 0 −6 0 −6  −4 0 0 0 0 𝑃𝑒𝑧𝑇 (𝜆) = 0 0 −4  −4 0 0 0 𝑟,𝑠 0 0 0 0 0 −4  −4 0 −6 0 0 0 0 −4  determinantı elde edilir. Bu determinantı hesaplarsak 𝑃𝑒𝑧 (𝜆) = (𝜆2𝑇 − 9)𝑃 (𝜆) − 72𝜆𝑃 (𝜆) − 9 ∙ 2 2𝑟−1𝜆 𝑟,1 ∆𝑟−1 ∆𝑟−2 sonucu elde edilir. Şimdi 𝑠 = 2 olsun. Bu durumda  −2 0 0 0 0 0 0 0 0 −2  −6 0 0 0 0 0 0 0 = 0 −6  −6 0 0 0 0 0 −6 0 0 −6  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 −6 0 0 0 0 0 −4  32 determinantı elde edilir ve bu determinantı üçüncü satıra göre açarsak  −2 0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 −2 −6 0 0 0 0 0 0 0 0 −2  0 0 0 0 0 0 0 0 0 −6  −4 0 0 0 0 0 0 0 0  −4 0 0 0 0 0 06 + λ 0 0 −4  −4 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 −4  −4 0 0 −6 0 0 0 0 0 −4  0 0 0 0 0 0 0 0 −4   −2 0 0 0 0 0 0 0 0  −2 0 0 0 0 0 0 0 0 +6 −2  −6 0 0 0 0 0 0 0 + (−1)𝑟+𝑠+3(-6) −2  −6 0 0 0 0 0 0 0 0 0 −6 −4 0 0 0 0 0 0 0 0 −6  −4 0 0 0 0 0 0 0 0  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 −4  −4 0 0 −6 0 0 0 0 0 −4  0 0 −6 0 0 0 0 0 −4  ifadesi elde edilir. Bu determinantları sırasıyla ikinci satıra, birinci satıra, üçüncü satıra ve son satıra göre açarsak ve Lemma 4.1 ile üst üçgensel matrisin özelliklerinden dolayı 𝑃𝑒𝑧𝑇 (𝜆) = 𝜆 2[𝜆𝑃 (𝜆) − 72𝜆𝑃 (𝜆) − 9 ∙ 22𝑟−1] − 40𝜆𝑃 (𝜆) 𝑟,2 ∆𝑟−1 ∆𝑟−2 ∆𝑟−1 +288(𝑃 (𝜆) + 22𝑟−4∆ ) 𝑟−2 elde edilir. Son olarak 𝑠 ≥ 3 için  −2 0 0 0 0 0 0 0 0 0 0 0 −2  −4 0 0 0 0 0 0 0 0 0 0 0 −4  0 0 0 0 0 0 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 𝑒𝑧 0 0 0 0 0 −4  −6 0 0 0 0 0𝑃𝑇 (𝜆) = 𝑟,𝑠 0 0 0 0 0 0 −6  −6 0 0 0 −6 0 0 0 0 0 0 0 −6  −4 0 0 0 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 0 0 0 0 0 0 −4  −4 0 0 0 0 0 0 −6 0 0 0 0 −4  determinantı elde edilir. Bu determinant hesaplandığında ise 33 𝑃𝑒𝑧 2𝑟−1𝑇 (𝜆) = 𝜆𝑃𝑟,1 ∆ (𝜆)[𝜆𝑃𝑠−1 ∆ (𝜆) − 72𝜆𝑃𝑟−1 ∆ (𝜆) − 9 ∙ 2 ] 𝑟−2 − 𝑃∆ (𝜆)[−40𝜆𝑃∆ (𝜆) + 288(𝑃 (𝜆) + 2 2𝑟−4)] 𝑠−2 𝑟−1 ∆𝑟−2 + 𝑃𝑠−3(𝜆)[144𝑃∆ (𝜆)] 𝑟−1 eşitliği elde edilir. Şimdi 𝑆𝑛 yıldız grafı için kenar-Zagreb polinomunu hesaplayacağız. Teorem 5.4. 𝑆𝑛 yıldız grafına ait kenar-Zagreb matrisi kullanılarak elde edilen kenar- Zagreb polinomunun formülü 𝑃𝑒𝑧 𝑛−2𝑆 (𝜆) = 𝜆 [𝜆 2 − (𝑛 − 1)3] 𝑛 formundadır. İspat. 𝑆𝑛 yıldız grafına ait kenar-Zagreb polinomunu hesaplamak için  −(n−1) 0 0 0 0 0 −(n−1)  −(n−1) −(n−1) −(n−1) −(n−1) −(n−1) 0 −(n−1)  0 0 0 0 𝑃𝑒𝑧𝑆 (𝜆) = 0 −(n−1) 0  0 0 0 𝑛 0 −(n−1) 0 0 0  0 0 −(n−1) 0 0 0 0  determinantı hesaplanmalıdır. Eğer determinantı dört blok matrise ayırırsak sol üst matris 2 × 2 tipinde ve sağ üst matris (𝑛 − 2) × (𝑛 − 2) tipinde olur. Ayrıca 𝑛 − 1 𝑅3 + 𝑅 → 𝑅𝜆 2 2, 𝑛 − 1 𝑅 𝜆 4 + 𝑅2 → 𝑅2, ⋮ 𝑛 − 1 𝑅𝑛 + 𝑅2 → 𝑅𝜆 2, elementer satır operasyonları uygulanırsa 34  −(n−1) 0 0 0 0 0 0 (n−2)(n−1)2 −(n−1) − 0 0 0 0 0 0  0 −(n−1)  0 0 0 0 0 0 −(n−1) 0 0 0 0  0 0 −(n−1) 0 0 0 0 0  determinantı elde edilir. Bu determinantın hesaplanması ise bize 𝑃𝑒𝑧𝑆 (𝜆) = 𝜆 𝑛−2[𝜆2 − (𝑛 − 1)3] 𝑛 sonucunu verir. Benzer şekilde aşağıdaki sonuç elde edilebilir: Teorem 5.5. 𝐾𝑛 tam grafına ait kenar-Zagreb matrisi kullanılarak elde edilen kenar- Zagreb polinomunun formülü 𝑃𝑒𝑧𝐾 (𝜆) = [𝜆 − (𝑛 − 1) 3][𝜆 + (𝑛 − 1)2]𝑛−1 𝑛 formundadır. İspat. 𝐾𝑛 tam grafına ait kenar-Zagreb polinomunu hesaplamak için  −(n−1)2 −(n −1)2 −(n−1)2 −(n−1)2  −(n −1)2 −(n−1)2 𝑃𝑒𝑧𝐾 (𝜆) = 𝑛 −(n−1)2 −(n −1)2 −(n −1)2 −(n −1)2 −(n−1)2 −(n−1)2 −(n−1)2  determinantına 𝑅1 + 𝑅2 +⋯+ 𝑅𝑛 → 𝑅1 elemanter satır operasyonu uygulanırsa 1 1 1 1 −(n −1)2  −(n −1)2 −(n −1)2 [𝜆 − (𝑛 − 1)3] −(n −1)2 −(n −1)2 −(n −1)2 −(n −1)2 −(n −1)2 −(n −1)2 −(n −1)2  ifadesi elde edilir. Ayrıca 35 (𝑛 − 1)2𝑅1 + 𝑅2 → 𝑅2, (𝑛 − 1)2𝑅1 + 𝑅3 → 𝑅3, ⋮ (𝑛 − 1)2𝑅1 + 𝑅𝑛 → 𝑅𝑛, satır operasyonları uygulanırsa 𝑃𝑒𝑧𝐾 (𝜆) = [𝜆 − (𝑛 − 1) 3][𝜆 + (𝑛 − 1)2]𝑛−1 𝑛 eşitliği elde edilir. Şimdi verilecek olan sonuç benzer şekilde kolayca ispatlanabilir: Teorem 5.6. 𝐾𝑟,𝑠 tam iki parçalı grafına ait kenar-Zagreb matrisi kullanılarak elde edilen kenar-Zagreb polinomunun formülü 𝑃𝑒𝑧 (𝜆) = 𝜆𝑟+𝑠−2 2𝐾 (𝜆 − 𝑟 3𝑠3) 𝑟,𝑠 formundadır. 36 KAYNAKLAR Balakrishnan, R., Ranganathan, K. 2012. A Textbook of Graph Theory, Springer, New York., 425 pp. Berge, C. 2001. The Theory of Graphs, Fletcher & Son Ltd., UK. Biggs, N. L., Lloyd, E. K., Wilson, R. J. 1986. Graph Theory 1736-1936, Oxford University Press, London. Bollobas, B. 1998. Modern Graph Theory, Springer, New York. Bondy, J. A., Murty, U. S. R. 2008. Graph Theory, Springer, New York. Chen, W. 1976. Applied Graph Theory, North-Holland Publishing Company, New York. Foulds, L. R. 1992. Graph Theory Applications, Springer, New York. Golumbic, M. C., Hartman, I. B. 2005. Graph Theory, Combinatorics and Algorithms, Springer, New York. Harary, F. 1994. Graph Theory, Addison-Wesley, USA. Harris, J. M., Hirst, J. L., Mossinghoff, M. J. 2008. Combinatorics and Graph Theory, Springer, New York. Oz, M. S., Yamac, C., Cangul, I. N. 2019. Sum-edge characteristic polynomials of graphs. Journal of Taibah University for Science, 13 (1): 193-200. West, D. B. 1996. Introduction to Graph Theory. Upper Saddle River, Prentice Hall. Yamac, C., Oz, M. S., Cangul, I. N. 2018. Edge Adjacency in Graphs. Proceedings of the Jangjeon Mathematical Society, 21 (3): 357-373. 37 ÖZGEÇMİŞ Adı Soyadı : Çilem YAMAÇ Doğum Yeri ve Tarihi : Aydın, 27/04/1991 Yabancı Dili : İngilizce Eğitim Durumu (Kurum ve Yıl) Lise : Menemen Anadolu Lisesi, 2005-2009 Lisans : Uludağ Üniversitesi, 2009-2015 Yüksek Lisans : Bursa Uludağ Üniversitesi, 2015-2019 İletişim (e–posta) : cilemyamac@hotmail.com 38