臺灣博碩士論文加值系統

本論文所要研究的是圖形的傳播時間，我們先給定一個圖形 ，如果 是圖中的一個子點集，當它為這個圖的傳播集合時，我們定義 是此圖上經由傳播集合中的點傳遞至所有點時所需花的最小傳播時間，並定義 為圖上有 個起始點時的最小傳播時間。

當 和 為圖形 中之兩個子點集時，對於所有在圖形 上的點 而言，定義 為 兩點的最小距離，其中 是子點集 中的點；而 定義為 兩點的最小距離，但此時 為子點集 中的點。再者定義 表 到 距離中的最大值，因此若子點集 中的點有 個時，則 表為這些 中的最小值。對於圖中的任一點 到圖中一子集 的距離均為 的這些點所成的集合定義為 ;而 中的點的個數定義為 。

在本文中，我們研究了一些圖形 和圖形 的 和兩個起始點的傳播問題。

Given a graph G and a vertex subset S of V(G), the
broadcasting time with respect to} S, denoted by b(G,S), is the minimum broadcasting time when using S as the broadcasting set. And the k-broadcasting number, denoted by bk(G), is defined by bk(G)=min{b(G,S)|S subseteq V(G),
|S|=k}}

For a given graph G and two vertex subsets S, S of
V(G). For all v in V(G), define d(v,S)=minlimits{u in S}
d(v,u),d(S,S'})=min{d(u,v)|u in S,v in S', and
d(G,S)=maxlimits{v in V(G)}d(v,S). For all k, k leqslant
|V(G)|, the k-radius of G, denoted by rk(G), is defined
as rk(G)=min {d(G,S) | S subseteq V(G),|S|=k}. For a vertex
subset S of V(G), we also define the m-neighbor of S to be
the set Nm(S)={v in V(G)| d(v,S)=m}, and nm(S)=|Nm(S)|.}

In this thesis, we study the 2-radius and the
2-broadcasting number of the graphs CmXPn and the graphs CmXCn.

1.Introduction 1

2.Lower bound of the k-broadcasting number of
graphs 3

3.The 2-radius and 2- broadcasting number of
CmXPn 6

4.The 2-radius and 2- broadcasting number of
CmXCn 20

5.Conclusion 32

[1] A. Farley and S. Hedetniemi, ``Broadcasting in
grid graphs.' In Proc. Ninth SE Conf. on
Combinatorics, Graph Theory and Computing. Utilitas
Mathematica, Winnipeg, 1987.

[2] A. Farley and A. Proskurowski, ``Broadcasting in
trees with multiple originators.' SIAM J. Alg.
(1981) 381-386.

[3] M. Garey and D. Johnson, Computers and
Intractability: A Guide to the Theory of NP-
Completeness. Freeman, San Francisco, 1979.

[4] S. M. Hedetniemi and S. T. Hedetniemi,
``Broadcasting by decomposing trees into paths of
bounded length'. Technical Report CS-TR-79-16,
University of Oregon, 1979.

[5] S. M. Hedetniemi, S. T. Hedetniemi and A. L.
Liestman, ``A Survey of gossiping and broadcasting in
communication networks', Networks(1988), 319-349.

[6] P. J. Slater, E. Cockayne and S. T. Hedetniemi,
``Information dissemination in trees.' SIAM J. Comput.
(1981) 692-701.

[7] K. W. Tien, Broadcasting Problemin Communation
Networks, Master Thesis, Dept. Applied
Math., National Chiao
Tung Univ., 2000.

[8] Y. S. Tsay, Gossiping and Broadcasting in
Communation Networks, Phd. Thesis, Dept. Applied
Math.,National Chiao TungUniv., 1996.

[9] M. F. Tung, The Multiple Originator
Broadcasting Problem in Graphs, Master thesis, Dept.
Applied Math.,National Dong Hwa Univ., 2001.