三嵌套圖的邊平衡指數集研究

摘要：本文定義了邊-友好標號、邊-平衡指數集和嵌套圖的概念，運用圖中邊的構造技巧，通研究三嵌套圖 的最大邊平衡指數，得到圖形的全部邊平衡指數。

關鍵字：邊-友好標號；邊-平衡指數集；嵌套圖

圖的標號問題起始于1966年A.Rosa的著名的優美樹猜想。邊的平衡指數集是布爾指數集中的主要研究問題。本文主要研究n圈3嵌套圖的邊平衡指數集的計算公式及其圖形的構造方法。

設一個簡單圖G，其頂點集和邊集分別是 ， .設一個數集 ，給定一個邊標號 ，即 ， =0或1。在圖G中，標號為0或1的邊集記為 ，用 分別來表示此二集合的基數；標號為0或1的頂點集分別記為 ，它們的基數分別記為 。

定義1 設f是一個簡單圖G的邊集 上的一個0、1標號，如果 ，那么就稱f為圖G的邊-友好標號。

定義2 如果一個簡單圖G存在邊-友好標號f，則稱集合 為圖G的邊—平衡指數集，記為EBI（G）。

定義3 由n 條路P連接起m 個 圈的嵌套圖，稱之為圖 。

將圖 的邊平衡指數集， ，中最大的指數，以max 來表示。

對于圖 進行友好標號， 為圖 的總邊數。我們將n分為6類：

； ； ； ； ； ，

來進行討論其邊平衡指數集。

在 中有三個 圈，分別用 ， ， 來表示從外到里三個 圈的頂點，其中 ， 對應相連。

引理1： 若 ，即 時，那么圖 的最大邊平衡指數為 。

證：令與頂點 相接的4條邊為0-邊，與頂點相接的4條邊也為0-邊。令邊 標號為0，其它邊標號為1。

圖中共有5n條邊，即當 時， 。由邊—友好標號的定義，得構造圖中的邊為友好標號。在構造圖中，頂點 ， 標號為0，其它頂點標號為1，則 。又因圖中每個頂點都在 下定義，且圖中共有3n個頂點，那么 。

在圖 中，最外和最內兩個 圈的頂點與之相鄰的邊數為3，而與內圈的頂點相鄰的邊數是4。在此構造圖中，頂點 ， 相鄰的0-邊個數為4，其它頂點僅有一0-邊與之相鄰。故若把構造圖中的任一0-邊和1-邊互換，那么0-點的個數，或不變或增加，而1-點的個數減少，則 的值必減少。

故，在此構造圖中得到的 的值最大，即 。

引理 2：在圖 中，若 ，即 時，則 。

證明：在引理1中構造的 的圖中，交換邊 與 的標號變為1和0，有2條0-邊與頂點 相接。在 的作用下，頂點 由1變為不標號。其它頂點標號不變， 的值減少1，等于 。

（1）交換邊 與 的標號變為0和1，與頂點 相接的0-邊有兩條。在 的作用下，頂點 的標號未變，頂點 由1變為0。 的值又減少2，等于 。

交換邊 與 的標號變為1和0，與頂點 相接的0-邊有2條。在 的作用下，頂點 的標號未變，頂點 變為0。 的值又減少2，等于1。

（2）交換邊 與 的標號變為1和0 ，與頂點 相接的0-邊有3條。在 的作用下，頂點 變為0，其它頂點不變， 的值減少2，等于 。

交換邊 與 的標號變為1和0，與頂點 相接的0-邊變為2條。在 的作用下，頂點 的標號不變，頂點 變為0。 的值又減少2，等于 。

交換邊 與 的標號變為1和0，與頂點 相接的0-邊變為2條。在 的作用下，頂點 的標號不變，頂點 變為0。則 的值又減少2，等于0。

定理 1：若 ，即 時，圖 的邊平衡指數集為 。

引理3：若 ，即 時，那么圖 的最大邊平衡指數是 。

證明：令與頂點 相接的4條邊為0-邊，與頂點相接的4條邊也為0-邊。

在圖中共有5n條邊，即當 時， 。由邊—友好標號的定義，得構造圖中的邊為友好標號。在構造圖中，頂點 ， 和 標號為0，其它頂點標號為1。又因圖中每個頂點都在 下定義，且圖中共有3n個頂點，那么 。

在圖 中，最外、最內兩個 圈的頂點與之相鄰的邊數為3，而與內圈的頂點相鄰的邊數是4。因在此構造圖中，頂點 ， 相接的0-邊個數為4，與頂點 相連接的邊有3條0-邊，其它頂點僅有一0-邊與之相鄰。故若把構造圖中的任一0-邊和1-邊互換，那么0-點的個數，或不變或增加，而1-點的個數減少，則 的值必減少。

故，在此構造圖中得到的 的值最大，即 。

引理 4：在圖 中，若 ，即 時，則

。

證明：在引理3中構造的 圖中，交換邊 與 的標號變為1和0，有2條0-邊與頂點 相接。在 的作用下，頂點 無定義。則 的值減少1。

（1）交換邊 與 的標號變為0和1，頂點 有2條0-邊與其相接。在 的作用下，頂點 變為0。則 的值減少2，等于 。

交換邊 與 的標號變為1和0，有2條0-邊與頂點 相接。在 的作用下，頂點 變為0。則 的值減少2，等于 。

交換邊 與 的標號變為1和0，頂點 有2條0-邊與之相接。在 的作用下，頂點 變為0。則 的值減少2 ，等于 。

（2）交換邊 與 的標號變為1和0，與頂點 相接的邊中有3條0-邊。在 的作用下，頂點 變為0。 的值減少1，等于 。

交換邊 與 ，邊 與 的標號變為0和1，0和1，得頂點 ， 有2條0-邊與之相接。在 的作用下，頂點 ， 變為0。 的值減少2，等于 ，

交換邊 與 的標號變為1和0，與頂點 相接的邊中有2條0-邊。在 的作用下，頂點 變為0。 的值減少2，等于 。

參考文獻：

[1]M.C.Hong and Sin-Min Lee， On the edge-balanced graphs， In Proceeding of the 7 th Quadrennial International Conference on the Theory anf Applications of Graphs， vol.2， p.711-722.

[2]Yuge Zheng and Ying Wang， On the Edge-Balance Index Sets of ， 2010 International Conference on Network and Digital Society， v2， p.360-363，2010.

[3]B.L.Chen，K.C. Huang and Shi-Shen Liu，On edge-balanced multigraphs，Journal of Combinatorial Mathematics and Combinatorial Computing，42 （2002），177-185.R. Nicole.

[4]Alexander Nien-Tsu Lee， Sin-Min Lee and Ho Kuen Ng， On The Balance Index Set of Graphs， Journal of Combinatorial Mathematics and Combinatorial Computing.， 66 （2008）， 133-150.

[5]Yu Guangming， Zeng Qun， Yang Shan， Hu Limei， Li Xiaowei， Che Yi and Zheng Yuge， On the intensity and type transition of land use at the basin scale using RS/GIS： A case study of the Hanjiang River Basin， Environmental Monitoring and Assessment， v 160， n 1-4， p 169-179， January 2010.