亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        K3,4,p的點可區(qū)別一般全染色

        2020-12-28 12:47:06楊佳睿陳祥恩
        關(guān)鍵詞:分配

        楊佳睿, 陳祥恩

        (西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 甘肅 蘭州 730070)

        0 引 言

        圖的(鄰)點可區(qū)別正常邊染色、(鄰)點可區(qū)別全染色及其相關(guān)猜想是受到當前國際著名圖論專家(如Bollobás等)重視的研究課題.1985年,Harary等[1]建設(shè)性地提出點可區(qū)別一般邊染色概念.1988年,Chartrand等[2]研究圖的非正規(guī)強度,即圖的可允許一般邊染色所需要顏色的最少數(shù)目;1997年Burris等[3]及1996年Hork等[4-6]分別獨立地提出圖的點可區(qū)別正常邊染色.Zagaglia[7]首次提出了點可區(qū)別的一般全染色概念.此后, 圖的可區(qū)別染色成為運籌方向的熱門領(lǐng)域,越來越多的學(xué)者投身其中,產(chǎn)出了許許多多相關(guān)成果.陳祥恩等[8-12]開辟了點可區(qū)別染色新方向,研究出許多新成果.點可區(qū)別的一般全染色是指滿足(鄰)點可區(qū)別及一般這兩個概念的色集合對圖的每個頂點的分配,其中,點可區(qū)別是指不同的點所分配的色集合均不相同,鄰點可區(qū)別則是指相鄰的點不能分配到相同的色集合.一般全染色是與正常全染色相對應(yīng)的概念.正常全染色需滿足三個條件,即相鄰的點不能染相同的顏色(V-條件),相鄰的邊不能染相同的顏色(E-條件),以及關(guān)聯(lián)的點與邊不能染相同的顏色(I-條件).而一般全染色則不需要滿足上述三個條件,在缺乏限制條件的情況下,色集合的分配也變得更加靈活和難以把握.事實上,圖的點可區(qū)別的E-全染色(VDETC)、點可區(qū)別的IE-全染色(VDIETC)、點可區(qū)別的I-全染色(VDITC),以及鄰點可區(qū)別的各種未必正常全染色,也是正在研究的課題.本文中出現(xiàn)了兩個概念,gvt(G)定義為G的一般的點可區(qū)別全色數(shù),k-GVDTC定義為圖G的能夠使用k種顏色的點可區(qū)別一般全染色.

        K3,4,p的點可區(qū)別一般全染色已被證明,K3,4,p的一般的點可區(qū)別全色數(shù)已經(jīng)給出.定義V=X∪Y∪Z為完全三部圖Km,n,p的頂點集合, 其中,X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp},邊集合為 {xiyj|i=1,2,…,m;j=1,2,…,n}∪{yjzt|j=1,2,…,n;t=1,2,…,p}∪{xizt|i=1,2,…,m;t=1,2,…,p}.

        1 準備工作

        證明首先利用反證法.假設(shè)K3,4,p有(l-1)-GVDTC.

        反證法, 不妨設(shè)Z中包含{3},{4},…,{l-1}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,l-1}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,l-1}, {1,3,4,…,l-1}, {2,3,4,…,l-1}和 {1,2,3,4,…,l-1}這 4 個集可以分配給X∪Y中的7 個頂點, 顯然矛盾.

        表1與表2給出K3,4,p的一個l-GVDTCf.

        表1 K3,4,p的點染色方案

        表2 K3,4,p的邊染色方案

        因?v∈V(K3,4,p), 均有C(v)=D(v).故得到K3,4,p的l色的點可區(qū)別一般全染色.

        2 主要結(jié)果及其證明

        定理1

        證明按照從一般到特殊分情形討論:

        證明在引理 1、引理 2中已給出證明.

        情形2當 499≤p≤1 006 時,gvt(K3,4,p)=10.

        證明假設(shè)K3,4,p有 9-GVDTC.

        斷言3 當499≤p≤1 006,?v∈X∪Y,|C(v)|≥6.

        斷言4當499≤p≤1 006,Z的色集合中至多含有6個 1-子集.

        反證法, 不妨設(shè)Z中包含{3},{4},…,{9}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,9}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,9}, {1,3,4,…,9}, {2,3,4,…,9}和 {1,2,3,4,…,9}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

        下面闡述K3,4,1 006的 10-GVDTC染色方案,先分配{1,2,3,4,…,10} 的子集給K3,4,p的每個頂點, 令D(x1)={1,2,…,10},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},將除{1},{2},{3},{4},{5},{6}外的 {1,2,…,10}的其余子集作為Z中點的色集合,詳細的邊染色與點染色方案可參照表1與表2所述給出.

        情形3當243≤p≤498 時,gvt(K3,4,p)=9.

        證明:假設(shè)K3,4,p有 8-GVDTC.

        斷言5 當243≤p≤498,K3,4,p的?v∈X∪Y,|C(v)|≥5.

        斷言6 當243≤p≤498,Z的色集合中至多含有5個 1-子集.

        反證法, 不妨設(shè)Z中包含{3},{4},…,{8}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,8}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,8}, {1,3,4,…,8}, {2,3,4,…,8}和 {1,2,3,4,…,8}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

        下面闡述K3,4,498的 9-GVDTC染色方案,先分配{1,2,3,…,9}的子集給K3,4,p的每個頂點, 令D(x1)={1,2,…,9},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},將除{1},{2},{3},{4},{5},{6}外的 {1,2,…,9}的其余子集作為Z中點的色集合,詳細的邊染色與點染色方案可參照表1與表2所述給出.

        情形4當 115≤p≤242 時,gvt(K3,4,p)=8.

        證明假設(shè)K3,4,p有 7-GVDTC.

        斷言7當 115≤p≤242,?v∈X∪Y,|C(v)|≥4.

        斷言8當 115≤p≤242,Z的色集合中至多含有4個 1-子集.

        反證法, 不妨設(shè)Z中包含{3},{4},…,{7}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,7}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,7}, {1,3,4,…,7}, {2,3,4,…,7}和 {1,2,3,4,…,7}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

        K3,4,242的 8-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

        情形5當 51≤p≤114 時,gvt(K3,4,p)=7.

        證明假設(shè)K3,4,p有 6-GVDTC.

        斷言9當 51≤p≤114,?v∈X∪Y,|C(v)|≥3.

        斷言10當 51≤p≤114,Z的色集合至多含有3個 1-子集.

        反證法, 不妨設(shè)Z中包含{3,4,5,6}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,5,6}, 由于點染色滿足可區(qū)別性,則只有{3,4,5,6}, {1,3,4,5,6}, {2,3,4,5,6}和{1,2,3,4,5,6}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

        K3,4,114的 7-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

        情形6當 19≤p≤50 時,gvt(K3,4,p)=6.

        證明假設(shè)K3,4,p有 5-GVDTC.

        斷言11當 19≤p≤50,?v∈X∪Y,|C(v)|≥3.

        斷言12當 19≤p≤50,Z的色集合至多含有2個 1-子集.

        反證法, 不妨設(shè)Z中包含{3,4,5}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,5}, 由于點染色滿足可區(qū)別性, 則只有{3,4,5}, {1,3,4,5}, {2,3,4,5}和{1,2,3,4,5}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

        K3,4,50的 6-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

        情形7當 5≤p≤18 時,gvt(K3,4,p)=5.

        證明假設(shè)K3,4,p有 4-GVDTC.

        斷言13當 5≤p≤18,X的色集合中不含1-子集.

        斷言14當 5≤p≤18,Y的色集合中不含1-子集.

        斷言15當 5≤p≤18,Z的色集合中至多含有1個 1-子集.

        反證法, 不妨設(shè)Z中含有{3},{4},僅不含 {1},{2} 這兩個色集合,即C(xi)∩C(yj)?{3,4}, 由于點染色滿足可區(qū)別性, 則只有{3,4}, {1,3,4}, {2,3,4}和{1,2,3,4}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

        K3,4,18的 5-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

        情形8當p=4 時,gvt(K3,4,p)=4.

        證明假如K3,4,4有 3-GVDTC.使用的 3 種顏色為 1,2,3.那么可分配的色集合有 7 個,無法區(qū)分X∪Y∪Z中的至少 11 個頂點, 矛盾.此時,K3,4,4沒有 3-GVDTC.在表3中給出了K3,4,4的4-GVDTC.

        表3 K3,4,4的全染色方案

        猜你喜歡
        分配
        分配正義:以弱勢群體為棱鏡
        基于可行方向法的水下機器人推力分配
        應(yīng)答器THR和TFFR分配及SIL等級探討
        Crying Foul
        遺產(chǎn)的分配
        一種分配十分不均的財富
        你知道電壓的分配規(guī)律嗎
        績效考核分配的實踐與思考
        收入分配視閾下的共享發(fā)展思考
        浙江績效分配改革觀察
        天堂8中文在线最新版在线| 在线人妻va中文字幕| 一区二区三区中文字幕p站| 国产女人水真多18毛片18精品| 国产精品高潮呻吟av久久无吗| 亚洲综合久久1区2区3区 | 欧美色五月| 中文字幕一区二区三区.| 极品尤物在线精品一区二区三区 | 黄片国产一区二区三区| 把女人弄爽特黄a大片| 老头巨大挺进莹莹的体内免费视频 | 成人无码午夜在线观看| 午夜日韩视频在线观看| 国产日产桃色精品久久久| 人妻无码中文字幕| 在线免费黄网| 无人视频在线播放在线观看免费| 24小时在线免费av| 夜夜揉揉日日人人青青| 免费一区二区三区久久| 日韩av一区在线播放| 人妻少妇中文字幕久久| 欧美最大胆的西西人体44| 亚洲国产成人无码影院| 亚洲av第二区国产精品| 欧美激情视频一区二区三区免费| 公粗挺进了我的密道在线播放贝壳 | 国偷自产一区二区免费视频| 欧美成人专区| 狼人狠狠干首页综合网| 久久无码高潮喷水抽搐| 国产成人综合亚洲精品| 久久久久综合一本久道| 激情五月天在线观看视频| 国产69精品久久久久777| 久久天天躁狠狠躁夜夜爽蜜月| 日本高清不卡一区二区三区| 久久精品国产亚洲av超清| 国产男女猛烈视频在线观看 | 久久精品一区二区三区不卡牛牛|