tailieunhanh - Chu trình Hamilton trong đồ thị ơ2>= N

Given a undirected and simple graph with n vertices, we denote by σ2 the minimum of degree sum of the pair of nonadjacent vertices in G and by σ∗2 the minimum of degree sum of the pair of nonadjacent vertices with distance 2. | T¤p ch½ Tin håc v i·u khiºn håc, , (2012), 153 160 ∗ CHU TR NH HAMILTON TRONG Ç THÀ σ2 ≥ N Ô 0 xr rÁe1 D xq x rÚ x ×Íxq2 1 Khoa Cæng ngh» thæng tin, Tr÷íng ¤i håc S÷ ph¤m H nëi 2 Khoa H» thèng thæng tin kinh t¸, Håc vi»n t i ch½nh Tóm t t. gho tr÷î mët 1ç thà 1ìn væ h÷îng vîi n 1¿nhD t kþ hi»u σ2 l têng ª ² nh§t õ ¡ ∗ °p 1¿nh khæng k· nh u trong G v σ2 l têng ª ² nh§t õ ¡ °p 1¿nh ¡ h nh u kho£ng ¡ h PF f i to¡n HC x¡ 1ành hu tr¼nh r milton @ hu tr¼nh 1i qu t§t £ ¡ 1¿nh trong 1ç thàA v¨n 1÷ñ i¸t l i to¡n N P C F ghóng tæi kh£o s¡t i to¡n HC ho lîp ¡ 1ç thà thä m¢n σ2 ≥ tn ∗ v lîp ¡ 1ç thà thä m¢n σ2 ≥ tnD vîi t l h¬ng sè ho tr÷î F rong i ¡o n y hóng tæi x¥y düng thuªt to¡n vîi thíi gi n 1 thù x¡ 1ành hu tr¼nh r milton khi t ≥ 1 v hùng minh r¬ng i to¡n HC v¨n án l i to¡n N P C trong tr÷íng hñp t < 1F Abstract. qiven undire ted nd simple gr ph with n verti esD we denote y σ2 the minimum of ∗ degree sum of the p ir of non dj ent verti es in G nd y σ2 the minimum of degree sum of the p ir of non dj ent verti es with dist n e PF he pro lem HC to determine the r milton y le @ y le p ssing ll the verti es of the gr phA is wellEknown N P C Epro lemF e onsider the pro lem HC for the l ss of gr phs s tisfying σ2 ≥ tn ∗ nd for the l ss of gr phs s tisfying σ2 ≥ tnD with given onst nt tF sn this p per we give polynomi l lgorithm to estim te r milton y le for the se t ≥ 1 nd prove th t the pro lem HC rem ins N P C pro lem for the se t < 1F 1. MÐ U Trong b i b¡o n y chóng ta sû döng kh¡i ni»m v c¡c kþ hi»u v· ç thà nh÷ trong [3], ri¶ng ç thà ¦y õ vîi n ¿nh th¼ kþ hi»u l Kn . Ta ch¿ kh£o s¡t c¡c ç thà ìn væ h÷îng, li¶n thæng. Mët ç thà ÷ñc gåi l nûa Hamilton n¸u nâ câ mët ÷íng i qua t§t c£ c¡c ¿nh cõa ç thà ( ÷íng Hamilton). T÷ìng tü, ç thà ÷ñc gåi l ç thà Hamilton n¸u nâ câ chu tr¼nh Hamilton (chu tr¼nh chùa t§t c£ c¡c ¿nh cõa ç thà). Cho .