BË GIO DÖC V O TO
I HÅC BCH KHOA H NËI
PHM Mß HNH
A THÙC ËC LP CÕA Ç THÀ
V MËT SÈ VN  LIN QUAN
Ngnh: To¡n håc
M¢ sè: 9460101
TÂM TT LUN N TIN S
H Nëi - 2025
Cæng tr¼nh ÷ñc hon thnh t¤i:
¤i håc B¡ch Khoa H Nëi
NG×ÍI H×ÎNG DN KHOA HÅC
:
1. TS. é Trång Hong
2. TS. on Duy Trung
1. Ph£n bi»n 1:....................
2. Ph£n bi»n 2:...................
3. Ph£n bi»n 3:...................
Luªn ¡n ÷ñc b£o v» tr÷îc Hëi çng ¡nh gi¡ luªn ¡n ti¸n s¾
c§p ¤i håc B¡ch khoa H Nëi håp t¤i ¤i håc B¡ch khoa
H Nëi.
Vo hçi . . . . . . .. gií, ngy .. . .. th¡ng . . . .. n«m . . . . . . . . .
Câ thº t¼m hiºu luªn ¡n t¤i
:
1. Th÷ vi»n T¤ Quang Bûu - ¤i håc B¡ch khoa H Nëi
2. Th÷ vi»n Quèc gia Vi»t Nam
MỞ ĐẦU
Lý thuyết đồ thị hiện nay là lĩnh vực phát triển rất mạnh và
có mối tương quan chặt chẽ, giao thoa với nhiều nhánh Toán học
như Đại số, Giải tích, Hình học và một số ngành khoa học, kỹ
thuật khác. Trong các bài toán liên quan đến lý thuyết đồ thị,
bài toán xác định tập độc lập có lực lượng lớn nhất của một đồ
thị Gtùy ý đã được chứng minh thuộc lớp các bài toán NP-khó
([47]). Năm 1983, Gutman và Harary ([29]) nêu định nghĩa đa
thức độc lập của đồ thị, cụ thể với đồ thị Gcho trước
I(G;x) =
α(G)
X
k=0
skxk=s0+s1x+· · · +sα(G)xα(G),
trong đó sklà số tập độc lập có lực lượng là kvà α(G)là lực
lượng của tập độc lập lớn nhất trong đồ thị G. Vì thế, bài toán
xác định đa thức độc lập của một đồ thị tùy ý cũng thuộc lớp
các bài toán NP-khó. Lưu ý rằng đa thức độc lập có mối liên hệ
mật thiết với các đa thức khác của đồ thị. Cụ thể, I(G;x)có thể
được xem là đa thức clique của đồ thị phần bù G([44]). Ngoài
ra, I(G;x)là đa thức ghép cặp của đồ thị đường L(G)sinh bởi
G([55]). Vì thế, chủ đề đa thức độc lập đã thu hút nhiều sự quan
tâm của các nhà toán học (xem trong [1, 12, 13, 14, 19, 20, 44,
62]) với mục tiêu đưa ra câu trả lời cho bài toán sau:
Bài toán nghiên cứu 1. Đặc trưng tính chỉ có nghiệm thực, lõm-
log và yếu vị của đa thức độc lập của lớp đồ thị G.
Một số công trình nghiên cứu đã được công bố góp phần giải
quyết bài toán trên như sau: tính yếu vị ([15, 34, 49, 51, 55, 56,
1
59, 62]); tính lõm-log ([79, 80]); và tập nghiệm của đa thức độc
lập ([12, 13, 20, 52]).
Đa thức độc lập I(G;x) =
α(G)
P
k=0
skxkđược gọi là thỏa tính yếu
vị nếu tồn tại chỉ số kvới 0≤k≤α(G)sao cho
s0≤ · · · ≤ sk≥ · · · ≥ sα(G).
Năm 1987, Alavi, Malde, Schwenk và Erd¨os ([1]) chứng tỏ rằng
với mỗi hoán vị πcủa tập hợp {1,2, ..., α}, tồn tại đồ thị Gthỏa
tính chất α(G) = αvà sπ(1) < sπ(2) < ... < sπ(α). Đồng thời, các
tác giả cũng đưa ra giả thuyết sau:
Giả thuyết 1. Đa thức độc lập của đồ thị cây thỏa tính yếu vị.
Lưu ý rằng Giả thuyết này đến nay vẫn chưa được chứng
minh hoàn toàn hay bác bỏ. Từ đó, các nhà toán học quan tâm
nhiều hơn vấn đề xác định tính yếu vị của đa thức độc lập của
các lớp đồ thị, trong đó có lớp đồ thị phủ tốt. Michael và Traves
([62]) đã nêu ra các đồ thị phủ tốt mà đa thức độc lập của chúng
không thỏa tính yếu vị. Đồ thị Gđược gọi là phủ tốt nếu tất cả
các tập độc lập cực đại của nó đều có cùng lực lượng ([65]). Để
phân lớp các đồ thị phủ tốt, Staples ([73]) định nghĩa lớp đồ thị
Wpvới p≥1như sau: Đồ thị phủ tốt Gcó số đỉnh lớn hơn hay
bằng pthuộc vào lớp Wpnếu với mỗi ptập độc lập rời nhau trong
Gđều thuộc vào ptập độc lập có lực lượng lớn nhất đôi một rời
nhau. Hiển nhiên W1chính là lớp đồ thị phủ tốt. Ngoài ra, năm
1993, Finbow, Hartnell và Nowakowski ([25]) chứng tỏ rằng với
đồ thị Gliên thông có độ vòng girth(G)≥6và G /∈ {C7, K1},
khi đó Glà phủ tốt nếu và chỉ nếu G=H◦K1với đồ thị Hnào
đó, hay Gcó dạng của đồ thị clique corona. Vì thế, chúng tôi xác
định mục tiêu nghiên cứu phục vụ cho Bài toán 1của luận án
như sau:
Mục tiêu 1. Nghiên cứu tính yếu vị của đa thức độc lập của đồ
thị thuộc lớp con của lớp đồ thị phủ tốt.
2
Nội dung này được trình bày trong Chương 2của luận án. Cụ
thể, đối với đồ thị phủ tốt chúng tôi tìm hiểu tính yếu vị của đa
thức độc lập của đồ thị thuộc lớp Wpvới p≥1và ứng dụng cho
trường hợp đồ thị clique corona. Ngoài ra, lưu ý rằng nếu Glà
đồ thị cây thì đồ thị corona G◦2K1cũng là đồ thị cây. Một kết
quả của Mandrescu ([61]) đã chứng tỏ rằng I(G◦2K1;x)thỏa
tính yếu vị. Vì thế, chúng tôi xác định mục tiêu thứ hai phục vụ
cho Bài toán 1của luận án như sau:
Mục tiêu 2. Nghiên cứu tính yếu vị của đa thức độc lập của đồ
thị G◦(Kp⊔Kq)với pvà qlà các số nguyên dương.
Nội dung này được trình bày trong phần tiếp theo của Chương
2. Lưu ý rằng đồ thị corona G◦(Kp⊔Kq)không là đồ thị phủ tốt.
Chúng tôi xác định điều kiện của pvà qđể I(G◦(Kp⊔Kq); x)
thỏa tính yếu vị, đồng thời tìm hiểu chiều tăng và chiều giảm của
dãy hệ số của đa thức độc lập, từ đó tính yếu vị của I(G◦2K1;x)
([61]) là một hệ quả trực tiếp. Hơn nữa, Giả thuyết 1có thể được
phát biểu lại một cách tương đương như sau:
Giả thuyết 2. Cho Tlà đồ thị cây và T′là một cây con của T.
Nếu I(T;x)thỏa tính yếu vị, thì I(T′;x)cũng thỏa tính yếu vị.
Bên cạnh đó, với đồ thị đơn, vô hướng và hữu hạn G, ta kí
hiệu n(G) = n∈N∗. Cho klà trường tùy ý, R=k[x1, . . . , xn]
là một vành đa thức nẩn trên k. Ta có thể thiết lập tương ứng
một-một giữa đồ thị Gvới một iđêan đơn thức bậc hai không
chứa bình phương. Iđêan này được gọi là iđêan cạnh I(G)của đồ
thị G([77]) như sau:
I(G)=(xixj|xixj∈E(G)) ⊆R.
Bài toán sau được nhiều nhà toán học quan tâm trong lĩnh vực
đại số giao hoán tổ hợp ([23, 32, 33, 36, 38, 43, 70, 71]).
Bài toán nghiên cứu 2. Đặc trưng tính chất Cohen–Macaulay,
Gorenstein của iđêan cạnh của một lớp đồ thị và nghiên cứu các
3