關於(2,3)-圖形零和流數之研究

Zero-Sum Flow Numbers of (2,3)-Graphs

游鎮魁(Zhen-Kui Eu)

指導教授 ： 翁志文

國立交通大學/理學院/應用數學系暨研究所/碩士(2016年)

摘要

對一無向圖形 G，令 E(v) 記為圖形中頂點 v 的相鄰邊所構成之集合。圖 G 上一零和流為一組對邊的非零實數編號 f 使得對每一頂點 v 來說，

∑ f (e) = 0
e∈E(v)

皆成立。 零和 k-流為一零和流且編號全來自集合{±1,...,±(k−1)}。 零和流數 F(G) 定義為圖 G 具有零和 k-流之最小正整數 k。在此篇論文中，對一(2,3)-圖形 G 給出了具有零和流數 3 的充分且必要之條件。此外我們研究由路徑和樹擴展而成之(2,3)-圖形上的零和流數，名曰，聖誕燈、樹燈，並總結它們的零和流數最多為 5。

關鍵字

零和流 ； 零和 k-流 ； 零和流數 ； (2,3)-圖形 ； 聖誕燈 ； 樹燈

並列摘要

For an undirected graph G, let E(v) denote the set of edges incident on a vertex v ∈ V(G). A zero-sum flow is an assignment f of non-zero real numbers on the edges of G such that

∑ f (e) = 0
e∈E(v)

for all v ∈ V(G). A zero-sum k-flow is a zero-sum flow with integers from the set {±1,...,±(k−1)}. Let zero-sum flow number F(G) be defined as the least number of k such that G admits a zero-sum k-flow. In this paper, a necessary and sufficient condition for (2,3)-graph G with F(G) = 3 is given. Furthermore we study zero-sum flow number of (2,3)-graphs expanded from path and tree, namely, the Christmas lamps, the tree lamps, respectively, and conclude that their zero-sum flow numbers are at most 5.

並列關鍵字

zero-sum flow ； zero-sum k-flow ； zero-sum flow number ； (2,3)-graph ； Christmas lamp ； tree lamp

參考文獻

[2] S. Akbari, A. Daemi, O. Hatami, A. Javanmard, A. Mehrabian, Zero-Sum Flows in Regular Graphs, Graphs and Combinatorics 26, pp. 603-615, 2010.

[3] S. Akbari, N. Ghareghani, G. B. Khosrovshahi, S. Zare, A note on zero-sum 5-flows in regular graphs, Electronic Journal of Combinatorics 19(2), P7, 2012.

[4] P.D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser. B 30, pp. 130-135, 1981.

[5] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad J. Math. 6, pp. 80-91, 1954.

[6] W.T. Tutte, A class of abelian groups, Canad J. Math. 8, pp. 13-28, 1956.