Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Giới hạn trên về số lượng thống trị bị hạn chế toàn phần của một cây
Tóm tắt
Cho G=(V,E) là một đồ thị. Một tập hợp các đỉnh S⊆V được gọi là tập thống trị bị hạn chế toàn phần nếu mọi đỉnh đều có cạnh kề với một đỉnh trong S và mọi đỉnh thuộc V−S đều có cạnh kề với một đỉnh trong V−S. Số lượng thống trị bị hạn chế toàn phần của G, ký hiệu là γtr(G), là kích thước nhỏ nhất của một tập thống trị bị hạn chế toàn phần của G. Một đỉnh hỗ trợ trong một đồ thị là một đỉnh có bậc ít nhất là hai và có cạnh kề với một đỉnh lá. Chúng tôi chứng minh rằng γtr(T)≤⌊(n+2s+ℓ−1)/2⌋, trong đó T là một cây có bậc n≥3, và s và ℓ lần lượt là số lượng đỉnh hỗ trợ và đỉnh lá của T. Chúng tôi cũng định nghĩa một cách xây dựng các cây đạt được giới hạn đã đề cập.
Từ khóa
#cây #đồ thị #thống trị bị hạn chế #đỉnh hỗ trợ #số lượng thống trịTài liệu tham khảo
Chartrand G, Lesniak L (1996) Graphs & digraphs, 3rd edn. Chapman & Hall, London
Chen XG, Ma DX, Sun L (2005) On total restrained domination in graphs. Czechoslov Math J 55(1):165–173
Cyman J, Raczek J (2006) On the total restrained domination number of a graph. Austr J Comb 36:91–100
Hattingh JH, Jonck E, Joubert EJ, Plummer AR (2007) Total restrained domination in trees. Discrete Math 307:1643–1650
Hattingh JH, Jonck E, Joubert EJ, Plummer AR (2008) Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs. Discrete Math 308:1080–1087
Haynes TW, Hedetniemi ST, Slater PJ (1997a) Fundamentals of domination in graphs. New York, Dekker
Haynes TW, Hedetniemi ST, Slater PJ (1997b) Domination in graphs: advanced topics. New York, Dekker
Zelinka B (2005) Remarks on restrained and total restrained domination in graphs. Czechoslov Math J 55(130):165–173