Báo cáo toán học: " Vizing-like conjecture for the upper domination of Cartesian products of graphs – the proof"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Vizing-like conjecture for the upper domination of Cartesian products of graphs – the proof. | Vizing-like conjecture for the upper domination of Cartesian products of graphs - the proof Bostjan Bresar University of Maribor FEECS Smetanova 17 2000 Maribor Slovenia Submitted Jul 7 2004 Accepted Jun 30 2005 Published Jul 19 2005 Mathematics Subject Classifications 05C69 05C99 Abstract In this note we prove the following conjecture of Nowakowski and Rall For arbitrary graphs G and H the upper domination number of the Cartesian product G H is at least the product of their upper domination numbers in symbols r G H r G r H . A conjecture posed by Vizing 7 in 1968 claims that Vizing s conjecture For any graphs G and H Y G H y G y H where Y as usual denotes the domination number of a graph and G H is the Cartesian product of graphs G and H. It became one of the main problems of graph domination cf. surveys 2 and 4 Section and two recent papers 1 6 . The unability of proving or disproving it lead authors to pose different variations of the original problem. Several such variations were studied by Nowakowski and Rall in the paper 5 from 1996. In particular they proposed the following Conjecture Nowakowski Rail For any graphs G and H r G H r G r H where r denotes the upper domination of a graph. In this note we prove this conjecture. In fact if both graphs G and H are nontrivial . have at least two vertices we prove the following slightly stronger bound r G H r G r H 1. Supported by the Ministry of Education Science and Sport of Slovenia under the grant Z1-3073-0101-01. THE ELECTRONIC JOURNAL OF COMBINATORICS 12 2005 N12 1 We start with basic definitions. For graphs G and H the Cartesian product G H is the graph with vertex set V G X V H where two vertices u vj and u2 v2 are adjacent if and only if either u1 u2 and v1v2 2 E H or v1 v2 and u1u2 2 E G . For a set of vertices S Q V G X V H let pG S pH S denote the natural projections of S to V G and V H respectively. A set S c V G of vertices in a graph G is called dominating if for every .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.