Research Information System
11. Uluslararası Marmara Bilimsel Araştırmalar ve İnovasyon Kongresi, İstanbul, Turkey, 24 - 25 October 2025, vol.1, pp.255-264, (Full Text)
In this paper, we present
a comprehensive algebraic framework that associates matrices with maximal
tubings on finite simple graphs. The concept of a tubing, which originates from
the combinatorial structure of graph associahedra, provides a bridge between
graph theory, polyhedral geometry, and matrix analysis. Each maximal tubing is
represented by an intersection matrix whose entries count the number of tubes
that simultaneously contain given vertex pairs. By investigating these
matrices, we establish a correspondence between combinatorial properties of
graphs and linear algebraic invariants such as determinants, inverses, and
characteristic polynomials.
We begin by defining the
intersection matrix of a maximal tubing and demonstrating its behavior under
graph operations such as disjoint union and connected composition. It is shown
that the determinant of this matrix depends solely on the number of connected
components of the underlying graph, and satisfies the elegant formula 
, where k denotes the number of
connected components. Furthermore, the inverse of the intersection matrix is
proven to be equivalent to a modified Laplacian matrix of the Hasse diagram of
the tubing, which encodes the hierarchical structure of nested tubes. The paper
then focuses on explicit examples, particularly complete graphs 
and star graphs 
. For complete graphs, the
intersection matrix has entries 
, and its characteristic polynomial
is expressed in closed form using a recurrence relation linked to Morgan--Voyce
polynomials. For star graphs, a classification of maximal tubings leads to
distinct characteristic polynomials that generalize those of complete graphs.
These findings reveal deep algebraic and combinatorial connections between the structure of graph associahedra and the spectral properties of the matrices defined by their maximal tubings. The framework proposed in this study opens a pathway for further exploration in spectral graph theory, combinatorial matrix theory, and polyhedral geometry, providing a unified approach to study algebraic invariants arising from graph-based polytopal constructions.
Bu çalışmada, sonlu basit
grafikler üzerindeki maksimal tüplemelere (maximal tubings) karşılık gelen
matrisleri tanımlayan kapsamlı bir cebirsel çerçeve sunulmaktadır. Graf
assosiahedra yapısının kombinatoryal temellerinden türeyen tüpleme kavramı,
grafik teorisi, polihedral geometri ve matris analizi arasında bir köprü
oluşturmaktadır. Her bir maksimal tüpleme, belirli bir tepe çifti tarafından
paylaşılan tüplerin sayısını gösteren elemanlara sahip bir kesişim matrisi ile
temsil edilir. Bu matrisler incelenerek, grafiklerin kombinatoryal özellikleri
ile determinant, ters matris ve karakteristik polinom gibi lineer cebirsel
değişmezler arasında bir ilişki kurulmuştur.
Öncelikle maksimal bir
tüplemenin kesişim matrisi tanımlanmış ve bu matrisin ayrık birleşim veya
bağlantılı birleşim gibi grafik işlemleri altındaki davranışı incelenmiştir. Bu
matrisin determinantının yalnızca grafın bağlı bileşenlerinin sayısına bağlı
olduğu ve biçiminde sade bir formül sağladığı
gösterilmiştir; burada k, grafın bağlı bileşenlerinin sayısını ifade
etmektedir. Ayrıca, kesişim matrisinin tersinin, tüplemenin Hasse diyagramına
ait değiştirilmiş Laplasyen matrisi ile özdeş olduğu kanıtlanmıştır. Bu yapı,
iç içe geçmiş tüplerin hiyerarşik düzenini cebirsel olarak kodlamaktadır. Çalışmanın
ilerleyen bölümlerinde özellikle tam grafikler ve yıldız grafikler ele alınmıştır. Tam grafikler için kesişim
matrisinin elemanları biçimindedir ve bu matrisin karakteristik
polinomu, Morgan–Voyce polinomlarıyla ilişkili bir özyinelemeli bağıntı
kullanılarak kapalı biçimde elde edilmiştir. Yıldız grafikler için yapılan
sınıflandırma ise, tam grafiklerin karakteristik polinomlarını genelleştiren
farklı polinom ifadelerine yol açmıştır.
Bu sonuçlar, grafik assosiahedra yapılarını tanımlayan kombinatoryal özellikler ile bu yapılara karşılık gelen matrislerin spektral özellikleri arasında derin bir cebirsel bağ ortaya koymaktadır. Önerilen bu çerçeve, spektral grafik teorisi, kombinatoryal matris teorisi ve polihedral geometri alanlarında daha ileri araştırmalara olanak sağlayarak, grafik temelli politop yapılarından türeyen cebirsel değişmezleri incelemek için birleşik bir yaklaşım sunmaktadır.