【摘要】：設(shè)G =(V,E)是一個(gè)圖,其中K = K(G)是圖的點(diǎn)集,,E=E(G)是邊集.G□H是圖G和H的笛卡爾乘積.稱D(?)V(G)是圖G的一個(gè)控制集,若V(G)\D中每個(gè)點(diǎn)都與D中至少一點(diǎn)相鄰.圖G的最小控制集中點(diǎn)的個(gè)數(shù)稱為控制數(shù),記作γ(G).一個(gè)函數(shù)f:V(G)→ {0,1,2}是一個(gè)羅馬控制函數(shù)(RDF),若每個(gè)賦值為0的點(diǎn)與至少一個(gè)賦值為2的點(diǎn)相鄰.一個(gè)羅馬函數(shù)f的權(quán)重定義為f(V(G))=∑u∈V G f(u).圖G的羅馬控制數(shù)γR(G)是圖G所有羅馬函數(shù)權(quán)重的最小值.設(shè)kk是一個(gè)正整數(shù),稱D D(?)V(G)是圖G的一個(gè)距離kk-控制集,若不在D中的點(diǎn)都與D中至少一點(diǎn)的距離不超過(guò)k.圖G最小距離kk-控制集中點(diǎn)的個(gè)數(shù)就是距離k-控制數(shù),記為γk(G).拓?fù)渲笖?shù)是圖論中不可忽視的研究?jī)?nèi)容,它是可以用來(lái)描述有機(jī)化合物的物理化學(xué)特性的數(shù)學(xué)參數(shù).第一(M1)和第二(M2)Zagreb指數(shù)是源于共軛分子總π-電子能量研究的點(diǎn)度定義拓?fù)渲笖?shù),定義為M1=∑u∈V(G)d2(u)和M2=∑uv∈E(G)d(u)d(v).離心距離和是利用點(diǎn)離心率定義的一個(gè)拓?fù)渲笖?shù):ξd(G)=∑v∈V(G)-G(v)DG()其中點(diǎn)v在圖G中的離心率εG(v)是指v到G中其它點(diǎn)的最大距離,且DG(v)是v到圖G中其它點(diǎn)的距離之和.Harary指數(shù)是利用兩點(diǎn)距離定義的一個(gè)拓?fù)渲笖?shù):H(G)=1/2∑u∈V(G)∑v∈V(G)1/d(u.v),其中d(u,u)表示的是G中點(diǎn)u和v的距離.本文主要研究了關(guān)于控制數(shù)的Vizing猜想,以及(距離k-)控制數(shù)與上段中提到的拓?fù)渲笖?shù)之間的關(guān)系.第一章介紹了圖論術(shù)語(yǔ)和符號(hào)以及本文研究?jī)?nèi)容的圖論背景.Vizing猜想是由Vizing在1963年提出的關(guān)于控制數(shù)的一個(gè)著名猜想,即對(duì)任意圖G和H都有γ(G□H)≥ γ(G)γ(H)成立.與Vizing猜想相關(guān)的不等式很少涉及羅馬控制數(shù),其中之一是由 Wu[Y.J.Wu,An improvement on Vizing's conjecture,Inform.Process.Lett.113(2013)87-88]得到的.本文第二章證明了 γR(G□H)≥γ(G)γ(H)+ 1/2min{γ(G),7(H)}在圖G或者圖H不是空?qǐng)D時(shí)成立.這一結(jié)果不僅改進(jìn)了由Wu得到的結(jié)果,并且在某些條件下優(yōu)于其他類似已有結(jié)果.AutoGraphiX(AGX)計(jì)算機(jī)系統(tǒng)是利用變鄰域搜索方法和數(shù)據(jù)分析方法尋找圖論猜想的一個(gè)軟件.這些猜想主要確定圖論中兩變量的四則運(yùn)算的界,同時(shí)刻畫(huà)達(dá)到上下界的極值圖.本文第三章我們改正了一個(gè)關(guān)于控制數(shù)和平均離心率的Auto-GraphiX猜想,并給出了修改后的猜想的證明.另外得到了 n階樹(shù)T的γ(T)-ecc(T)的緊上界.Borovicanin[B.Borovicanin,B.Furtula,On extremal Zagreb indices of trees with given domination number,Appl.Math.Comput.276(2016)208-218]確定了給定控制數(shù)的樹(shù)的Zagreb指數(shù)的上界.在這一結(jié)果的啟發(fā)下,本文第四章用距離kk-控制數(shù)給出了 n階樹(shù)的Zagreb指數(shù)的上界,并且刻畫(huà)了相應(yīng)的極值樹(shù).同時(shí)得到了一個(gè)用n,k,△表示的樹(shù)的距離k-控制數(shù)的上界.最后利用已有的Harary指數(shù)與Zagreb指數(shù)的關(guān)系得到了給定距離kk-控制數(shù)的樹(shù)的Harary指數(shù)的上界,并刻畫(huà)了相應(yīng)的極值圖.本文第五章確定了給定距離k-控制數(shù)的n階樹(shù)中具有最小離心距離和的樹(shù),并且得到了若干離心距離和的緊界.
【學(xué)位授予單位】：安徽大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2018
【分類號(hào)】：O157.5
【圖文】：

，Ｇ和ｉ？■的笛卡爾乘積圖（Ｃａｒｔｅｓｉａｎ邋ｐｒｏｄｕｃｔ邋ｇｒａｐｈ）邋Ｇ口丑丨ｕ邋ｅ邋Ｖ（Ｇ），邋Ｖ邋ｅ邐且兩個(gè)點(diǎn)ｈｕ＇）與0；，？／）相鄰邋邐或者ｕ＇邋＝邋？／且邋Ｖ（Ｇ）．對(duì)于文中出現(xiàn)的未定義的§１．２邐研究問(wèn)題的背景逡逑所有研宄都圍繞著控制數(shù)問(wèn)題展開(kāi)，與圖論的起源類似，圖戲：國(guó)際象棋游戲．國(guó)際象棋發(fā)源地在印度，圖１．２．１呈現(xiàn)的際象棋的游戲規(guī)則，皇后可以在棋盤(pán)上橫向，縱向，對(duì)角線上空格位置（假設(shè)這些方向上的空格上沒(méi)有其他的棋子）？所以攻擊（或者控制）標(biāo)號(hào)為“ｘ”的空格位置．１９世紀(jì)５０年代，考慮如下一＂ｔ＂有趣的問(wèn)題，棋盤(pán)上最少要放置多少個(gè)皇后可皇后占據(jù)，或被皇后攻擊（或控制）？圖１．２．１中放置的六個(gè)皇，隨后被證實(shí)最少需要放五個(gè)皇后．這就是歷史上著名的五個(gè)Ｘ邐１邋ＩＸ—

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李寧;范英梅;;兩類乘積圖的符號(hào)控制數(shù)[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年06期

2 尚華輝;苗連英;;全控制數(shù)與連通控制數(shù)相等的圖[J];江蘇師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2018年01期

3 徐保根;李春華;范自柱;;關(guān)于圖的符號(hào)星控制數(shù)[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2016年21期

4 李文升;黃中升;馮志芳;吳丹丹;;圖的2符號(hào)全控制數(shù)[J];江蘇師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2017年02期

5 敖國(guó)艷;紅霞;張桂芝;吉日木圖;;圖的逆符號(hào)邊全控制數(shù)[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2017年16期

6 丁超;;關(guān)于圖的嚴(yán)格強(qiáng)控制數(shù)的界[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2016年02期

7 周穎;葉淼林;;圖的符號(hào)控制數(shù)的一些上、下界[J];安慶師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2016年02期

8 莊蔚;吳曉霞;;外平面圖的全控制數(shù)[J];閩南師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年02期

9 莊蔚;楊衛(wèi)華;;外平面圖的匹配控制數(shù)（英文）[J];新疆大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年03期

10 尚華輝;謝鳳艷;;關(guān)于圖的兩類符號(hào)全控制數(shù)[J];四川文理學(xué)院學(xué)報(bào);2016年05期

相關(guān)重要報(bào)紙文章 前10條

1 粟時(shí)勇 記者　黃先明;“人員控制數(shù)”破終身制[N];四川日?qǐng)?bào);2006年

2 科訊;引進(jìn)院士不計(jì)入結(jié)構(gòu)比例控制數(shù)[N];廣東科技報(bào);2005年

3 李永桃 史生榮 高潔;自治區(qū)財(cái)政激勵(lì)性轉(zhuǎn)移支付預(yù)算控制數(shù)全部下達(dá)到盟市[N];內(nèi)蒙古日?qǐng)?bào)(漢);2006年

4 記者 龍立瓊 鄭滔;下半年連續(xù)三月未完成案件控制數(shù)的，嚴(yán)格問(wèn)責(zé)![N];法制生活報(bào);2011年

5 記者 周韌　通訊員 張偉 實(shí)習(xí)生 吳文青 王海藍(lán);安全生產(chǎn)步入全國(guó)先進(jìn)[N];長(zhǎng)江日?qǐng)?bào);2007年

