% ========================================================================
% estu.cls için Örnek Tez Dosyası (main.tex)
%
% Amaç:
% Bu dosya, estu.cls sınıf dosyasının sağladığı komutların Türkçe bir
% Yüksek Lisans veya Doktora tezi için nasıl kullanılacağını gösteren
% örnek bir ana dosyadır.
%
% Notlar:
% - estu.cls birçok temel paketi zaten yükler (amsmath, amsthm, babel,
% caption, geometry, newtxtext/newtxmath, titlesec, indentfirst, longtable,
% tocloft, xparse vb.). Bu nedenle aşağıda yalnızca tezinizde gerçekten
% ihtiyaç duyacağınız ek paketleri yükleyin.
% - Dil bağımlı iki zorunlu parametreli komutlarda sıralama standardı
% her zaman {İngilizce}{Türkçe} biçimindedir.
% - Bu örnek dosyadaki içerik (metin/teorem/tablo/şekil) tamamen örnektir.
% ========================================================================
% ------------------------------------------------------------------------
% Belge sınıfı seçimi:
% [yl] : Yüksek Lisans tezi
% [dr] : Doktora tezi
% [tr] : Tezin ana dili Türkçe
% [eng] : Tezin ana dili İngilizce
%
% Notlar:
% - Hiç seçenek verilmezse varsayılanlar [yl,tr] olur.
% - Bilinmeyen class seçenekleri hata üretir ve derlemeyi durdurur.
% ------------------------------------------------------------------------
\documentclass[dr]{estu}
% ------------------------------------------------------------------------
% Ek paketler
% estu.cls içinde zaten yüklenmeyen paketleri burada yükleyin.
% ------------------------------------------------------------------------
\usepackage{graphicx} % Şekil/çizim eklemek için
\usepackage{lipsum} % Örnek/dolgu metin üretmek için
% ========================================================================
% TEZ KÜNYE BİLGİLERİ (estu.cls komutları)
% ========================================================================
% ------------------------------------------------------------------------
% Tez başlığı:
% \title{English Title}{Türkçe Başlık}
%
% Notlar:
% - Parametre sırası {İngilizce}{Türkçe} biçimindedir.
% - İngilizce başlık İngilizce sayfalarda kullanılır.
% - Türkçe başlık Türkçe özet sayfasında kullanılır.
% ------------------------------------------------------------------------
\title{A detailed investigation of the classical cops and robbers game defined on various and mutually distinct families of graphs}{Farklı ve birbirinden değişik çeşitli çizge aileleri üzerinde tanımlanan klasik hırsız–polis oyununun ayrıntılı olarak incelenmesi}
% ------------------------------------------------------------------------
% Yazar:
% \author[ek]{Adı SOYADI}
%
% Örnekler:
% \author[un]{Nilay TORUN}
% \author[in]{Betül ÇELİKTEN}
% Notlar:
% - [ek] alanı yalnızca bazı Türkçe sabit metinlerde kullanılır.
% ------------------------------------------------------------------------
\author[ın]{Nazlıcan ÇAKMAK}
% ------------------------------------------------------------------------
% Tarih:
% \date{dd}{mm}{yyyy}
%
% Not:
% Bu, tez savunma sınavı tarihidir. Zorunludur.
% ------------------------------------------------------------------------
\date{18}{07}{2025}
% ------------------------------------------------------------------------
% Danışman(lar):
% Zorunlu:
% \danisman[English Supervisor]{Türkçe Danışman}
% İsteğe bağlı:
% \ikincidanisman[English Co-supervisor]{Türkçe İkinci Danışman}
%
% Not:
% Köşeli parantez içindeki İngilizce argüman verilmezse aynı metin hem
% Türkçe hem İngilizce sayfalarda kullanılır.
% ------------------------------------------------------------------------
\danisman{Prof. Dr. Emrah AKYAR}
\ikincidanisman{Prof. Dr. Handan AKYAR} % İsteğe bağlı
% ------------------------------------------------------------------------
% Proje numarası (BAP vb. destek varsa):
% \projeno{...}
%
% Not:
% Yazılmazsa başlık sayfasında proje destek notu basılmaz.
% ------------------------------------------------------------------------
\projeno{1709F522}
% ------------------------------------------------------------------------
% Anabilim dalı / Bilim dalı:
% \anabilimdali{English Department}{Türkçe Anabilim Dalı}
% \bilimdali{English Programme}{Türkçe Bilim Dalı}
%
% Notlar:
% - Parametre sırası {İngilizce}{Türkçe} biçimindedir.
% - \bilimdali komutu isteğe bağlıdır. Kullanılmazsa bilim dalı satırı
% hiç yazdırılmaz.
% ------------------------------------------------------------------------
\anabilimdali{Department of Mathematics}{Matematik}
\bilimdali{Programme in Analysis and Theory of Functions}{Analiz ve Fonksiyonlar Teorisi}
% ------------------------------------------------------------------------
% Jüri üyeleri:
% Doktora (dr) için en fazla 5 üye kullanılabilir; Yüksek Lisans (yl)
% için ilk 3 üye yeterlidir.
%
% Not:
% \juriuyei her zaman tez danışmanını içermelidir.
% ------------------------------------------------------------------------
\juriuyei{Prof. Dr. Emrah AKYAR}
\juriuyeii{Prof. Dr. Cahit ARF}
\juriuyeiii{Prof. Dr. Kerim ERİM}
\juriuyeiv{Doç. Dr. Ayşe ÖZTÜRK}
\juriuyev{Dr. Öğr. Üyesi Ali YILMAZ}
% ------------------------------------------------------------------------
% Enstitü müdürü:
% \mudur{Unvan Adı SOYADI}
% ------------------------------------------------------------------------
\mudur{Prof. Dr. Harun BÖCÜK}
% ------------------------------------------------------------------------
% Anahtar kelimeler:
% Türkçe : \anahtarkelimeler{...}
% İngilizce: \keywords{...}
%
% Öneri:
% - 3 ila 5 anahtar sözcük kullanın.
% - Virgülle ayırın.
% ------------------------------------------------------------------------
\anahtarkelimeler{Anahtar sözcük 1, Anahtar sözcük 2, Anahtar sözcük 3, Anahtar sözcük 4, Anahtar sözcük 5.}
\keywords{First keyword, Second keyword, Third keyword, Fourth keyword, Fifth keyword.}
% ========================================================================
% METİN İÇİ ORTAMLAR (örnek)
% estu.cls amsthm paketini yüklediği için teorem ortamları burada
% tanımlanabilir.
% ========================================================================
\theoremstyle{definition}
\newtheorem{teorem}{Teorem}[section]
\newtheorem{tanim}[teorem]{Tanım}
\newtheorem{ornek}[teorem]{Örnek}
\newtheorem{sonuc}[teorem]{Sonuç}
\newtheorem{onerme}[teorem]{Önerme}
\newtheorem{lem}[teorem]{Lemma}
% ========================================================================
% BELGE BAŞLANGICI
% ========================================================================
\begin{document}
% ========================================================================
% ÖN SAYFALAR
%
% Not:
% estu.cls içinde \maketitle yeniden tanımlıdır; ancak bu örnekte ön
% sayfalar tek tek komutlarla basılmaktadır.
% ========================================================================
\ickapak % İç kapak (roman sayfa numaralandırmasını başlatır)
\basliksayfasi % Başlık sayfası (proje numarası varsa destek notunu basar)
\jurionayi % Jüri ve enstitü onay / final approval sayfası
\danismanonayi % Danışman onay sayfası
% ------------------------------------------------------------------------
% Türkçe özet ve İngilizce abstract:
% \ozetveabstract{<Türkçe özet>}{<İngilizce abstract>}
%
% Not:
% estu.cls bu iki sayfayı seçilen tez diline göre doğru sırada basar.
% ------------------------------------------------------------------------
\ozetveabstract{
Bu tezde, çizgeler üzerinde bir köşe takip oyunu olan "Hırsız-Polis" oyunu incelenmektedir. Oyunun çizgeler üzerinde incelenmesi fikri, popüler video oyunu Pac-Man’in analizinden kaynaklanmaktadır. Bu oyunda, her hamle çizge üzerindeki bir kenara karşılık gelir. Oyunda hırsız ve polis olmak üzere iki tür oyuncu yer alır. Oyuncu sayısı, çizgenin köşe noktalarıyla sınırlanır. Oyunun başında, her oyuncu bir köşe noktası seçer ve her turda, komşu köşelere hareket edebilir veya mevcut yerlerinde kalabilirler.
Oyunun amacı, en az sayıda polis kullanarak hırsızı yakalamaktır. Hırsızı yakalamak için gereken minimum polis sayısına çizgenin "polis sayısı" denir. Bu tezde, belirli çizge türleri için polis sayısı belirlenmekte ve oyun, çizgenin alt çizgeleri üzerinde oynandığında polis sayısının nasıl değiştiği araştırılmaktadır. Ayrıca, oyunun yeni bir versiyonu tanıtılarak klasik versiyonuyla karşılaştırılmıştır.
}{
The inspiration for studying this game on graphs comes from an analysis of the popular video game Pac-Man. In this game, each move corresponds to an edge in the graph. The game involves two players: the cop and the robber. The number of players is limited by the vertices of the graph. At the beginning of the game, each player selects a vertex, and in each round, they can either move to adjacent vertices or remain in their current positions. The objective of the game is to capture the robber using the minimum number of cops. This minimum number of cops required to catch the robber is called the cop number of the graph.
The main focus of this thesis is to determine the cop number for specific graphs. It explores how the cop number changes when the game is played on various subgraphs of the original graph. Furthermore, a new version of the game is introduced and compared to the classical version.
}
% ------------------------------------------------------------------------
% Etik beyan:
% \etikbeyanname
%
% Not:
% Beyan metni harici bir dosyadan değil, class içinde tanımlı Türkçe ve
% İngilizce metin değişkenlerinden alınır.
% ------------------------------------------------------------------------
\etikbeyanname
% ------------------------------------------------------------------------
% Teşekkür (isteğe bağlı):
% \tesekkur{ ... }
% ------------------------------------------------------------------------
\tesekkur{
Lisansüstü eğitim sürecim boyunca gerçek anlamda danışmanlığını her zaman hissettiğim, bilgi ve deneyimiyle bana çok şey katan değerli danışmanım X'e; bu süreçte her daim paylaşımda bulunduğum, desteğini her zaman yanımda hissettiğim Y'ye ve ihtiyaç duyduğum her anda yanımda olarak varlıklarıyla bana güç veren kıymetli aileme içtenlikle teşekkür ederim.
}
% ========================================================================
% İÇİNDEKİLER / DİZİNLER
% estu.cls bu sayfalar için yardımcı komutlar tanımlar.
% ========================================================================
\icindekilerdizini
\tablolardizini
\sekillerdizini
% ------------------------------------------------------------------------
% Simgeler ve kısaltmalar dizini:
% \simgelerdizini{dosya-adi}
%
% Notlar:
% - Dosya adı uzantısız verilmelidir.
% - İlgili dosyanın içinde yalnızca tablo/longtable içeriği bulunmalıdır.
% ------------------------------------------------------------------------
\simgelerdizini{simgeler-dizini}
% ========================================================================
% ANA METİN
% Arap rakamlarıyla sayfa numaralandırma burada başlatılır.
% ========================================================================
\pagenumbering{arabic}
\renewcommand*{\thepage}{\footnotesize\arabic{page}} % Sayfa numarası 10pt benzeri boyutta görünsün
\setcounter{page}{1}
% ========================================================================
% BÖLÜMLER / ALT BÖLÜMLER (örnek içerik)
% ========================================================================
\section{Giriş}
Çizge kuramı, temelleri 1736 yılında Leonhard Euler tarafından atılan matematiğin bir alt dalıdır. Bu kuram aslında Königsberg’in 7 köprüsü" isimli bir matematik problemi olarak ortaya çıkmıştır. Günümüzde çizge kuramı bilgisayar bilimleri, mühendislik bilimleri, sosyoloji, işletme, genetik bilimi, coğrafya gibi birçok alanda kullanılmaktadır. Çok sayıda gerçek hayat problemi çizgeler yardımıyla modellenip çözülebilmektedir.
Bu tezde, çizgeler üzerinde oynanan bazı köşe takip oyunları, özellikle de Hırsız-Polis oyunu ele alınmıştır. Çizgeler üzerinde köşe takip oyunu, çizgenin köşe noktaları ve kenarları üzerinde oyuncuların belli kurallara göre hamleler yapması olarak tanımlanabilir. Köşe takip oyunlarından en popüler olan Hırsız-Polis oyunu, 1980’lerin başında ortaya atılmış ve günümüze kadar değişerek ve gelişerek ulaşmıştır. Oyun, temelde verilen çizge üzerinde bir hırsızı yakalamaya çalışan polislerden oluşmaktadır. Hırsız ve polislerin sayısı oyunun üzerinde oynandıgı çizgenin köşe noktaları ile sınırlıdır ve her turda oyuncular bulundukları köşe noktalarının komşu köşe noktalarına hamle yapabilir veya oldukları köşe noktasında kalabilirler. Amaç en az sayıda polisle hırsızı yakalamaktır.
\subsection{Temel Tanımlar}
Bu bölümde çizge kuramı ile ilgili sonraki bölümler için gerekli olan bazı temel tanım ve teoremlerden bahsedilmiştir. Bu tanım ve teoremler için [2, 8, 28] referanslarından yararlanılmıştır.
\subsubsection{Çizge ile ilgili tanımlar}
\begin{tanim}
$V\neq \emptyset$ ve sonlu bir küme, $E$ kümesi de $V$ kümesinin iki elemanlı bazı alt kümelerinden oluşan bir küme olmak üzere; $G=(V,E)$ yapısı bir çizge belirtir. Burada $V$ kümesi $G$ çizgesinin köşe noktaları, $E$ kümesi de $G$ çizgesinin kenarlar kümesi olarak adlandırılır.
\end{tanim}
Tablo~\ref{tab:platonikcizgeler} ile Platonik çizgelerin çeşitli özellikleri verilmektedir.
\begin{table}[htb]
\caption[Beş platonik katı cismin çizge karşılıklarının temel özellikleri]{Bu tablo, beş platonik katı cismin çizge karşılıklarının temel özelliklerini göstermektedir. Her çizge için köşe sayısı, kenar sayısı, çizgenin yarıçapı, çapı ve kromatik sayısı verilmiştir. Yarıçap, çizgenin herhangi bir köşesinden diğer köşelere olan en kısa yolların minimum uzunluğunu; çap ise çizgenin en uzak köşe çiftleri arasındaki en kısa yol uzunluğunu ifade etmektedir. Kromatik sayı ise çizgenin boyanmasında gerekli minimum renk sayısını belirtir}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline
\textbf{Çizge} & \textbf{Köşe} & \textbf{Kenar} & \textbf{Yarıçap} & \textbf{Çap} & \textbf{Kromatik Sayı} \\
\hline
Tetrahedron & 4 & 6 & 1 & 1 & 4 \\
Cube & 8 & 12 & 3 & 3 & 2 \\
Octahedron & 6 & 12 & 1 & 2 & 4 \\
Dodecahedron & 20 & 30 & 5 & 5 & 3 \\
Icosahedron & 12 & 30 & 1 & 3 & 4 \\
\hline
\end{tabular}
\label{tab:platonikcizgeler}
\end{table}
\subsubsection{Çizge ile ilgili olmayan bazı tanımlar}
\lipsum[3]
\newpage
\section{Oldukça Uzun Görünebilecek Bir Bölüm Başlığı Olsun Diye Yazılan Bir Başlık}
\lipsum[1-3]
\subsection{Bir Diğer Alt Başlık}
\lipsum[6-7]
\begin{table}[htb]
\caption{Bazı temel diziler ve seriler için genel terim, kısmi toplam ve yakınsaklık özellikleri.
Bu tablo, özellikle analiz derslerinde sıkça karşılaşılan aritmetik ve geometrik diziler ile
bazı klasik serilerin davranışlarını özetlemek amacıyla hazırlanmıştır.}
\label{tab:series-summary}
\footnotesize
\begin{tabular}{|c|c|c|c|}
\hline
\textbf{Dizi / Seri} & \textbf{Genel Terim} & \textbf{$S_n$ (Kısmi Toplam)} & \textbf{Yakınsaklık} \\
\hline
Aritmetik Dizi
& $\displaystyle a_n = a_1 + (n-1)d$
& $\displaystyle S_n = \frac{n}{2}(2a_1 + (n-1)d)$
& Iraksak ($d\neq 0$) \\
\hline
Geometrik Dizi
& $\displaystyle a_n = a_1 r^{\,n-1}$
& $\displaystyle S_n = a_1 \frac{1-r^n}{1-r}$
& $|r|<1$ ise yakınsak \\
\hline
Geometrik Seri
& $\displaystyle \sum_{n=0}^{\infty} ar^n$
& $\displaystyle \frac{a}{1-r}$
& $|r|<1$ \\
\hline
Harmonik Seri
& $\displaystyle \sum_{n=1}^{\infty} \frac{1}{n}$
& ---
& Iraksak \\
\hline
$p$-Serisi
& $\displaystyle \sum_{n=1}^{\infty} \frac{1}{n^p}$
& ---
& $p>1$ ise yakınsak \\
\hline
Üstel Seri
& $\displaystyle \sum_{n=0}^{\infty} \frac{x^n}{n!}$
& $\displaystyle e^x$
& Her $x\in\mathbb{R}$ için yakınsak \\
\hline
\end{tabular}
\end{table}
\subsubsection{Diğer tanımlar}
Bir $G$ çizgesinin köşe noktaları veya kenarlar kümesinden bahsedildiğini belirtmek için genellikle $V(G)$ ve $E(G)$ gösterimleri kullanılır. Burada $G$ çizgesinin herhangi iki $u$ ve $v$ köşe noktasını birleştiren kenar genel olarak $\{u,v\}$ ile ya da kısaca $uv$ ile gösterilir.
Çizgeler genellikle; köşe noktaları düzlemde noktalar, kenarları ise köşe noktalarına karşılık gelen bu noktalar arasına çizilen çizgilerden oluşan diyagramlar yardımıyla gösterilir.
%% Şekiller için not:
%% \begin{center} ... \end{center} ortamı yerine,
%% \begin{figure} ortamı içinde \centering komutunun kullanılması önerilir.
%% Bu yöntem, LaTeX'in şekil yerleşimini daha doğru yönetmesini sağlar.
\begin{figure}[htb]
\centering
% Not: Şekillerin "sekiller/" klasörü altında tutulduğu varsayılmıştır.
\includegraphics[width=0.40\textwidth]{sekiller/ornek-cizge.pdf}
\caption{Bir $G$ çizgesi örneği olsun diye koyulan ama koyulmasa da olabilecek olan bir şekil}
\label{fig:ornekcizge}
\end{figure}
\begin{tanim}
Bir $u \in V(G)$ köşe noktası için, $u$ köşe noktasına gelen kenarların sayısına $u$ köşe noktasının derecesi denir ve $\deg(u)$ ile gösterilir.
\end{tanim}
\begin{teorem}[El Sıkışma Teoremi]
Bir $G=(V,E)$ çizgesinde tüm köşe noktalarının dereceleri toplamı, kenar sayısının iki katına eşittir. Yani,
\begin{equation}
\sum_{v\in V} \deg(v)= 2|E|
\end{equation}
olur.
\end{teorem}
\begin{proof}
Her bir kenarın iki uç noktasının çizgenin toplam derecesine katkısı 2 olacağından tüm noktaların derecelerinin toplamı kenar sayısının iki katına eşit olur.
\end{proof}
Tablo~\ref{tab:platonikcizgeler2} ile Platonik çizgelerin çeşitli özellikleri verilmektedir.
\begin{table}[htb]
\caption{Her çizge için köşe sayısı, kenar sayısı, çizgenin yarıçapı, çapı ve kromatik sayısı verilmiştir. Yarıçap, çizgenin herhangi bir köşesinden diğer köşelere olan en kısa yolların minimum uzunluğunu; çap ise çizgenin en uzak köşe çiftleri arasındaki en kısa yol uzunluğunu ifade etmektedir.}
\footnotesize
\begin{tabular}{|l|c|c|c|c|c|}
\hline
\textbf{Çizge} & \textbf{Köşe} & \textbf{Kenar} & \textbf{Yarıçap} & \textbf{Çap} & \textbf{Kromatik Sayı} \\
\hline
Tetrahedron & 4 & 6 & 1 & 1 & 4 \\
Cube & 8 & 12 & 3 & 3 & 2 \\
Octahedron & 6 & 12 & 1 & 2 & 4 \\
Dodecahedron & 20 & 30 & 5 & 5 & 3 \\
Icosahedron & 12 & 30 & 1 & 3 & 4 \\
\hline
\end{tabular}
\label{tab:platonikcizgeler2}
\end{table}
\subsection{Bir Başka Alt Başlık}
\lipsum[1-2]
\subsubsection{Örnek olsun diye yazılan bir başka üçüncü düzey başlık örneği}
\lipsum[1]
\subsubsection{Bir tane daha örnek olsun diye yazılan bir başka üçüncü düzey başlık örneği}
\lipsum[2]
\begin{table}[htb]
\caption{Bazı temel türevler ve integraller}
\label{tab:calc-basic}
\footnotesize
\begin{tabular}{|c|c|c|}
\hline
\textbf{Fonksiyon $f(x)$} & \textbf{Türev $f'(x)$} & \textbf{Belirsiz integral $\displaystyle \int f(x)\,dx$} \\
\hline
$\displaystyle x^n \ (n\neq -1)$
& $\displaystyle n x^{n-1}$
& $\displaystyle \frac{x^{n+1}}{n+1}+C$ \\
\hline
$\displaystyle \sin x$
& $\displaystyle \cos x$
& $\displaystyle -\cos x + C$ \\
\hline
$\displaystyle \cos x$
& $\displaystyle -\sin x$
& $\displaystyle \sin x + C$ \\
\hline
$\displaystyle e^x$
& $\displaystyle e^x$
& $\displaystyle e^x + C$ \\
\hline
$\displaystyle \ln x \ (x>0)$
& $\displaystyle \frac{1}{x}$
& $\displaystyle x\ln x - x + C$ \\
\hline
$\displaystyle \frac{1}{1+x^2}$
& $\displaystyle \frac{-2x}{(1+x^2)^2}$
& $\displaystyle \arctan x + C$ \\
\hline
\end{tabular}
\end{table}
\begin{figure}[htb]
\centering
\includegraphics[width=0.5\linewidth]{sekiller/petersen-cizge.pdf}
\caption[Petersen çizge]{Petersen çizge, 10 köşe ve 15 kenara sahip, 3-regüler bir çizgedir. Çizge, yüksek simetriye sahip olup, Hamilton döngüsü içermez. Kapsamlı bir örnek olarak çizge kuramı çalışmalarında sıkça kullanılır.}
\label{fig:petersen-cizge}
\end{figure}
\subsection{Bir Diğer Uzunca Sayılabilecek İki Satır Olacak Şekilde Bir Alt Başlık Örneği}
\lipsum[4-5]
Çizgeler üzerinde bir başka çarpım da güçlü çarpım (strong product) işlemidir. $G$ ve $H$ çizgelerinin güçlü çarpımı olan $G \boxtimes H$ çizgesi, köşe noktaları kümesi
\[
V(G \boxtimes H) = V(G) \times V(H)
\]
ve kenarlar kümesi de
\begin{eqnarray*}
E(G \boxtimes H) & = & \left\{
\{(u, u^\prime), (v, v^\prime)\} \, \middle| \, \left( u = v \mbox{ ve } \{u^\prime, v^\prime\} \in E(H) \right) \mbox{ veya } \right. \\
& & \left( u^\prime = v^\prime \mbox{ ve } \{u, v\} \in E(G) \right) \mbox{ veya } \\
& & \left. \left( \{u, v\} \in E(G) \mbox{ ve } \{u^\prime, v^\prime\} \in E(H) \right)
\right\}
\end{eqnarray*}
şeklinde tanımlanan bir çizgedir.
Örneğin, Şekil~\ref{fig:guclucarpim} ile $P_2 \boxtimes P_3$ ve $P_2 \boxtimes C_3$ güçlü çarpım çizgeleri gösterilmektedir.
\begin{figure}[htb]
\centering
\includegraphics[width=0.6\textwidth]{sekiller/guclu-carpim.pdf}
\caption{$P_2 \boxtimes P_3$ ve $P_2 \boxtimes C_3$ güçlü çarpım çizgeleri}
\label{fig:guclucarpim}
\end{figure}
Enomoto ve diğerleri, çeşitli çizgelerin güçlü çarpımlarının oyun kromatik sayıları ile ilgili önemli sonuçlar elde etmiştir \cite{Enomoto}.
\begin{teorem}[\cite{Enomoto}]
Keyfi $t \ge 2$ çift tamsayısı için
\[
\chi_g(G \boxtimes K_t) > t \, \chi_g(G)
\]
eşitsizliğini sağlayan sonsuz sayıda $G$ çizgesi vardır.
\end{teorem}
$t$ tamsayısının tek olması durumunda bu iddianın geçerli olup olmadığı ise kanıtlanamamıştır.
Çizgelerin bir başka çarpımı da nokta çarpımı (corona product) olarak adlandırılan çarpımdır. Eğer $G$ ve $H$ çizgeleri sırasıyla $n_1$ ve $n_2$ köşe noktalı çizgeler ise, $G$ ve $H$ çizgelerinin nokta çarpımı olan $G \circ H$ çizgesi, $G$ çizgesinin bir kopyası ile $H$ çizgesinin $n_1$ tane kopyası alınıp, $G$ çizgesinin $i$. köşe noktası ile $H$ çizgesinin $i$. kopyasının tüm köşe noktaları arasına bir kenar çizilmesiyle elde edilir.
Örneğin, Şekil~\ref{fig:noktacarpim} ile $C_4 \circ C_3$ nokta çarpım çizgesinin elde edilişi gösterilmektedir.
\begin{figure}[htb]
\centering
\includegraphics[width=0.6\textwidth]{sekiller/nokta-carpim.pdf}
\caption{$C_4 \circ C_3$ nokta çarpım çizgesi}
\label{fig:noktacarpim}
\end{figure}
Çizgelerin nokta çarpımının oyun kromatik sayıları ile ilgili literatürde çok fazla çalışma bulunmasa da, \cite{Bokhary} ve diğerleri $P_m \circ C_m$ nokta çarpım çizgesinin oyun kromatik sayısını belirlemiştir.
\begin{teorem}[\cite{Bokhary}]
Her $n \ge 2$ ve $m \ge 3$ için
\[
\chi_g(C_m \circ P_m) = 4
\]
olur.
\end{teorem}
Bazı $n$ doğal sayıları için $\gamma_g(P_n)$, $\gamma^\prime_{g}(P_n)$, $\gamma_{tg}(P_n)$ ve $\gamma^\prime_{tg}(P_n)$ değerleri Tablo~\ref{table:P_n} ile verilmiştir.
\begin{table}[htb]
\caption{Bazı $n$ sayıları için $\gamma_g(P_n)$, $\gamma^\prime_{g}(P_n)$, $\gamma_{tg}(P_n)$ ve $\gamma^\prime_{tg}(P_n)$ değerleri}
\begin{tabular}{c|c|c|c|c|c|c|c|c}
\hline
$n$ & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline \hline
$\gamma_g(P_n)$ & 1 & 2 & 3 & 3 & 3 & 4 & 5 & 5 \\ \hline
$\gamma^\prime_{g}(P_n)$ & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 \\ \hline
$\gamma_{tg}(P_n)$ & 2 & 3 & 3 & 4 & 5 & 6 & 6 & 7 \\ \hline
$\gamma^\prime_{tg}(P_n)$ & 2 & 3 & 4 & 4 & 5 & 6 & 6 & 7 \\ \hline
\end{tabular}
\label{table:P_n}
\end{table}
\cite{Henning} ile verilen çalışmada sunulan, oyun baskınlık sayısına ilişkin genel üst sınır ve kanıt aşağıda sunulmuştur.
\begin{teorem}[\cite{Henning}]
$G$, domine edilmemiş izole köşe nokta bulundurmayan, kısmen domine edilmiş bir çizge olsun. Eğer $G$ çizgesi, $d$ tane domine edilmiş ve $s$ tane doymuş köşe noktasına sahip, $n$ köşe noktalı bir çizge ise,
\[
\gamma_g(G)\leq\frac{1}{3}(2n-s-d)
\qquad \mbox{ve}\qquad
\gamma^\prime_g(G)\leq\frac{1}{3}(2n-s-d+1)
\]
eşitsizlikleri sağlanır.
\end{teorem}
\begin{proof}
Genelliği bozmaksızın, $G$ çizgesinin küçültülmüş bir çizge olduğu varsayılsın. Bu varsayım, oyunun sonucunu etkilemeyeceği için sakıncasızdır. Bu durumda $G$ çizgesinin $s \geq 0$ tane doymuş köşe noktası vardır; bu köşe noktaları $G$ çizgesinde izoledir ve varsa geri kalan $n - s$ köşe noktası izole değildir. Kanıt, $n - s$ üzerinden tümevarım yoluyla yürütülür.
Eğer $n - s = 0$ ise, $G$ çizgesinin tüm köşe noktaları doymuştur. Bu durumda $n = s = d$ olur ve $\gamma_g(G) = \gamma^\prime_g(G) = 0 = (2n - s - d)/3$ eşitliği sağlanır. Dolayısıyla temel durumda eşitsizliğin geçerli olduğu görülür.
$n-s>0$ olsun. O halde $G$ çizgesinin en az iki köşe noktası bulunduran, en az bir bileşeni vardır. Tümevarım hipotezi olarak, $G^\prime$ küçültülmüş çizgesinin $d^\prime$ tane domine edilmiş, $s^\prime> s$ olmak üzere, $s^\prime$ tane doymuş köşe noktasına sahip, $n$ köşe noktalı bir çizge olduğu ve $\gamma_g(G^\prime)\leq\frac{1}{3}(2n-s^\prime-d^\prime)$ ile $\gamma^\prime_g(G^\prime)\leq\frac{1}{3}(2n-s^\prime-d^\prime+1)$ eşitsizliklerinin geçerli olduğu kabul edilsin.
$G$ çizgesinin her biri $K_2$ ile izomorfik olan $k\geq1$ tane, en az bir köşe noktası bulunduran bileşene sahip olduğu varsayılsın. Bu durumda $n-s=2k$ ve her $K_2$ bileşeni en az bir domine edilmemiş köşe noktası içerdiğinden, $d\leq s+k$ eşitsizliği sağlanır. Ayrıca oyunun geri kalanında her bileşende yalnızca bir hamle yapılması mümkündür. O halde
\[
\gamma_g(G)=\gamma^\prime_g(G)=k=\frac{1}{3}(2(s+2k)-s-(s+k))\leq\frac{1}{3}(2n-s-d)
\]
olup her iki sınır da geçerlidir. Dolayısıyla, $G$ çizgesinin en az üç köşe noktasına sahip en az bir bileşen içerdiği durum incelenmelidir. Aksi halde eşitsizliklerin geçerli olduğu görülmüştür.
$G$ çizgesinin en az üç köşe noktasına sahip, en az bir bileşen içerdiği varsayılsın. İlk hamleyi yapan Oyalayan oyuncu olsun. $G^\prime$, $d^\prime$ tane domine edilmiş ve $s^\prime$ tane doymuş köşe noktasına sahip, $n$ köşe noktalı küçültülmüş çizgeyi göstersin. $G^\prime$ çizgesinin, izole olmayan domine edilmemiş köşe noktası içermediğine dikkat edilmelidir. Çünkü $G^\prime$ çizgesinin en az bir köşe noktasına sahip her bileşeni, en az bir tane domine edilmemiş köşe noktasına sahiptir ve $G^\prime$ çizgesindeki domine edilmemiş tüm köşe noktaları, $G$ çizgesinde sahip olduğu dereceye sahiptir. Oyalayan oyuncunun hamlesi en az bir yeni köşe noktasını domine eder ve en az bir yeni köşe noktasını (hamle olarak seçip oynadığı köşe noktası) doyurur. Buradan $d^\prime\geq d+1$ ve $s^\prime\geq s+1$ sonuçları elde edilir. O halde
\begin{eqnarray*}
\gamma^\prime_g(G) & = & 1+\gamma_g(G^\prime) \\
& \leq & 1+\frac{1}{3}(2n-s^\prime-d^\prime) \\
& \leq & 1+\frac{1}{3}(2n-(s+1)-(d+1)) \\
& = & \frac{1}{3}(2n-s-d+1)
\end{eqnarray*}
olup eşitsizlik sağlanır. Burada ilk eşitlik Oyalayan oyuncunun hamlesinin optimalliğinden, ikinci eşitsizlik $G^\prime$ çizgesine uygulanan tümevarım hipotezinden, üçüncü eşitsizlik ise yukarıda elde ettiğimiz sonuçlardan kaynaklanır.
Şimdi de ilk hamleyi yapanın Baskın oyuncu olduğu varsayılsın. $C$, $G$ çizgesinin en az üç köşe noktasına sahip, keyfi bir bileşeni olsun. İncelenmesi gereken iki durum söz konusudur. Her iki durum da incelenirken Baskın oyuncunun hamlesi belirlenerek, $G^\prime$ çizgesinin $d^\prime$ tane domine edilmiş ve $s^\prime$ tane doymuş köşe noktasına sahip, $n$ köşe noktalı küçültülmüş çizgeyi gösterdiği kabul edilsin.
\begin{description}
\item[1. Durum:] $C$ bileşeninin bir yaprağı vardır. $v$ köşe noktası, $C$ bileşeninin herhangi bir yaprağı ve $u$ da onun komşusu olsun.
Hem $v$ köşe noktası hem de $u$ köşe noktası domine edilmemişse, o zaman Baskın oyuncu $v$ köşe noktasını seçer, böylece hem $u$ hem de $v$ köşe noktasını domine eder ve doyurur. Buradan $s^\prime\geq s+2$ ve $d^\prime\geq d+2$ sonuçları elde edilir. O halde
\begin{eqnarray*}
\gamma_g(G) & \leq & 1+\gamma^\prime_g(G^\prime) \\
& \leq & 1+\frac{1}{3}(2n-s^\prime-d^\prime+1) \\
& \leq & 1+\frac{1}{3}(2n-(s+2)-(d+2)+1) \\
& = & \frac{1}{3}(2n-s-d)
\end{eqnarray*}
olup eşitsizlik sağlanır. Burada ilk eşitsizlik Baskın oyuncunun hamlesinin optimalliğinden, ikinci eşitsizlik $G^\prime$ çizgesine uygulanan tümevarım hipotezinden, üçüncü eşitsizlik ise yukarıda elde edilen sonuçlardan kaynaklanır.
Bunun yerine, $v$ köşe noktasının domine edilmemiş fakat $u$ köşe noktasının domine edilmiş olduğu varsayılsın. $C$ bileşeni en az üç köşe noktasına sahip olduğundan ve domine edilmiş köşe noktaları arasında kenar bulunmadığından, bu durum $u$ köşe noktasının $v$ köşe noktasından farklı, domine edilmemiş bir $w$ komşusuna sahip olduğu anlamına gelir. Bu durumda Baskın oyuncu hamlesini $u$ köşe noktasını seçerek yapar ve dolayısıyla $v$ ile $w$ köşe noktalarını domine edip, $u$ ile $w$ köşe noktalarını doyurur. Bir önceki durumda olduğu gibi $s^\prime\geq s+2$ ve $d^\prime\geq d+2$ sonuçları elde edilerek aynı şekilde $\gamma_g(G)\leq (2n-s-d)/3$ eşitsizliği gerçeklenir.
Geriye kalan tek olasılık olan, $v$ köşe noktasının domine edilmiş fakat $u$ köşe noktasının domine edilmemiş olduğu varsayılsın. Eğer $u$ köşe noktasının henüz domine edilmemiş bir $w$ komşusu varsa, Baskın oyuncu bu $w$ köşe noktasını seçerek hamle yapar. Böylece $u$ ile $w$ köşe noktalarını domine edip, $v$ ile $w$ köşe noktalarını doyurur. Buradan da yine $s^\prime\geq s+2$ ve $d^\prime\geq d+2$ sonuçları elde edilerek $\gamma_g(G)\leq (2n-s-d)/3$ eşitsizliğinin gerçeklendiği görülür. Son olarak eğer $u$ köşe noktasının henüz domine edilmemiş bir komşusu yoksa, $C$ bileşeni en az üç köşe noktasına sahip olduğundan, $u$ köşe noktasının $v$ köşe noktasından farklı en az bir $t$ komşusu vardır. Bu durumda Baskın oyuncu $t$ köşe noktasını seçerek hamle yapar. Böylece $u$ köşe noktasını domine eder ve $t$ ile $v$ köşe noktalarını doyurur. $u$ köşe noktasının domine edilmemiş komşusu bulunmadığından, bu hamle $u$ köşe noktasını da doyurur. Buradan $s^\prime\geq s+3$ ve $d^\prime\geq d+1$ sonuçları elde edilir. O halde
\begin{eqnarray*}
\gamma_g(G) & \leq & 1+\gamma^\prime_g(G^\prime) \\
& \leq & 1+\frac{1}{3}(2n-s^\prime-d^\prime+1) \\
& \leq & 1+\frac{1}{3}(2n-(s+3)-(d+1)+1) \\
& = & \frac{1}{3}(2n-s-d)
\end{eqnarray*}
olup eşitsizlik yine sağlanır.
\item[2. Durum:] $C$ bileşeninin yaprağı yoktur. İlk olarak $C$ bileşenindeki bazı domine edilmemiş $v$ köşe noktalarının, en az iki domine edilmemiş komşusu olduğu varsayılsın. Bu durumda Baskın oyuncu $v$ köşe noktası ve onun domine edilmemiş komşuları olmak üzere, en az üç köşe noktasını domine eden $v$ köşe noktasını seçerek hamlesini yapar. Aynı zamanda bu hamle ile $v$ köşe noktasını doyurur. Buradan $s^\prime\geq s+1$ ve $d^\prime\geq d+3$ sonuçları elde edilir. O halde
\begin{eqnarray*}
\gamma_g(G) & \leq & 1+\gamma^\prime_g(G^\prime) \\
& \leq & 1+\frac{1}{3}(2n-s^\prime-d^\prime+1) \\
& \leq & 1+\frac{1}{3}(2n-(s+1)-(d+3)+1) \\
& = & \frac{1}{3}(2n-s-d)
\end{eqnarray*}
olup eşitsizlik sağlanır.
\end{description}
$C$ bileşeninde hiçbir domine edilmemiş köşe noktasının, iki veya daha fazla domine edilmemiş komşusunun var olmadığı durum incelenmelidir. Aksi halde istenen sınırın geçerli olduğu yukarıda görülmüştür. $C$ bileşenindeki bazı domine edilmemiş köşe noktalarının, tam olarak bir tane domine edilmemiş komşusu olduğu varsayılsın. $u$ köşe noktası, $v$ köşe noktasının domine edilmemiş komşusu olsun. Varsayım gereği, $u$ köşe noktasının başka domine edilmemiş komşusu yoktur. Baskın oyuncu hamlesini $u$ köşe noktasını seçerek yapar. Bu hamle hem $u$ hem de $v$ köşe noktasını domine eder ve doyurur. Buradan $s^\prime\geq s+2$ ve $d^\prime\geq d+2$ sonuçları elde edilerek daha önce olduğu gibi $\gamma_g(G)\leq (2n-s-d)/3$ eşitsizliği gerçeklenir.
Kalan son olasılık olan, $C$ bileşeninin hiçbir domine edilmemiş komşu köşe noktası çifti içermediği varsayılsın. $G^\prime$ izole edilmemiş ve domine edilmemiş bir köşe noktası içermediğinden, $C$ en az bir çift komşu köşe noktası içerir. Bunlardan da en az birinin domine edilmiş olması gerekir. $v$ köşe noktası, $C$ bileşeninde domine edilmiş bir köşe noktası olsun. $C$ bileşeninin yaprağı bulunmadığından, $v$ köşe noktasının en az iki komşusu var olmalıdır. Küçültülmüş çizgede hiçbir kenar iki domine edilmiş köşe noktasını birleştiremeyeceğinden, $v$ köşe noktasının tüm komşuları domine edilmemiştir. $u$ ve $w$ köşe noktaları, $v$ köşe noktasının domine edilmemiş iki komşusu olsun. Varsayım gereği, ne $u$ ne de $w$ köşe noktasının domine edilmemiş komşuları yoktur. Bu durumda Baskın oyuncu hamlesini, hem $u$ hem de $w$ köşe noktalarını domine eden $v$ köşe noktasını seçerek yapar. Böylece $u$, $v$ ve $w$ köşe noktalarını doyurur. Buradan $s^\prime\geq s+3$ ve $d^\prime\geq d+2$ sonuçları elde edilir. O halde
\begin{eqnarray*}
\gamma_g(G) & \leq & 1+\gamma^\prime_g(G^\prime) \\
& \leq & 1+\frac{1}{3}(2n-s^\prime-d^\prime+1) \\
& \leq & 1+\frac{1}{3}(2n-(s+3)-(d+2)+1) \\
& < & \frac{1}{3}(2n-s-d)
\end{eqnarray*}
olup eşitsizlik yine sağlanır. Bu da ispatı tamamlar.
\end{proof}
% ========================================================================
% KAYNAKÇA
%
% Not:
% Burada klasik thebibliography örneği verilmiştir.
% Eğer BibTeX veya Biber kullanılacaksa bu bölüm farklı kurgulanmalıdır.
% ========================================================================
\clearpage
\addcontentsline{toc}{section}{\refname}
\titleformat*{\section}{\bfseries\normalsize\centering}
% Eğer kaynak sayısı 9'dan fazlaysa, {9} yerine {99} gibi daha geniş bir değer veriniz.
\begin{thebibliography}{9}
\bibitem{Akyar} Akyar, E. (2021). \textit{Çizge Kuramına (Graf Teorisine) Giriş}, Seçkin Yayıncılık, Ankara.
\bibitem{Bokhary} Bokhary, S. A. U. H. and Iqbal, T. and Ali, U. (2018). Game chromatic number of {C}artesian and corona product graphs.
\textit{Journal of Algebra Combinatorics Discrete Structures and Applications}, 5 (3), 129--136.
\bibitem{Enomoto} Enomoto H., Fujisawa J. and Matsumoto N. (2023).
Game chromatic number of strong product graphs.
\textit{Discrete Mathematics}, 346 (1), 113--162.
\bibitem{Henning} Henning, M. A. and Kinnersley W. B. (2016).
Domination Game: A proof of the 3/5--Conjecture for graphs with minimum degree at least two.
\textit{SIAM Journal On Discrete Mathematics}, 30 (1), 20--35.
\end{thebibliography}
% ------------------------------------------------------------------------
% Ekler:
% \ekler
% veya
% \ekler{dosya-adi}
%
% Not:
% Dosya adı verilirse uzantısız yazılmalıdır.
% ------------------------------------------------------------------------
\ekler
% ------------------------------------------------------------------------
% Özgeçmiş:
% \ozgecmis
% veya
% \ozgecmis{dosya-adi}
%
% Not:
% Dosya adı verilirse uzantısız yazılmalıdır.
% ------------------------------------------------------------------------
\ozgecmis{ozgecmis} % ozgecmis.tex dosyası mevcut olmalı
\end{document}
