1. NCCU Academic Hub
  2. Publications
  3. College of Science
  4. Theses
  5. Item

Publications-Theses

Article View/Open

Publication Export

Google ScholarTM

NCCU Library

Citation Infomation

Related Publications in TAIR

題名 Maximum Gap of Mixed Hypergraph
作者 郭威廷
Kuo, Wei-Ting
貢獻者 張宜武
郭威廷
Kuo, Wei-Ting
關鍵詞 mixed hypergraph
feasible set
gap
日期 2005
上傳時間 17-Sep-2009 13:50:58 (UTC+8)
摘要 A mixed hypergraph is a triple H = (X; C;D), where X is the vertex set, and each of C;D is a list of subsets of X. A strict t-coloring is a onto mapping from X to {1, 2,…,t} such that each c belongs to C contains two vertices have a common value and each d belongs to D has two vertices have distinct values. If H has a strict t-coloring, then t belongs to S(H), such S(H) is called the feasible set of H, and k is a gap if there are a value larger than k and a value less than k in the feasible set but k is not.
We find the minimum and maximum gap of a mixed hypergraph with more than 5 vertices. Then we consider two special cases of the gap of mixed hypergraphs. First, if the mixed hypergraphs is spanned by a complete bipartite graph, then the gap is decided by the size of bipartition. Second, the (l,m)-uniform mixed hypergraphs has gaps if l > m/2 >2, and we prove that the minimum number of vertices of a (l,m)-uniform mixed hypergraph which has gaps is (m/2)( l -1) + m.
參考文獻 [1] E. Bulgaru and V. Voloshin, Mixed interval hypergraphs, Discrete Applied Math. 77
(1997), 29–41.
[2] T. Jiang, D. Mubayi, Z. Tuza, V. Voloshin, and D. West, The chromatic spectrum of
mixed hypergraphs, Graphs Combin. 18 (2003), 309–318.
[3] D. Kr´al’, J. Kratochv´il, and H. Voss, Mixed hypercacti, Discrete Math. 286 (2004),
99–113.
[4] M. Gionfriddo, L. Milazzo, and V. Voloshin, On the upper chromatic index of a
multigraph, Computer Science J. Moldova 10 (2002), 81–91.
[5] V. Voloshin, On the upper chromatic number of a hypergraph, Australasian J. Comb.
11 (1995), 25–45.
描述 碩士
國立政治大學
應用數學研究所
92751017
94
資料來源 http://thesis.lib.nccu.edu.tw/record/#G0927510171
資料類型 thesis
dc.contributor.advisor 張宜武zh_TW
dc.contributor.author (Authors) 郭威廷zh_TW
dc.contributor.author (Authors) Kuo, Wei-Tingen_US
dc.creator (作者) 郭威廷zh_TW
dc.creator (作者) Kuo, Wei-Tingen_US
dc.date (日期) 2005en_US
dc.date.accessioned 17-Sep-2009 13:50:58 (UTC+8)-
dc.date.available 17-Sep-2009 13:50:58 (UTC+8)-
dc.date.issued (上傳時間) 17-Sep-2009 13:50:58 (UTC+8)-
dc.identifier (Other Identifiers) G0927510171en_US
dc.identifier.uri (URI) https://nccur.lib.nccu.edu.tw/handle/140.119/32613-
dc.description (描述) 碩士zh_TW
dc.description (描述) 國立政治大學zh_TW
dc.description (描述) 應用數學研究所zh_TW
dc.description (描述) 92751017zh_TW
dc.description (描述) 94zh_TW
dc.description.abstract (摘要) A mixed hypergraph is a triple H = (X; C;D), where X is the vertex set, and each of C;D is a list of subsets of X. A strict t-coloring is a onto mapping from X to {1, 2,…,t} such that each c belongs to C contains two vertices have a common value and each d belongs to D has two vertices have distinct values. If H has a strict t-coloring, then t belongs to S(H), such S(H) is called the feasible set of H, and k is a gap if there are a value larger than k and a value less than k in the feasible set but k is not.
We find the minimum and maximum gap of a mixed hypergraph with more than 5 vertices. Then we consider two special cases of the gap of mixed hypergraphs. First, if the mixed hypergraphs is spanned by a complete bipartite graph, then the gap is decided by the size of bipartition. Second, the (l,m)-uniform mixed hypergraphs has gaps if l > m/2 >2, and we prove that the minimum number of vertices of a (l,m)-uniform mixed hypergraph which has gaps is (m/2)( l -1) + m.		en_US
dc.description.tableofcontents Abstract i
1 Introduction 1
2 Maximum gaps of mixed hypergraphs with n vertices 3
3 Mixed hypergraphs spanned by complete bipartite graphs 8
4 Gaps of (l,m)-uniform mixed hypergraphs 11
References 15		zh_TW
dc.format.extent 44963 bytes-
dc.format.extent 54623 bytes-
dc.format.extent 73827 bytes-
dc.format.extent 43069 bytes-
dc.format.extent 81686 bytes-
dc.format.extent 92910 bytes-
dc.format.extent 91858 bytes-
dc.format.extent 107690 bytes-
dc.format.extent 46024 bytes-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.format.mimetype application/pdf-
dc.language.iso en_US-
dc.source.uri (資料來源) http://thesis.lib.nccu.edu.tw/record/#G0927510171en_US
dc.subject (關鍵詞) mixed hypergraphen_US
dc.subject (關鍵詞) feasible seten_US
dc.subject (關鍵詞) gapen_US
dc.title (題名) Maximum Gap of Mixed Hypergraphen_US
dc.type (資料類型) thesisen
dc.relation.reference (參考文獻) [1] E. Bulgaru and V. Voloshin, Mixed interval hypergraphs, Discrete Applied Math. 77zh_TW
dc.relation.reference (參考文獻) (1997), 29–41.zh_TW
dc.relation.reference (參考文獻) [2] T. Jiang, D. Mubayi, Z. Tuza, V. Voloshin, and D. West, The chromatic spectrum ofzh_TW
dc.relation.reference (參考文獻) mixed hypergraphs, Graphs Combin. 18 (2003), 309–318.zh_TW
dc.relation.reference (參考文獻) [3] D. Kr´al’, J. Kratochv´il, and H. Voss, Mixed hypercacti, Discrete Math. 286 (2004),zh_TW
dc.relation.reference (參考文獻) 99–113.zh_TW
dc.relation.reference (參考文獻) [4] M. Gionfriddo, L. Milazzo, and V. Voloshin, On the upper chromatic index of azh_TW
dc.relation.reference (參考文獻) multigraph, Computer Science J. Moldova 10 (2002), 81–91.zh_TW
dc.relation.reference (參考文獻) [5] V. Voloshin, On the upper chromatic number of a hypergraph, Australasian J. Comb.zh_TW
dc.relation.reference (參考文獻) 11 (1995), 25–45.zh_TW