臺灣博碩士論文加值系統

1966 年, 艾迪續證明任何有 n 點簡單圖的邊集合, 其中無孤立點, 均能被最多 ⌊n2/4⌋ 團所覆蓋, 幾十年後 McGuinness 證明任何一個貪婪團分割均為這樣的一個分割, 這篇論文證明與其對應的集合表示也不會用到超過 ⌊n2/4⌋ 元素

In 1966 Erd¨os et al. [8] proved that the edge set of any simple graph G with n vertices, no one of which is isolated vertex, can be partitioned using
at most ⌊n2/4⌋ cliques. A couple of tens of years behind McGuinness
proved that any greedy clique partition is such a partition.
In this paper we prove that any set representation corresponding to it wouldn't use more than ⌊n2/4⌋ element.

Abstract 2
1 Introduction 5
2 partition edge set by cliques 6
3 Clique partition of complete multigraph Kn and finite linear
space. 23
4 Various intersection numbers of complete multigraph. 26
5 The intersection number of diamond-free multigraph. 30
6 Intersection number and antichain intersection number of
line graph. 34
7 Clique-Helly graph, maximal clique irreducible graph, and
strongly chordal graph. 54

[1] R. Alter and C.C. Wang, Uniquely intersectable graphs, Discrete Math-
ematics 18 (1977) 217-226.
[2] R. P. Anstee and M. Farber, Characterizations of totally balanced matrices,
J. Algorithms 5 (1984) 215-230.
[3] Batten L. M., Combinatorics of Finite Geometries, Cambridge University
Press, Cambridge, New York, Melbourne (1986).
[4] Batten L. M. and Beutelspacher A., The theory of finite linear spaces,
Cambridge University Press (1993).
[5] W. G. Bridges, Near 1-designs, Journal of Combinatorial Theory (Series
A) Volume 13 Issue 1 (July 1972) 116-126.
[6] de Bruijn N. G. and Erd¨os P. (1948), On a combinatorial problem, Indag.
Math. 10 421-423 and Nederl. Akad. Wetensch. Proc. Sect. Sci. 51 1277-
1279.
[7] S. Bylka and J. Komar, Intersection properties of line graphs, Discrete
Mathematics 164 (1997) 33-45.
[8] P. Erd¨os, A. Goodman, and L. Posa, The representation of a graph by
set intersections, Canad. J. Math. 18 (1966) 106-112.
[9] M. Frber, Characterizations of strongly chordal graphs, Discrete Math.
43 (1983) 173-189.
[10] N. V. R. Mahadev and T. M. Wang, On uniquely intersectable graphs,
Discrete Mathematics 207 (1999) 149-159.
[11] Sean McGuinness and Rolf REES, On the number of distinct minimal
clique partitions and clique covers of a line graph, Discrete Math. 83
(1990) 49-62.
[12] McGuinness S., The greedy clique decomposition of a graph, J. Graph
Th. 18 (1994) 427-430.
[13] J. Orlin, Contentment in graph theory: covering graphs with cliques,
Indag. Math. 39 (1977) 406-424.
[14] E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin.
Comput. 14 (1993) 216-220.
[15] J.L. Szwarcfiter, Recognizing clique-Helly graphs, Ars Combinatoria 45
(1997) 29-32.
[16] M. Tsuchiya, On intersection graphs with respect to uniform families,
Utilitas Math. 37 (1990) 3-12.
[17] M. Tsuchiya, On intersection graphs with respect to antichains (II),
Utilitas Math. 37 (1990) 29-44.
[18] W.D. Wallis and G-H. Zhang, On maximal clique irreducible graphs, J.
Combin. Math. Combin. Comput. 8 (1990) 187-193.
[19] D. B. West, Introduction to Graph Theory, Second Edition, Prentice-
Hall, Upper Saddle River, NJ, 2004.