圖的控制參數(shù)的若干問題.pdf

1、大連理工大學(xué)碩士學(xué)位論文圖的控制參數(shù)的若干問題姓名：麻娜申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：計(jì)算數(shù)學(xué)指導(dǎo)教師：于洪全2001.6.1大 連理工大學(xué)碩士學(xué)位論文 Ab s t r a c tAb s t r a c tA d o m i n a t i n g s e t D o f a g r a p h G i s d e f i n e d a s a s u b s e t o f v e r t i c e s

2、 i nG s u c h t h a t e a c h v e r t e x n o t i n D i s a d j a c e n t t o a t l e a s t o n e v e r t e x o f D .T h e p r o b l e m o f d e t e r m i n i n g t h e d o m i n a t i n g s e t s

3、h a s m a n y a p p l i c a t i o n st o t h e l o c a t i o n o f o b j e c t s , s a f e g u a r d s o r f a c i l i t i e s o n t h e v e r t i c e s o f an e t w o r k . D u r i n g t h e p a s t 3

4、0 y e a r s t h e s t u d y o f d o m i n a t i o n p a r a m e t e r so f a g r a p h h a s b e c o m e a s i g n i f i c a n t a r e a o f r e s e a r c h i n g r a p h t h e o r y .T o d a t e , t

5、h e r e a r e m o r e t h a n o n e t h o u s a n d p a p e r s w r i t e n o nd o m i n a t i o n p r o b l e m s a n d n e a r l y 1 0 0 d i f e r e n t t y p e s o f d o m i n a t i o nr e l a t e d p

6、 a r a m e t e r s h a v e b e e n s t u d i e d .I n t h i s p a p e r w e g e n e r a l i z e s o m e b a s i c t y p e s o f d o m i n a t i o n . F i r s t l yw e i n t r o d u c e t h e c o n c e p t

7、 s o f k - d o m i n a t i o n , k - i n d e p e n d e n c ed o m i n a t i o n a n d k - i r r e d u n d a n c e a n d t h e i r s o m e a p p l i c a t i o n s t o t h e r e a lw o r d a n d w e a l s o

8、g i v e s o m e r e l a t i o n s o f t h e s e d o m i n a t i o n p a r a m e t e r s .S e c o n d l y w e i n t r o d u c e t h e t o t a l k - d o m i n a t i o n a n d c o n n e c t e d k -d o mi n a t

9、 i o n a n d d i s c u s s t h e r e l a t i o n s b e t w e e n t h e t w o d o mi n a t i o np a r a m e t e r s a n d s o m e o t h e r p a r a m e t e r s o f g r a p h s a n d g i v e s o m e n e w

10、r e s u l t s . F i n a l l y w e i n t r o d u c e t h e m u l t i p l e d o m i n a t i o n , k - t u p l ed o m i n a t i o n a n d k - s t e p d o m i n a t i o n a n d g i v e t h e p r o p e r t i e s