6 付程君 劉慧梅 楊光欽 姜桃瑞;云南高速公路交通事故四項(xiàng)控制數(shù)全面下降[N];云南經(jīng)濟(jì)日?qǐng)?bào);2007年

7 徐侃;克服松懈情緒 防范事故發(fā)生[N];安慶日?qǐng)?bào);2008年

8 記者 宋蘭蘭;我市首次曬“三公”經(jīng)費(fèi)[N];長(zhǎng)江日?qǐng)?bào);2011年

9 徐侃;把安全生產(chǎn)工作抓實(shí)抓細(xì)[N];安慶日?qǐng)?bào);2009年

10 記者 許淵;我市安全生產(chǎn)工作接受省考核[N];臺(tái)州日?qǐng)?bào);2012年

相關(guān)博士學(xué)位論文 前10條

1 裴利丹;控制數(shù)與拓?fù)渲笖?shù)的研究[D];安徽大學(xué);2018年

2 單而芳;圖的控制數(shù)及其相關(guān)參數(shù)[D];上海大學(xué);2005年

3 呂長(zhǎng)虹;[D];南京大學(xué);2000年

4 趙敏;幾類圖的控制參數(shù)的理論與算法[D];上海大學(xué);2006年

5 王侃;圖的鄰域全控制數(shù)研究[D];華東師范大學(xué);2016年

