Chu trình Hamilton trong đồ thị tách cực G = S (I hợp K, E) với deg(u) nhỏ hơn hoặc bằng 2 với mọi u thuộc I

Chia sẻ: Vi4mua Vi4mua | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

12
lượt xem 0
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đồ thị G = (V ,E) được gọi là đồ thị tách cực nếu tồn tại phân hoạch V = I hợp K sao cho đồ thị con của G cảm sinh trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị đầy đủ. Chúng ta ký hiệu đồ thị tách cực đó là S (I hợp K, E). Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và P. L. Hammer.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chu trình Hamilton trong đồ thị tách cực G = S (I hợp K, E) với deg(u) nhỏ hơn hoặc bằng 2 với mọi u thuộc I

94 Lê Xuân Hùng CHU TRÌNH HAMILTON TRONG ĐỒ THỊ TÁCH CỰC G = S ( I  K , E) VỚI deg(u)  2 VỚI MỌI u  I HAMILTON CYCLES IN SPLIT GRAPHS G = S (I  K , E) WITH deg(u)  2 FOR ANY u  I Lê Xuân Hùng Trường Đại học Tài nguyên và Môi trường Hà Nội; lxhung@hunre.edu.vn Tóm tắt - Đồ thị G = (V , E ) được gọi là đồ thị tách cực nếu tồn tại phân hoạch V = I  K sao cho đồ thị con của G cảm sinh trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị đầy đủ. Chúng ta ký hiệu đồ thị tách cực đó là S ( I  K , E ) . Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và P. L. Hammer. Trong bài báo này chúng ta sẽ nghiên cứu sự tồn tại chu trình Hamilton trong lớp đồ thị tách cực G = S ( I  K , E ) với I  K và deg(u )  2 với mọi u  I . Chúng ta chứng minh được rằng đồ thị tách cực G có chu trình Hamilton khi và chỉ khi ' ' ' N ( I )  I với mọi   I  I và N I ( v )  2 với mọi v  K . Abstract - A graph G = (V , E ) is called a split graph if there exists a partition V = I  K so that the subgraphs of G induced by I and K are empty and complete, respectively. We will denote such a graph by S ( I  K , E ) . The notion of split graphs was introduced in 1977 by S. Foldes and P. L. Hammer. In this paper, we characterize Hamiltonian graphs in the class of split graphs G = S ( I  K , E ) with I  K and deg( u )  2 for any u  I . We prove that split graph G has Hamilton cycle if and only if ' ' ' N ( I )  I for any   I  I and N I ( v )  2 for any v  K . Từ khóa - đồ thị tách cực; chu trình Hamilton; đồ thị 2 phần; đồ thị đầy đủ; đồ thị rỗng. Key words - split graph; Hamilton cycle; bipartite graph; complete graph; empty graph. 1. Đặt vấn đề Tất cả các đồ thị được nói tới trong bài báo này là những đơn đồ thị hữu hạn, vô hướng, không có khuyên và không có cạnh bội. Nếu G là một đồ thị, thì V (G) (hoặc V ) được gọi là tập đỉnh và E(G) (hoặc E ) được gọi là tập cạnh. Tập hợp tất cả các đỉnh là hàng xóm của tập con S  V (G) được ký hiệu là N G (S ) (hoặc N (S ) ). Với mỗi đỉnh v V (G) , [8]. Liên quan tới độ bền (toughness) của đồ thị, một điều kiện đủ để đồ thị tách cực có chu trình Hamilton đã được công bố vào năm 1996 bởi các tác giả Kratsch, Lehel và Muller [7]. Trong những năm gần đây, các tác giả Ngô Đắc Tân và Lê Xuân Hùng đã đưa ra một số điều kiện cần và đủ để một đồ thị tách cực có chu trình Hamilton [6], [10], [11]. Tuy vậy, cho đến nay vấn đề sự tồn tại chu trình Hamilton trong lớp đồ thị tách cực vẫn chưa được giải quyết triệt để, vẫn cần tiếp tục được nghiên cứu. Trong bài báo này, tác giả tiếp tục nghiên cứu sự tồn tại chu trình Hamilton cho đồ thị tách cực G = S (I  K , E) với deg(u)  2 với mọi u  I . ta gọi N G (v) là bậc của đỉnh v, ký hiệu là deg(v). Với đồ thị G = (V , E) , số min deg(v) | v V  được gọi là bậc cực tiểu của G , ký hiệu là  (G) . Đồ thị con của G cảm sinh trên tập U  V (G) được ký hiệu là G[U ] . Ngoài ra, một số khái niệm và ký hiệu khác được định nghĩa trong [1]. Đồ thị G = (V , E) được gọi là đồ thị tách cực nếu tồn tại một phân hoạch V = I  K sao cho đồ thị con G[ I ] là đồ thị rỗng và đồ thị con G[ K ] là đồ thị đầy đủ. Chúng ta ký hiệu đồ thị tách cực là S (I  K , E) . Khái niệm đồ thị tách cực được định nghĩa đầu tiên vào năm 1977 bởi Foldes và Hammer [4]. Các đồ thị này đã và đang được nghiên cứu nhiều bởi vì chúng có liên quan nhiều đến các vấn đề về tổ hợp [3], [5], [9]. Việc nghiên cứu bài toán Hamilton đối với lớp đồ thị tách cực bắt đầu được nghiên cứu vào năm 1980 bởi Burkard và Hammer, các tác giả đã đưa ra một điều kiện cần nhưng không là điều kiện đủ để đồ thị tách cực G = S (I  K , E) với | I || K | có chu trình Hamilton [2]. Năm 1985, Peemoller đã đưa ra một số điều kiện cần tương đương với điều kiện cần của Burkard và Hammer 2. Nội dung nghiên cứu 2.1. Một số kết quả liên quan Giả sử C là một chu trình trong đồ thị G = (V , E) . Ta sẽ ký hiệu chu trình C với một chiều xác định là C và chu trình C với chiều ngược lại là C . Nếu u, v V (C) , thì ta ký hiệu các đỉnh liên tiếp của C từ u tới v theo chiều đã xác định trên C là u Cv và ký hiệu các đỉnh liên tiếp của C từ u tới v theo chiều ngược lại xác định trên C là u Cv . Ta sẽ xem u Cv và u Cv như là các đường và cũng như là + − các tập đỉnh. Nếu u V (C) , thì ta ký hiệu u và u lần lượt là các đỉnh đứng ngay sau và ngay trước đỉnh u trên C . Các khái niệm tương tự như đã mô tả ở trên cho các chu trình cũng sẽ được sử dụng cho các đường. Nếu U  V (G) , thì ta ký hiệu tập U  N G (u ) là N U (u ) . ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 3(124).2018 Giả sử G = S (I  K , E) là đồ thị tách cực. Ta ký hiệu đồ thị G* = B( I  K , E * ) là đồ thị 2 phần thu được từ đồ thị G bằng cách xóa đi tất cả các cạnh có cả hai đỉnh đầu mút đều thuộc K . Bổ đề 1 [9]. Nếu đồ thị tách cực G = S ( I  K , E) với I = m và K = n có chu trình Hamilton, thì N ( I ' )  I ' với mọi   I '  I thỏa mãn | I ' | min m, n −1 . 95 v  K . Ta sẽ chứng minh đồ thị G có chu trình Hamilton bằng quy nạp theo I = m . Với m = 1 , giả sử I = u , K = v1 , v2 ,..., vn  . Vì N ( I )  I và deg(u)  2 nên ta có deg(u) = 2 . Không mất tính tổng quát ta có thể giả sử N (u) = v1 , v2  . Khi đó v1uv2v3 ...vn v1 là chu trình Hamilton của đồ thị G . Giả sử m  2 và khẳng định đã được chứng minh cho những đồ thị tách cực có I  m . Bổ đề 2. Giả sử G = S (I  K , E) là đồ thị tách cực với I = K = n và G* = B( I  K , E * ) là đồ thị 2 phần thu Giả sử G = S (I  K , E) là đồ thị tách cực thỏa mãn | I |= m | K |= n , N ( I ' )  I ' với mọi   I '  I và được từ đồ thị G bằng cách xóa đi tất cả các cạnh có cả hai đỉnh đầu mút đều thuộc K . Khi đó, G có chu trình Hamilton khi và chỉ khi G * có chu trình Hamilton. N I (v)  2 với mọi v  K . Theo giả thiết quy nạp, với mỗi u  I , đồ thị G − u có chu trình Hamilton. Chứng minh: Giả sử đồ thị G có chu trình Hamilton C và u1 , u2 ,..., un là các đỉnh của I , lần lượt xuất hiện trên v  N (I ) sao cho N I (v) = 1, bởi vì trong trường hợp + + + C . Vì K = n , các đỉnh u1 , u2 ,..., un đều thuộc tập K và Vì deg(u)  2 với mọi u  I và N ( I )  I nên tồn tại ngược lại ta sẽ có: 2 I   N (u ) = đôi một phân biệt nên K = {u1+ , u2+ ,..., un+ } . Khi đó chu trình + C có dạng C = u1u1+u2u2+ ...unu1 (chú ý rằng un = u1 ). Do đó, C chính là chu trình Hamilton của đồ thị G * . Giả sử G * có chu trình Hamilton C* . Vì G * là đồ thị 2 phần nên C* phải có dạng C * = u1v1u2 v2 ...un vnu1 , trong đó I = u1 , u2 ,..., un  , K = v1 , v2 ,..., vn  . Rõ ràng C* cũng là chu trình Hamilton của đồ thị G . 2.2. Kết quả chính Trong mục này chúng ta sẽ phát biểu và chứng minh các định lý dưới đây. Định lý 3. Giả sử G = S (I  K , E) là đồ thị tách cực với I  K và deg(u)  2 với mọi u  I . Khi đó G có chu trình Hamilton khi và chỉ khi N (I ' )  I ' với mọi Chứng minh: Giả sử đồ thị G = S (I  K , E) có chu trình Hamilton C . Theo Bổ đề 1 ta luôn có N ( I ' )  I ' với mọi   I '  I . Ta chỉ còn phải chứng minh N I (v)  2 với mọi v  K . Với m = 1 hoặc m = 2 , khẳng định là hiển nhiên. Do vậy, ta có thể giả sử m  3 . Giả sử tồn tại v  K sao cho N I (v)  3 và N I (v) = u1 , u2 ,..., ut  , t  3 . Vì nên tồn tại j 1, 2,..., t sao cho + − u j  v + , v −  , ở đây v , v tương ứng là các đỉnh đứng ngay sau và đứng ngay trước đỉnh v trên chu trình C . Do đó, N ( u j )  u +j , u −j , v , vì vậy N ( u j )  3 . Điều này mâu   thuẫn với giả thiết. Ngược lại, giả sử đồ thị G = S (I  K , E) thỏa mãn N ( I ' )  I ' với mọi   I '  I và NI (v)  2 với mọi  vN ( I ) NI (v ) = 2 N ( I ) . Điều này mâu thuẫn với giả thiết N ( I )  I . Giả sử N I (v) = u1 , N ( u1 ) = v, v1 . Ký hiệu G1 là đồ thị G − u1 . Khi đó đồ thị G1 = S ( I1  K1 , E1 ) là đồ thị tách cực với I1 = I − u1 , K1 = K . Theo giả thiết quy nạp, đồ thị G1 có chu trình Hamilton C1 . Nếu v + = v1 thì C = vu1v1 C1v là chu trình Hamilton của đồ thị G . Bây giờ ta xét trường v +  v1 . hợp Vì NI (v) = u1 , N I ( v1 )  2 và − − + v1  N ( u1 ) , nên cả v và v1 đều thuộc K hoặc cả v + và v1 đều thuộc K . Nếu cả v − và v1− đều thuộc K thì C = vu1v1 C1v −v1− C1v là chu trình Hamilton của đồ thị G . Nếu cả   I '  I và N I (v)  2 với mọi v  K . N I (v)  3 uI v + và v1+ đều thuộc K thì C = vu1v1C1v+v1+ C1v là chu trình Hamilton của đồ thị G . Định lý 4. Giả sử G = S (I  K , E) là đồ thị tách cực với I = K = n  2 và deg(u)  2 với mọi u  I . Khi đó G có chu trình Hamilton khi và chỉ khi N ( I ' )  I ' với mọi   I '  I thỏa mãn | I ' | n − 1 và N I (v) = 2 với mọi vK . Chứng minh: Giả sử đồ thị G = S (I  K , E) có chu trình Hamilton C . Theo Bổ đề 1 ta luôn có N ( I ' )  I ' với mọi   I '  I thỏa mãn | I ' | n − 1 . Do đó deg(u)  2 với mọi uI . Kết hợp với giả thiết ta suy ra và deg(u) = 2 với mọi u  I . Tiếp theo ta sẽ chứng minh N I (v) = 2 với mọi v  K . Với n = 2 , khẳng định là hiển nhiên. Do vậy ta có thể giả sử n  3 . Ta xét hai trường hợp. 96 Lê Xuân Hùng Trường hợp 1: Tồn tại v  K sao cho N I (v)  3 . Đặt N I (v) = u1 , u2 ,..., ut  , t  3 . Vì N I (v)  3 nên   tồn tại j 1, 2,..., t sao cho u j  v + , v − , ở đây v + , v − tương ứng là các đỉnh đứng ngay sau và đứng ngay trước đỉnh v trên chu trình C . Do đó, N u j  u +j , u −j , v , vì ( )   vậy N ( u j )  3 . Điều này mâu thuẫn với giả thiết. Trường hợp 2: Tồn tại v  K sao cho N I (v)  1 . Khi đó sẽ tồn tại v1  K sao cho N I (v1 )  3 , bởi vì nếu điều này không đúng ta sẽ có 2 I =  N (u ) =  NI ( v )  2 K , uI vK G1 = S ( I  K , E1 ) với tập đỉnh và tập cạnh như sau: I = V1 , K = V2 , E1 = E  uv | u V2 , v V2 , u  v . Giả sử đồ thị G có chu trình Hamilton C . Khi đó các đỉnh của V1 và V2 xuất hiện luân phiên trên C , do đó m = n . Theo Bổ đề 2, đồ thị tách cực G1 = S ( I  K , E1 ) cũng có chu trình Hamilton. Theo Định lý 4 ta có N (S )  S với mọi   S  V1 thỏa mãn S  n − 1 và N (v) = 2 với mọi v  V2 . Bây giờ ta giả sử m = n , N (S )  S với mọi   S  V1 thỏa mãn S  n −1 và N (v) = 2 với mọi điều này trái với giả thiết I = K . Lập luận tương tự như v  V2 . Từ đó suy ra trong đồ thị tách cực Trường hợp 1 ta suy ra điều mâu thuẫn. Từ hai trường hợp trên ta suy ra N I (v) = 2 với mọi v  K . G1 = S ( I  K , E1 ) ta có N (S )  S với mọi   S  I Bây giờ ta chứng minh điều kiện đủ. Giả sử đồ thị G = S (I  K , E) thỏa mãn N ( I ' )  I ' với mọi   I '  I sao cho | I ' | n − 1 và N I (v) = 2 với mọi v  K . Giả sử u là một đỉnh bất kỳ thuộc I và N (u) = v1 , v2  . Đặt Gu = G − u . Khi đó Gu là đồ thị tách cực S ( Iu  K , Eu ) , trong đó Iu = I − u . Dễ thấy đồ thị tách cực Gu thỏa mãn Iu = n − 1  K , deg(u)  2 với mọi u  I , N ( I u' )  I u' với mọi   I u'  I u và N Iu (v)  2 với mọi v  K . Theo Định lý 3, đồ thị Gu có chu trình Hamilton Cu . Giả sử u1 , u2 ,..., un −1 là các đỉnh của I u , lần lượt xuất hiện trên Cu . Vì Iu = n − 1  K và các đỉnh của I u không thể kề với nhau nên trong số các đường u1 Cu u2 , u2 Cu u3 ,…, un−1 Cu u1 , có đúng một đường chứa hai đỉnh của K , mỗi đường còn lại chứa đúng một đỉnh của K . Không mất tính tổng quát ta có thể giả sử đường u1 Cu u2 chứa hai đỉnh của K . Mặt khác, trong đồ thị Gu ta có N Iu (v1 ) = N Iu ( v2 ) = 1 , do đó v1 , v2 chắc chắn là hai đỉnh của K thuộc đường u1 Cu u2 (ta có thể giả sử v1 , v2 nằm thỏa mãn S  n − 1 và N I (v) = 2 với mọi v  K , theo Định lý 4 thì đồ thị G1 có chu trình Hamilton. Theo Bổ đề 2 ta suy ra đồ thị 2 phần G = B(V1  V2 , E ) có chu trình Hamilton. 3. Kết luận Vấn đề tìm điều kiện để một đồ thị nói chung, đồ thị tách cực nói riêng có chu trình Hamilton luôn là vấn đề thời sự của toán học, được nhiều nhà toán học quan tâm nghiên cứu. Đối với lớp đồ thị tách cực, vấn đề này được nghiên cứu từ năm 1980 bởi Burkard và Hammer. Đặc biệt, trong thời gian gần đây, một số tác giả đã tìm ra một số điều kiện cần và đủ cho một số lớp đồ thị tách cực có chu trình Hamilton (đặc điểm chung của các lớp đồ thị tách cực được xem xét trong các kết quả này là đồ thị có bậc cực tiểu khá lớn). Trong lần tiếp cận này, tác giả xem xét lớp đồ thị tách cực ở một khía cạnh khác (bậc của các đỉnh thuộc tập độc lập là tương đối nhỏ), kết quả chính trong bài báo này là các định lý 3 và 4. Ngoài ra còn suy ra một kết quả cho đồ thị 2 phần được phát biểu trong Hệ quả 5. Những kết quả đạt được trong bài báo này góp phần làm phong phú thêm cho việc nghiên cứu sự tồn tại chu trình Hamilton trong đồ thị tách cực mà cho đến nay vẫn chưa giải quyết được triệt để. trên đường u1 Cu u2 theo thứ tự của chỉ số). Khi đó chu trình TÀI LIỆU THAM KHẢO C = u1v1uv2u2 Cuu1 là chu trình Hamilton của đồ thị G . [1] M. Behazad and G. Chartrand, Introduction to the Theory of graphs, Allyn and Bacon, Boston, 1971. [2] R. E. Burkard and P. L. Hammer, “A note on Hamiltonian split graphs”. J. Combin. Theory, Vol. 28, 1980, pp. 245-248. [3] V. Chvatal and P. L. Hammer, “Aggregation of inequalities in integer programming”, Ann. Discrete Math, 1, 1977, pp. 145-162. [4] S. Foldes and P. L. Hammer, Split graphs, in Proceeding of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State University, Baton Rouge, LA, 1977), Congressus Numerantium, vol. XIX, Utilitas Mathematics, Winnipeg, Man., 1977, pp. 311-315. [5] S. Foldes and P. L. Hammer, On a class of matroid-producing Hệ quả 5. Giả sử G = B(V1  V2 , E ) là đồ thị hai phần với các phần là V1 và V2 , deg(u)  2 với mọi u  I và m = V1  V2 = n . Khi đó G có chu trình Hamilton khi và chỉ khi m = n , N (S )  S với mọi   S  V1 thỏa mãn S  n − 1 và N (v) = 2 với mọi v  V2 . Chứng minh. Ta xây dựng đồ thị tách cực ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 3(124).2018 graphs, Combinatorics (Proceeding of the Filth Hungarian Colloquium, Kesrthely, 1976), Vol. 1, Colloquium Mathematical Society, Jano’s Bolyai, Vol. 18, North-Holland, Amsterdam, New York, 1978, pp. 331-352. [6] Lê Xuân Hùng, “Về chu trình Hamilton trong đồ thị tách cực”, Tạp chí Khoa học và Công nghệ Đại học Đà Nẵng, Số 7(80), 2014, trang 112–115. [7] D. Kratsch, J. Lehel, H. Muller, “Toughness, hamiltonicity and split graphs”, Discrete Math, Vol. 150, 1996, pp. 231-245. [8] J. Peemoller, “Necessary conditions for Hamiltonian split graphs”, 97 Discrete Math, Vol. 54, 1985, pp. 39-47. [9] U. N. Peled, Regular Boolean function and their polytope, Ph.D. Thesis, Department of Combinatorics and Optimization, University of Waterloo, Chapter VI, 1975. [10] Ngo Dac Tan, Le Xuan Hung, “Hamilton cycles in split graphs with large minimum degree”, Discussiones Math. Graph Theory, 24, 2004, pp. 23-40. [11] Ngo Dac Tan, Le Xuan Hung, “On the Burkard-Hammer codition for hamiltonian split graphs”, Discrete Math, 296, 2005, pp. 59-72. (BBT nhận bài: 04/01/2018, hoàn tất thủ tục phản biện: 12/02/2018)