Graflarda yerel bağlantılı boyama sayısı
Yükleniyor...
Dosyalar
Tarih
2017
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Ege Üniversitesi, Fen Bilimleri Enstitüsü
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Bu tez çalışmasında, yeni bir boyama ölçümü olarak yerel bağlantılı boyama sayısı tanımlanmıştır. Bir G grafının yerel bağlantılı k-boyaması, k (u,v) sayısı u ve v tepeleri arasındaki içten ayrık yolların maksimum sayısı olmak üzere (1) uv ∈ E(G) ise c(u) ≠ c(v) ve (2) uv ∉ E(G) ve c(u)=c(v)=i ise k(u,v) ≥ i koşullarını sağlayan bir c:V(G) ⟶ {1,2,...,k} dönüşümüdür. G grafında var olan yerel bağlantılı k-boyamaları içinden minimum olan k tamsayısına G grafının yerel bağlantılı boyama sayısı denir ve Xlc (G) ile gösterilir. Bu yeni boyama ile bilinen parametreler arasında bazı genel sonuçlar verilip yerel bağlantılı boyamanın standart boyama ve packing boyama ile ilişkisi incelenmiştir. Temel graf ailelerinde, bazı özel ağaç graflarda ve bazı hiperküp graflarda yerel bağlantılı boyama sayısı hesaplanmıştır. Ardışık toplam, bağlantılı herhangi bir grafa ayrıt ekleme, kartezyen çarpım ve direkt çarpım gibi graf işlemlerinde yerel bağlantılı boyama sayısı çalışılmıştır. Son olarak, bağlantılı herhangi bir grafın yerel bağlantılı boyama sayısını hesaplayan bir algoritma verilmiştir.
In this dissertation, we define a new coloring concept called local connective coloring. A local connective k-coloring of a graph G is a mapping c: V(G) ⟶ {1,2,...,k\} such that (1) If uv ∈ E(G) ise c(u) ≠ c(v) and E(G) and (2) If uv ∉ E(G) and c(u)=c(v)=i , then k(u,v) ≥ i , where k(u,v) is the maximum number of internally disjoint paths between u and v. \end{itemize} The smallest integer k for which there exists a local connective k - coloring of G is called the local connective chromatic number of G, and it is denoted by Xlc (G) . We give some general bounds and compare the local connective chromatic number of a graph with the proper chromatic number and the packing chromatic number of it. We determine the local connective coloring of some several classes of graphs, some special trees and some hypercube graphs. We also study this coloring on some graph operations such as squential join, adding an edge to a graph, Cartesian product and direct product. Consequently, we give an algorithm which is calculated local connective chromatic number of any connected graph.
In this dissertation, we define a new coloring concept called local connective coloring. A local connective k-coloring of a graph G is a mapping c: V(G) ⟶ {1,2,...,k\} such that (1) If uv ∈ E(G) ise c(u) ≠ c(v) and E(G) and (2) If uv ∉ E(G) and c(u)=c(v)=i , then k(u,v) ≥ i , where k(u,v) is the maximum number of internally disjoint paths between u and v. \end{itemize} The smallest integer k for which there exists a local connective k - coloring of G is called the local connective chromatic number of G, and it is denoted by Xlc (G) . We give some general bounds and compare the local connective chromatic number of a graph with the proper chromatic number and the packing chromatic number of it. We determine the local connective coloring of some several classes of graphs, some special trees and some hypercube graphs. We also study this coloring on some graph operations such as squential join, adding an edge to a graph, Cartesian product and direct product. Consequently, we give an algorithm which is calculated local connective chromatic number of any connected graph.
Açıklama
Anahtar Kelimeler
Graf Boyama, Packing Boyama, İçten Ayrık Yol, Yerel Bağlantılılık, Yerel Bağlantılı Boyama Sayısı, Graph Coloring, Packing Coloring, Internally Disjoint Path, Local Connectivity, Local Connective Coloring