6 蔣紅星;圖的幾類控制參數(shù)研究[D];上海大學(xué);2009年

7 趙衍才;圖的某些控制參數(shù)的計(jì)算[D];上海大學(xué);2011年

8 王超;圖的配對(duì)控制數(shù)和彩虹控制數(shù)研究[D];華東師范大學(xué);2015年

9 寧文杰;關(guān)于圖的若干參數(shù)的研究[D];清華大學(xué);2015年

10 曹永昌;圖的穩(wěn)定性的相關(guān)研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2009年

相關(guān)碩士學(xué)位論文 前10條

1 段偉;循環(huán)圖的兩類控制數(shù)研究[D];大連海事大學(xué);2018年

2 張清芳;兩類圖的控制數(shù)研究[D];大連海事大學(xué);2018年

3 鄒妍;關(guān)于圖的邊控制數(shù)[D];華東交通大學(xué);2016年

4 周穎;圖的符號(hào)控制數(shù)[D];安慶師范大學(xué);2016年

5 曹惠萍;若干圖類的全符號(hào)控制數(shù)的研究[D];大連海事大學(xué);2016年

6 連小娟;一些圖的笛卡爾乘積的全控制數(shù)和成對(duì)控制數(shù)[D];安徽大學(xué);2014年

7 沈玄玄;圖的符號(hào)圈控制數(shù)的幾個(gè)問(wèn)題研究[D];華東師范大學(xué);2014年

8 陳悅;圖的幾類K控制數(shù)[D];華東交通大學(xué);2012年

9 喬麗娜;關(guān)于圖的符號(hào)控制數(shù)的研究[D];華北電力大學(xué);2012年

10 劉曉艷;平面圖的誘導(dǎo)圈符號(hào)控制數(shù)問(wèn)題[D];華東師范大學(xué);2010年

本文編號(hào)：2797525